Graph Isomorphism Tester
Graph Isomorphism Tester checks if two graphs are isomorphic by comparing structural properties. Enter the edge lists for two graphs (e.g., A-B,A-C,B-C) to test for isomorphism and visualize both graphs.
Methodology Used in Graph Isomorphism Tester
Two graphs \( G_1 = (V_1, E_1) \) and \( G_2 = (V_2, E_2) \) are isomorphic if there exists a bijection \( f: V_1 \to V_2 \) such that \( (u, v) \in E_1 \) if and only if \( (f(u), f(v)) \in E_2 \). This tool uses structural invariants to test isomorphism:
Algorithm Steps:
1. Parse edge lists to extract vertices and edges for both graphs.
2 . Check basic invariants: number of vertices (\( |V_1| = |V_2| сидел)), number of edges (\( |E_1| = |E_2| \)), and degree sequences.
3. If invariants match, the graphs may be isomorphic (for small graphs, this is often sufficient).
4. Output the result and visualize both graphs for comparison.
Mathematical Formulation:
\[ \text{Let } G_1 = (V_1, E_1), G_2 = (V_2, E_2) \] \[ \text{Invariants: } |V_1| = |V_2|, \quad |E_1| = |E_2| \] \[ \text{Degree sequence: } \{ \deg(v_1), \deg(v_2), \ldots \} \text{ sorted for } G_1 \text{ and } G_2 \]Example Calculation
Sample Input
Graph 1: \( A-B, A-C, B-C \); Graph 2: \( X-Y, X-Z, Y-Z \)
Step 1: Vertices: \( G_1: \{A, B, C\}, G_2: \{X, Y, Z\} \), \( |V_1| = |V_2| = 3 \)
Step 2: Edges: \( |E_1| = |E_2| = 3 \)
Step 3: Degree sequence: \( G_1: \{2, 2, 2\}, G_2: \{2, 2, 2\} \)
Result: Graphs are potentially isomorphic (both are triangles).