Graph Isomorphism

Graph Isomorphism

In graph theory, graph isomorphism refers to the concept of two graphs being structurally identical, meaning that they can be transformed into each other simply by renaming their vertices and edges. More formally, two graphs are isomorphic if there exists a one-to-one correspondence between their vertices and edges that preserves adjacency. This means that the graphs have the same structure, even if they might look different when drawn.

1. Definition of Graph Isomorphism

Two graphs $G = (V_G, E_G)$ and $H = (V_H, E_H)$ are isomorphic if there exists a bijection (one-to-one correspondence) $f: V_G \to V_H$ between their vertex sets, such that for every pair of vertices $u, v \in V_G$, there is an edge $(u, v) \in E_G$ if and only if there is an edge $(f(u), f(v)) \in E_H$.

In simpler terms:

• The vertices of $G$ and $H$ correspond in such a way that the edges are preserved.
• If two vertices are connected by an edge in one graph, their corresponding vertices must also be connected by an edge in the other graph.

2. Conditions for Graph Isomorphism

For two graphs to be isomorphic, the following conditions must be met:

1. Same number of vertices: The graphs must have the same number of vertices.
2. Same number of edges: The graphs must have the same number of edges.
3. Same degree sequence: The degree (the number of edges incident to a vertex) of corresponding vertices in both graphs must be the same.
4. Preservation of adjacency: If two vertices are adjacent in one graph, their corresponding vertices must also be adjacent in the other graph.

3. How to Check for Graph Isomorphism

Determining whether two graphs are isomorphic is not always trivial and can require examining different ways to map vertices and edges. Here are some key steps to check for graph isomorphism:

1. Check Basic Properties:

   • Ensure both graphs have the same number of vertices and edges.
   • Check that both graphs have the same degree sequence (the list of degrees of all the vertices).

2. Check Vertex Degree Sequences:

   • The degree sequence of a graph is the list of degrees of all its vertices in non-decreasing order. If two graphs do not have the same degree sequence, they are not isomorphic.

3. Try to Find a One-to-One Vertex Mapping:

   • Attempt to match the vertices of the two graphs based on their degree and adjacency. Start with vertices that have the same degree and try to establish correspondences while preserving the adjacency structure.

4. Check Edge Correspondence:

   • For each vertex pair you match, verify that the edges corresponding to them match the adjacency relations in the other graph.

5. Use Algorithms for Larger Graphs:

   • For larger graphs, specialized algorithms (such as the Nauty algorithm, Bliss algorithm, or VF2 algorithm) are used to check graph isomorphism efficiently.

4. Example of Graph Isomorphism

Let’s consider two graphs $G$ and $H$ with the following adjacency lists:

• Graph $G$:

  • Vertices: $V_G = \{A, B, C, D\}$
  • Edges: $E_G = \{(A, B), (A, C), (B, D), (C, D)\}$

• Graph $H$:

  • Vertices: $V_H = \{W, X, Y, Z\}$
  • Edges: $E_H = \{(W, X), (W, Y), (X, Z), (Y, Z)\}$

Now, let's check if $G$ and $H$ are isomorphic:

1. Same Number of Vertices and Edges:

   • Both graphs have 4 vertices and 4 edges.

2. Same Degree Sequence:

   • In $G$:
     • $\text{deg}(A) = 2$, $\text{deg}(B) = 2$, $\text{deg}(C) = 2$, $\text{deg}(D) = 2$.
   • In $H$:
     • $\text{deg}(W) = 2$, $\text{deg}(X) = 2$, $\text{deg}(Y) = 2$, $\text{deg}(Z) = 2$.
   • Both graphs have the same degree sequence.

3. Checking Vertex Correspondence:

   • Match the vertices $A$ with $W$, $B$ with $X$, $C$ with $Y$, and $D$ with $Z$, because their degrees and adjacency properties are identical.

4. Check Edges:

   • In $G$: $(A, B), (A, C), (B, D), (C, D)$.
   • In $H$: $(W, X), (W, Y), (X, Z), (Y, Z)$.
   • The adjacency relationships are preserved.

Since the graphs have the same number of vertices, edges, and the degree sequence is identical, and the vertex correspondence preserves adjacency, graphs $G$ and $H$ are isomorphic.

5. Isomorphism Classes

Two graphs are isomorphic if there is a bijection between their vertices and edges. This means that isomorphic graphs belong to the same isomorphism class. Graphs in the same isomorphism class share the same structural properties, even if they look different when drawn.

• Example: A square and a triangle drawn differently can still be isomorphic to each other in certain contexts. However, two graphs with different numbers of vertices or edges can never be isomorphic.

6. Graph Isomorphism Problem

The graph isomorphism problem is a classic computational problem that asks whether two given graphs are isomorphic. It is important in theoretical computer science because:

• It is one of the few problems that is not known to be NP-complete nor known to be solvable in polynomial time (i.e., it is not known whether it’s “easy” or “hard” to solve).
• There are algorithms that work efficiently in practice for many graphs, but the general case remains unsolved in terms of time complexity.

7. Applications of Graph Isomorphism

Graph isomorphism has various applications in different fields:

1. Pattern Recognition:

   • In computer vision, graph isomorphism can be used to match shapes or patterns in images.

2. Chemistry:

   • In molecular chemistry, molecules are represented as graphs, where atoms are vertices and bonds are edges. Isomorphism is used to compare molecular structures to identify identical compounds.

3. Social Network Analysis:

   • In social networks, isomorphism can be used to detect identical structures of relationships, even when the individual identities (vertices) are different.

4. Computer Networks:

   • In distributed systems, network structures are analyzed using graph isomorphism to determine if two networks are structurally equivalent.

8. Summary of Graph Isomorphism

• Graph Isomorphism: Two graphs are isomorphic if there exists a one-to-one mapping between their vertices and edges that preserves adjacency.
• Conditions: Same number of vertices, same number of edges, same degree sequence, and edge correspondence must be preserved.
• Applications: Pattern recognition, chemistry, social networks, and computer networks.
• Graph Isomorphism Problem: It is an important problem in computer science, and while not proven to be NP-complete, no polynomial-time algorithm is known.

Understanding graph isomorphism is essential for analyzing graphs in various practical contexts, from computer science to chemistry, and for solving problems related to structure and equivalence in graphs.