izomorfizm grafów
- yorgin
- Użytkownik
- Posty: 12762
- Rejestracja: 14 paź 2006, o 12:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 17 razy
- Pomógł: 3440 razy
izomorfizm grafów
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.
lub
gdy macierze sąsiedztwa tych grafów są równe z dokładnością do permutacji wierszy/kolumn.
Tyle znam.
-
- Użytkownik
- Posty: 1054
- Rejestracja: 8 paź 2012, o 23:19
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 696 razy
izomorfizm grafów
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
-
- Użytkownik
- Posty: 1054
- Rejestracja: 8 paź 2012, o 23:19
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 696 razy
izomorfizm grafów
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ę?
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
- Użytkownik
- Posty: 12762
- Rejestracja: 14 paź 2006, o 12:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 17 razy
- Pomógł: 3440 razy
izomorfizm grafów
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}\)
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}\)
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
izomorfizm grafów
To trochę za mało.yorgin pisze:Wtedy, gdy istnieje bijekcja między wierzchołkami zachowująca ich stopnie
\(\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}}\)