Ask Math Problems
Sibbo
•
7mo ago
•
90%
Graph isomorphism
Definitions
A graph G = (V, E) is a set of nodes V and a set of undirected edges E. An undirected edge is a set of two vertices.
Two graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorph if there is a bijective mapping f from V1 to V2 such that f(E1) = E2. Applying f to E1 means applying it to each node in each edge in E1.
Problem
Is there an algorithm that decides if two arbitrary graphs are isomorphic in polynomial time?
Comments 7