Algorytm sprawdzania czy graf jest izomorficzny

[MichalProg]

Dzień dobry.

Czy jest jakiś zwarty algorytm, którym można jednoznacznie stwierdzić, czy dwa grafy są izomorficzne?

Dzięki
M.

[Dasio11]

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Graph_isomorphism_problem

.

[MichalProg]

Dzięki. Chodziło mi bardziej o taki "ludzki algorytm" porównywania dwóch obrazków grafów i stwierdzenie, czy są izomorficzne. Z tego co się dowiedziałem, wystarczy:

• sprawdzić czy jest taka sama l. wierzchołków
• sprawdzić czy jest taka sama l. krawędzi
• porównać sumy stopni wierzchołków
• zbadać czy te same wierzchołki sąsiadują z tymi samymi w obu grafach

Problem jest tylko taki, że jak graf ma damy na to 15 wierzchołków i pomieszane krawędzie to trudno cokolwiek zobaczyć. Jeszcze w dodatku, jak nie mają podpisanych wierzchołków.