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?

  • Redjard@lemmy.dbzer0.com
    3·
    8 months ago

    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.

  • Feathercrown@lemmy.worldEnglish
    3·
    8 months ago

    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?