submitted 8 months ago* (last edited 8 months ago) by Sibbo@sopuli.xyz to c/askmath

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?

top 7 comments

sorted by: hot top controversial new old

[-] Feathercrown@lemmy.world 3 points 8 months ago* (last edited 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?

[-] Feathercrown@lemmy.world 3 points 8 months ago* (last edited 8 months ago)

Is there an algorithm that decides if two arbitrary graphs in polynomial time?

If two arbitrary graphs are what? I assume isomorphic.

[-] Sibbo@sopuli.xyz 2 points 8 months ago

Fixed

[-] Sibbo@sopuli.xyz 3 points 8 months ago

Fixed

[-] MBM 3 points 8 months ago

Unless I'm reading your question wrong, it's an open question so nobody knows

[-] Sibbo@sopuli.xyz -1 points 8 months ago

That's why I'm asking

[-] Redjard@lemmy.dbzer0.com 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.

this post was submitted on 13 Mar 2024

8 points (90.0% liked)

Ask Math Problems

82 readers

1 users here now

founded 8 months ago

MODERATORS

MagneticElectron