Graph isomorphism

Imagine two drawings of shapes. They might look different. One might be stretched out. The other might be small.

But they can still be the same. This happens if they have the same parts. The parts must connect in the same way.

We call these shapes isomorphic. It means they have the same structure. This is a big puzzle for computers. They try to find these matches. It helps us study things like chemicals.

Finding these matches is very important.

Imagine two drawings of networks. One might look messy. The other might look neat.

Even if they look different, they can be the same. This happens if they have the same structure. We call this graph isomorphism.

In these networks, we have points called vertices. We also have lines called edges. Two graphs are isomorphic if every point and line matches up perfectly. You can move the points around. As long as the connections stay the same, the structure is the same.

Some graphs have special labels or colors. We can still check if they match. We just have to make sure the labels match too. If a graph matches itself, we call it an automorphism.

This is a famous puzzle for computers. It is called the graph isomorphism problem. Scientists use it to study chemicals. It also helps design electronic circuits.

A man named László Babai worked on this. He shared new ideas about how fast computers can solve it. It remains a big mystery in computer science.

Imagine you have two different drawings of a web. One drawing might look like a messy tangle. The other might look like a neat, organized shape.

Even if they look different, they might actually be the same structure. This idea is called graph isomorphism. It means the two graphs are essentially twins. They have the same connections between their points. We call these points vertices and the lines edges.

If you can move the points without breaking the lines, they are isomorphic.

To find an isomorphism, we look for a special match. We need a way to pair every vertex in the first graph with a vertex in the second. This pairing is called a bijection. Every vertex must have exactly one partner. We also check if the edges match up perfectly. If two vertices are connected in the first graph, their partners must be connected in the second. This is often called an edge-preserving bijection. If a graph matches itself perfectly, we call that an automorphism.

Math lovers have studied these patterns for a long time. A man named Hassler Whitney shared a famous rule. This is called the Whitney graph isomorphism theorem. It says two connected graphs are isomorphic if their line graphs match. There is one tiny exception to his rule. The graph K3 and the graph K1,3 are not the same. However, they both have K3 as their line graph.

Today, this is a huge puzzle for computer scientists. It is known as the graph isomorphism problem. It is a very hard job for computers to solve quickly. It is one of only two problems in a special group of twelve. The other mystery problem is integer factorization. In November 2015, László Babai shared a big idea. He is a mathematician from the University of Chicago. He claimed he found a way to solve it in quasi-polynomial time.

We use these math ideas in the real world every day. Scientists use them in cheminformatics to identify chemical compounds. Engineers use them to check the design of electronic circuits. Computers also use them for pattern recognition and computer vision. One tool is the vf2 algorithm from 2001. It helps computers handle graphs with thousands of nodes. This math helps us see the true shape of things.

In the field of graph theory, mathematicians study the structure of networks. A graph consists of vertices, which are points, and edges, which are the lines connecting them. Sometimes, two graphs look completely different when drawn on a page.

One might look like a simple circle, while the other looks like a tangled web.

However, they might actually share the exact same structural pattern. This concept is known as graph isomorphism. Two graphs are isomorphic if they are structurally identical, even if their visual representations differ.

To prove two graphs are isomorphic, we must find a specific type of mapping called a bijection. A bijection is a rule that pairs every vertex in the first graph with exactly one unique vertex in the second graph. This mapping must be an edge-preserving bijection. This means that if any two vertices are connected by an edge in the first graph, their corresponding partners must also be connected in the second graph. If such a mapping exists, the graphs belong to the same isomorphism class. This relationship is an equivalence relation, which allows mathematicians to group all possible graphs into these distinct classes.

There are different ways to define isomorphism depending on the type of graph being studied. The basic definition applies to undirected, non-labeled, and non-weighted graphs. However, we can add more rules for other structures. For example, in directed graphs, the mapping must preserve the direction of the arcs. In weighted graphs, the mapping must preserve the weights assigned to the edges. Labeled graphs are more complex and have two different definitions in use. One definition requires the mapping to preserve both the edges and the specific labels. Another definition only requires preserving the equivalence classes of labels, meaning vertices with equivalent labels must map to each other.

An interesting special case occurs when a graph is mapped onto itself. This type of isomorphism is called an automorphism. When we study the history of these ideas, we find important theorems like the Whitney graph isomorphism theorem. Hassler Whitney showed that two connected graphs are isomorphic if and only if their line graphs are isomorphic. A line graph is a different way of representing the connections between edges. There is one famous exception to this rule. The complete graph on three vertices, known as K3, and the complete bipartite graph K1,3, are not isomorphic.

Despite this, they both share K3 as their line graph.

In computer science, determining if two graphs are isomorphic is a major challenge. This is known as the graph isomorphism problem. It is a significant puzzle because of its place in computational complexity theory. The problem belongs to a class called NP, but it is not known to be in P or to be NP-complete. It is one of only two problems among twelve standard problems where the complexity remains unresolved. The other mystery problem is integer factorization. In November 2015, László Babai from the University of Chicago claimed a breakthrough. He suggested the problem could be solved in quasi-polynomial time. Although he briefly retracted the claim in 2017, he later restored the original result.

This mathematical concept has many practical uses in modern technology. In the field of cheminformatics, scientists use it for the identification of chemical compounds. Electronic design automation also relies on it to verify that different representations of a circuit design are equivalent. Computer scientists use various algorithms to solve these problems. The Weisfeiler-Leman test is a heuristic method used to check for isomorphism. While it can prove two graphs are different, it cannot always prove they are the same. Another tool is the vf2 algorithm, developed by Cordella and others in 2001. This is a depth-first search algorithm that builds an isomorphism incrementally.

Even though the vf2 algorithm has a worst-case exponential time complexity, it works very well in practice. It can efficiently handle graphs containing thousands of nodes. This makes it useful for pattern recognition, computer vision, and bioinformatics. Understanding isomorphism helps us separate the true properties of a structure from how it is drawn. For instance, if a graph has exactly one cycle, every graph in its isomorphism class will also have exactly one cycle. By focusing on these underlying connections, we can understand the fundamental nature of complex networks.