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?
I would think a good way is to find an ordering of nodes. If you can order the nodes of any graph in a repeatable way depending only on the graphs shape, then the ordered form of V1 and V2 should be identical, and ordering E1 and E2 by their nodes would also yield identical lists, if and only if the graphs are isomorphic.
An easy start would be ordering by number of connections, but this of course is in no way sufficient.
Two graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorph if there is a bijective mapping f from V1 to V2 such that if f(E1) = E2.
If f(E1) = E2 then what?
Related:
Is there an algorithm that decides if two arbitrary graphs in polynomial time?
If two arbitrary graphs are what? I assume isomorphic.
Fixed
Fixed
Unless I’m reading your question wrong, it’s an open question so nobody knows
That’s why I’m asking
