Jak udowodnić izomorficzność grafów?
-
- Użytkownik
- Posty: 52
- Rejestracja: 8 paź 2016, o 12:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 9 razy
Jak udowodnić izomorficzność grafów?
Udowodnić, że wszystkie grafy proste, o sześciu wierzchołkach, których każdy wierzchołek jest stopnia \(\displaystyle{ 4}\), są izomorficzne.
Ostatnio zmieniony 14 maja 2018, o 19:59 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Re: Jak udowodnić izomorficzność grafów?
Popatrzmy na dopełnienia tych grafów. W dopełnieniu każdy wierzchołek ma stopień \(\displaystyle{ 1}\), a to znaczy, że dopełnienie to trzy krawędzie. Dlatego dopełnienia każdego z tych grafów są izomorficzne, więc i początkowe grafy też.
-
- Użytkownik
- Posty: 52
- Rejestracja: 8 paź 2016, o 12:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 9 razy
Re: Jak udowodnić izomorficzność grafów?
skąd wiadomo, że jeśli dopełnienia grafów są izomorficzne, to początkowe grafy też?
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Re: Jak udowodnić izomorficzność grafów?
No bo jeżeli mamy izomorficzność dwóch grafów to znaczy że istnieje bijekcja \(\displaystyle{ f}\) taka, która przekształca zbiór wierzchołków pierwszego grafu na zbiór wierzchołków drugiego grafu tak, że wierzchołki \(\displaystyle{ x, y}\) pierwszego grafu są połączone krawędzią w pierwszym grafie, wtedy i tylko wtedy gdy, \(\displaystyle{ f(x), f(y)}\) są połączone krawędzią w drugim grafie. No a biorąc dopełnienie, jeżeli były połączone w pierwszym grafie to w jego dopełnieniu nie są (i na odwrót) i to samo z drugim grafem, czyli powyższy warunek nadal jest spełniony.
Ostatnio zmieniony 14 maja 2018, o 21:16 przez Mruczek, łącznie zmieniany 2 razy.
-
- Użytkownik
- Posty: 52
- Rejestracja: 8 paź 2016, o 12:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 9 razy
Re: Jak udowodnić izomorficzność grafów?
i za każdym razem to działa? że jeśli dopełnienia się izomorficzne, to podstawowe grafy też?