izomorfizm grafów

[tukanik]

Witam
Kiedy dwa grafy są izomorficzne? Tzn., jakie są warunki?

[yorgin]

Wtedy, gdy istnieje bijekcja między wierzchołkami zachowująca ich stopnie

lub

gdy macierze sąsiedztwa tych grafów są równe z dokładnością do permutacji wierszy/kolumn.

Tyle znam.

[tukanik]

co oznacza równość z dokładnością do permutacji? No chyba, że nie jest to odpowiedź na kilka zdań, to nie odpowiadaj ( ale zakomunikuj mi to ) to sam do tego może kiedyś dojdę ;P

[yorgin]

Jeśli potrafisz przepermutować wiesze/kolumny jednej macierzy tak, aby dostać drugą.

[tukanik]

ok, czyli podstawowym warunkiem jest to, żeby macierze sąsiedztwa były takie same pod względem jakościowym.
Rozumiem, że chodzi tu o to żeby poprzestawiać te wartości tak, żeby uzyskać takie same macierze.
Teraz pytanie, które chwyty są dozwolone. Jak mniemam, mogę przestawiać liczby tyko w obrębie jednego wiersza, lub w obrębie jednej kolumny. Czy tak?
I jeżeli uzyskam w ten sposób drugi macierz ( czyli tak naprawdę, ten pierwszy jest permutacją drugiego) to oba grafy opisane przez macierze są izomorficzne.
Dobrze myślę?

[yorgin]

Nie przestawiasz liczb w obrębie jednego wiersza/kolumny, tylko zamieniasz całe wiersze/kolumny między sobą. To tak, jakby liczyć rząd macierzy - permutacje wierszy/kolumn nie zmieniają rzędu.

Dla porządku, by była jasność.

Dwa grafy \(\displaystyle{ G_1}\) i \(\displaystyle{ G_2}\) są izomorficzne wtedy i tylko wtedy i tylko wtedy, gdy dla ich macierzy sąsiedztwa \(\displaystyle{ A_1, A_2}\) istnieje macierz permutacji \(\displaystyle{ P}\) taka, że

\(\displaystyle{ PA_1P^{-1}=A_2}\)

[tukanik]

Muszę się nad tym zastanowić

[norwimaj]

Wtedy, gdy istnieje bijekcja między wierzchołkami zachowująca ich stopnie

To trochę za mało.

\(\displaystyle{ \begin{picture}(0,0)
\multiput(0,0)(60,0){2}{
\put(0,0){\line(0,1){20}}
\put(40,0){\line(0,1){20}}
\put(0,20){\line(1,1){20}}
\put(40,20){\line(-1,1){20}}
\put(0,0){\line(1,-1){20}}
\put(40,0){\line(-1,-1){20}}
\put(0,0){\circle*{3}}
\put(0,20){\circle*{3}}
\put(40,0){\circle*{3}}
\put(40,20){\circle*{3}}
\put(20,40){\circle*{3}}
\put(20,-20){\circle*{3}}
}
\put(0,20){\line(1,0){40}}
\put(60,20){\line(2,-1){40}}
\end{picture}}\)

[yorgin]

Zgadzam się. Powinienem dodać jeszcze, że poza zachowaniem stopni, zachowuje się struktura grafu.

[norwimaj]

Chyba najszybciej jest powiedzieć, że zachowana jest relacja sąsiedztwa. O stopniach wtedy wcale nie trzeba mówić.