Ask Math Problems

82 readers

1 users here now

founded 8 months ago

MODERATORS

[email protected]

Graph isomorphism (sopuli.xyz)

submitted 8 months ago* (last edited 8 months ago) by [email protected] to c/[email protected]

7 comments fedilink hide all child comments

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?

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 3 points 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.