Wykres izomorfizmu można opisać jako graf, na którym pojedynczy wykres może mieć więcej niż jedną postać. Oznacza to, że dwa różne grafy mogą mieć tę samą liczbę krawędzi, wierzchołków i taką samą łączność krawędzi. Tego typu wykresy nazywane są wykresami izomorfizmu. Przykład wykresu izomorfizmu opisano w następujący sposób:
Powyższy wykres zawiera następujące elementy:
- Ten sam wykres jest reprezentowany w więcej niż jednej formie.
- Można zatem powiedzieć, że te wykresy są grafami izomorfizmu.
Warunki izomorfizmu grafów
Dowolne dwa wykresy będą nazywane izomorfizmem, jeśli spełniają następujące cztery warunki:
- W podanych grafach będzie taka sama liczba wierzchołków.
- W podanych grafach będzie taka sama liczba krawędzi.
- Na podanych wykresach będzie taka sama liczba stopni.
- Jeżeli pierwszy graf tworzy cykl o długości k za pomocą wierzchołków {v1, v2, v3, …. vk}, to inny graf również musi tworzyć ten sam cykl o tej samej długości k za pomocą wierzchołków {v1, v2, v3, …. vk}.
Uwaga: Sekwencję stopni grafu można opisać jako sekwencję stopni wszystkich wierzchołków w kolejności rosnącej.
Ważne punkty
- Aby dowolne dwa wykresy były izomorfizmem, niezbędnymi warunkami są cztery warunki określone powyżej.
- Nie jest konieczne, aby określone powyżej warunki wystarczyły do wykazania, że dane wykresy są izomorficzne.
- Jeżeli dwa wykresy spełniają wyżej określone cztery warunki, nawet wtedy nie jest konieczne, aby wykresy były na pewno izomorficzne.
- Jeśli graf nie spełnia żadnych warunków, to można powiedzieć, że z pewnością nie jest izomorfizmem.
Warunki wystarczające dla izomorfizmu grafów
Jeśli chcemy udowodnić, że dowolne dwa wykresy są izomorfizmem, istnieją pewne warunki wystarczające, które nam zapewnią, gwarantujące, że te dwa wykresy z pewnością są izomorfizmem. Kiedy oba wykresy pomyślnie spełnią wszystkie powyższe cztery warunki, dopiero wtedy sprawdzimy, czy te wykresy spełniają warunki wystarczające, które opisano w następujący sposób:
- Jeśli wykresy dopełnienia obu wykresów są izomorfizmem, to te wykresy z pewnością będą izomorfizmem.
- Jeśli sąsiednie macierze obu grafów są takie same, to wykresy te będą izomorfizmem.
- Jeżeli poprzez usunięcie niektórych wierzchołków jednego grafu otrzymamy odpowiadające sobie wykresy dwóch grafów, a odpowiadające im obrazy na innych obrazach będą izomorfizmem, to tylko wtedy te wykresy nie będą izomorfizmem.
Jeżeli dwa wykresy spełniają którykolwiek z powyższych warunków, to można powiedzieć, że te wykresy są z pewnością izomorfizmem.
Przykłady izomorfizmu grafów
Istnieje wiele przykładów izomorfizmu grafów, które opisano w następujący sposób:
Przykład 1:
W tym przykładzie pokazaliśmy, czy poniższe wykresy są izomorfizmem.
Rozwiązanie: W tym celu sprawdzimy wszystkie cztery warunki izomorfizmu grafów, które opisano w następujący sposób:
Warunek 1:
- Na grafie 1 znajdują się w sumie 4 wierzchołki, czyli G1 = 4.
- Na grafie 2 mamy w sumie 4 wierzchołki, czyli G2 = 4.
Tutaj,
W obu grafach G1 i G2 jest taka sama liczba wierzchołków. Zatem te wykresy spełniają warunek 1. Teraz sprawdzimy drugi warunek.
Warunek 2:
- Na wykresie 1 znajduje się łącznie 5 krawędzi, czyli G1 = 5.
- Na wykresie 2 jest łącznie 6 krawędzi, czyli G2 = 6.
Tutaj,
Na obu grafach G1 i G2 nie ma równej liczby krawędzi. Zatem te wykresy nie spełniają warunku 2. Nie możemy teraz sprawdzić wszystkich pozostałych warunków.
Ponieważ te wykresy naruszają warunek 2. Zatem te wykresy nie są izomorfizmem.
∴ Wykres G1 i wykres G2 nie są wykresami izomorfizmu.
Przykład 2:
W tym przykładzie pokazaliśmy, czy poniższe wykresy są izomorfizmem.
Rozwiązanie: W tym celu sprawdzimy wszystkie cztery warunki izomorfizmu grafów, które opisano w następujący sposób:
Warunek 1:
- Na grafie 1 znajdują się w sumie 4 wierzchołki, czyli G1 = 4.
- Na grafie 2 mamy w sumie 4 wierzchołki, czyli G2 = 4.
- Na grafie 3 znajdują się łącznie 4 wierzchołki, czyli G3 = 4.
Tutaj,
We wszystkich grafach G1, G2 i G3 liczba wierzchołków jest równa. Zatem te wykresy spełniają warunek 1. Teraz sprawdzimy drugi warunek.
Warunek 2:
- Na wykresie 1 znajduje się łącznie 5 krawędzi, czyli G1 = 5.
- Na wykresie 2 jest łącznie 5 krawędzi, czyli G2 = 5.
- Na wykresie 3 znajduje się łącznie 4 krawędzi, czyli G2 = 4.
Tutaj,
- Na obu grafach G1 i G2 znajduje się taka sama liczba krawędzi. Zatem te wykresy spełniają warunek 2.
- Ale na grafach (G1, G2) i G3 nie ma równej liczby krawędzi. Zatem wykresy (G1, G2) i G3 nie spełniają warunku 2.
Ponieważ wykresy (G1, G2) i G3 naruszają warunek 2. Można więc powiedzieć, że te wykresy nie są izomorfizmem.
∴ Wykres G3 nie jest izomorfizmem ani z grafem G1, ani z grafem G2.
Ponieważ wykresy G1 i G2 spełniają warunek 2. Można więc powiedzieć, że te wykresy mogą być izomorfizmem.
∴ Wykresy G1 i G2 mogą być izomorfizmem.
Teraz sprawdzimy trzeci warunek dla wykresów G1 i G2.
Warunek 3:
- Na wykresie 1 stopień ciągu s wynosi {2, 2, 3, 3}, tj. G1 = {2, 2, 3, 3}.
- Na wykresie 2 stopień ciągu s wynosi {2, 2, 3, 3}, tj. G2 = {2, 2, 3, 3}.
Tutaj
Na obu wykresach G1 i G2 występuje taka sama liczba ciągów stopni. Zatem te wykresy spełniają warunek 3. Teraz sprawdzimy czwarty warunek.
Warunek 4:
równa się metodzie Java
Wykres G1 tworzy cykl o długości 3 za pomocą wierzchołków {2, 3, 3}.
Wykres G2 również tworzy cykl o długości 3 za pomocą wierzchołków {2, 3, 3}.
Tutaj,
Pokazuje, że oba grafy zawierają ten sam cykl, ponieważ oba grafy G1 i G2 tworzą cykl o długości 3 za pomocą wierzchołków {2, 3, 3}. Zatem te wykresy spełniają warunek 4.
Zatem,
- Wykresy G1 i G2 spełniają wszystkie powyższe cztery niezbędne warunki.
- Zatem G1 i G2 mogą być izomorfizmem.
Teraz sprawdzimy warunki wystarczające, aby pokazać, że wykresy G1 i G2 są izomorfizmem.
Sprawdzanie wystarczających warunków
Jak dowiedzieliśmy się, że jeśli wykresy dopełnienia obu wykresów są izomorfizmem, to te dwa wykresy z pewnością będą izomorfizmem.
Narysujemy więc wykresy dopełnienia G1 i G2, które opisano w następujący sposób:
Na powyższych wykresach uzupełnienia G1 i G2 widzimy, że oba wykresy są izomorfizmem.
∴ Wykresy G1 i G2 są izomorfizmem.
Przykład 3:
W tym przykładzie pokazaliśmy, czy poniższe wykresy są izomorfizmem.
Rozwiązanie: W tym celu sprawdzimy wszystkie cztery warunki izomorfizmu grafów, które opisano w następujący sposób:
Warunek 1:
- Na grafie 1 jest łącznie 8 wierzchołków, czyli G1 = 8.
- Na grafie 2 jest łącznie 8 wierzchołków, czyli G2 = 8.
Tutaj,
W obu grafach G1 i G2 jest taka sama liczba wierzchołków. Zatem te wykresy spełniają warunek 1. Teraz sprawdzimy drugi warunek.
Warunek 2:
- Na wykresie 1 całkowita liczba krawędzi wynosi 10, tj. G1 = 10.
- Na wykresie 2 całkowita liczba krawędzi wynosi 10, tj. G2 = 10.
Tutaj,
Na obu grafach G1 i G2 znajduje się taka sama liczba krawędzi. Zatem te wykresy spełniają warunek 2. Teraz sprawdzimy trzeci warunek.
Warunek 3:
- Na wykresie 1 stopień ciągu s wynosi {2, 2, 2, 2, 3, 3, 3, 3}, tj. G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- Na wykresie 2 stopień ciągu s wynosi {2, 2, 2, 2, 3, 3, 3, 3}, tj. G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Tutaj
Na obu wykresach G1 i G2 występuje taka sama liczba ciągów stopni. Zatem te wykresy spełniają warunek 3. Teraz sprawdzimy czwarty warunek.
Warunek 4:
- Wykres G1 tworzy cykl o długości 4 za pomocą wierzchołków stopnia 3.
- Wykres G2 nie tworzy cyklu o długości 4 za pomocą wierzchołków, ponieważ wierzchołki nie sąsiadują ze sobą.
Tutaj,
Obydwa wykresy G1 i G2 nie tworzą tego samego cyklu o tej samej długości. Zatem te wykresy naruszają warunek 4.
Ponieważ wykresy G1 i G2 naruszają warunek 4. Zatem z powodu naruszenia warunku 4 wykresy te nie będą izomorfizmem.
∴ Wykresy G1 i G2 nie są izomorfizmem.