Algorytm sprawdzania czy graf jest izomorficzny

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
MichalProg
Administrator
Administrator
Posty: 406
Rejestracja: 28 cze 2011, o 21:11
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 62 razy
Pomógł: 1 raz

Algorytm sprawdzania czy graf jest izomorficzny

Post autor: MichalProg » 26 lip 2020, o 14:10

Dzień dobry.

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

Dzięki
M.

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9327
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 2040 razy

Re: Algorytm sprawdzania czy graf jest izomorficzny

Post autor: Dasio11 » 26 lip 2020, o 15:53


MichalProg
Administrator
Administrator
Posty: 406
Rejestracja: 28 cze 2011, o 21:11
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 62 razy
Pomógł: 1 raz

Re: Algorytm sprawdzania czy graf jest izomorficzny

Post autor: MichalProg » 27 lip 2020, o 21:24

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.

ODPOWIEDZ