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?

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

[-] 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?

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

Fixed

[-] 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

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