Czy dostrzegasz podobieństwo? cz.1

04.06.2009 - Damian Rusak
Trudność

Jak myślisz, czy te grafy są takie same?



No tak, to nie było trudne. A te dwa poniżej?

Wystarczy zmniejszyć kąt między wierzchołkami i mamy dwa identyczne grafy. A co można powiedzieć o tych dwóch?

Widać od razu, że żadne przesuwanie nic tu nie pomoże. Te dwa są po prostu inne. Teraz przyjrzyjmy się następnym dwóm. Czy są takie same?

No tak, to już nie jest takie proste.  Fajnie byłoby móc poprzesuwać wierzchołki grafu na obrazku i się przekonać. Na szczęście tuż, tuż czeka gra.  Sprawdź, czy uda Ci się dostrzec podobieństwo (lub jego brak) pomiędzy dwoma grafami. Wystarczy przeciągać wierzchołki zielonego grafu na wierzchołki czerwonego. Jeśli to niemożliwe, trzeba nacisnąć przycisk na górze. Na wyższych poziomach zaczyna robić się ciekawie…  Aby przejść do następnego poziomu po odnalezieniu izomorfizmu należy nacisnąć przycisk z "trzema kropkami" na górze ekranu.


Demonstracja izomorfizmu grafów

 

Przeglądarka ma wyłączoną obsługę Javy lub Java nie została zainstalowana. Pobierz Javę

Zgłoś problem z apletem

 

O grze

Co właściwie działo się w tej grze? Trzeba dopasować do siebie dwa grafy i szybko się okazuje, że to może być trudne, jeśli nie ma się sprytnego sposobu. Oto kilka wskazówek, na pewno wpadłeś (wpadłaś) już na którąś z nich:


a) Liczby na wierzchołkach oznaczają, ilu ten wierzchołek ma sąsiadów. W takim razie pasują do siebie tylko wierzchołki z tą samą liczbą (nazywamy ją stopniem wierzchołka),


b) Najlepiej zacząć od pewniaków. Jeśli mamy tylko po jednym wierzchołku o stopniu 4, to wiadomo, że trzeba je połączyć. Potem łatwiej dopasować resztę. Szybko możemy stwierdzić, że grafy się różnią, jeśli w którymś występuje więcej wierzchołków pewnego stopnia niż w drugim. Wtedy na pewno jeden z nich zostanie bez pary.


c) Podobnie można szukać charakterystycznych połączeń. W grafie jest tylko jedna para połączonych wierzchołków o stopniach 3? W takim razie wiadomo, gdzie musi wylądować. Znaleźliśmy cykl wierzchołków, który występuje tylko w jednym miejscu? Łatwo go będzie dopasować.


d) Graf jest zwykle bardzo poplątany. Dlaczego nie ułatwić sobie zadania, i najpierw nie poprzesuwać go, żeby miał rozsądny kształt? Im mniej krawędzi się w nim przecina, tym lepiej widać, jak jest zbudowany. Może nawet uda się to zrobić tak, żeby żadne krawędzie się nie przecinały? Wtedy graf wygląda jak siatka jakiejś bryły albo mapa i prosto jest znaleźć pasujące do siebie fragmenty dwóch grafów. Takie grafy nazywamy grafami planarnymi.

 

Jak to mądrze nazwać?

Skoro dla takich kilku prostych grafów można wymyślić fajne sposoby na dopasowanie, to czy podobnie będzie dla bardziej skomplikowanych? Co  tak naprawdę robimy, mówiąc, że przesuwamy graf, albo dopasowujemy jeden graf do drugiego?


To wszystko nazywa się izomorfizmem.


Ta nazwa pochodzi od greckich słów isos ("równy") i morphos ("kształt"). Dwa grafy są izomorficzne, jeśli mają ten sam kształt, czyli taką samą strukturę. Dopasowanie wierzchołków jednego grafu do wierzchołków drugiego to właśnie izomorfizm.  Stąd na górnym przycisku w grze jest napis "nie są izomorficzne – nie da się dopasować".

 

Kilka ciekawych przykładów

Na pewno zauważyłeś (zauważyłaś), że czasem dwa grafy można do siebie dopasować na więcej niż jeden sposób:



Te dwa grafy można dopasować jeszcze na cztery inne sposoby. Czy potrafisz je znaleźć?


Znalezienie izomorfizmu trochę utrudnia to, że wierzchołki są anonimowe i łatwo się mylą. Może dobrym pomysłem byłoby nazwanie ich? Wtedy zamiast przesuwać je ręcznie, albo rysować strzałki, można by po prostu napisać, który wierzchołek pasuje do którego. Możemy skorzystać z liczb albo liter i wypisać po kolei, która liczba odpowiada której literze:




Sprawdź, czy to faktycznie izomorfizm. Np. 1 sąsiadowało z 2 i 6. Odpowiadają im wierzchołki A, B i F i faktycznie w drugim grafie A sąsiaduje z B i z F.
Ważne! Jeżeli nazwiemy wierzchołki, wtedy jeśli dwa konkretne wierzchołki są ze sobą połączone przed dopasowaniem do drugiego grafu, to ich odpowiedniki w drugim grafie też muszą być ze sobą połączone.


Jakie litery należy przyporządkować liczbom na tym rysunku?:

Zastosowania praktyczne

Izomorfizmy grafów to zagadnienie na tyle ciekawe, że musi mieć jakieś praktyczne zastosowanie. Ze sposobów znajdowania izomorfizmów korzystają m.in. informatyka chemiczna i elektronika. W skrócie można powiedzieć, że wiele badanych przez chemików substancji ma bardzo skomplikowaną budowę, którą można przedstawić za pomocą grafu połączeń pomiędzy atomami. Stwierdzenie, czy dwie badane cząsteczki reprezentują tę samą substancję nie jest proste – jest to bowiem pytanie też o to, czy grafy tych cząsteczek są izomorficzne. W przypadku, gdy tych atomów są dziesiątki albo setki, potrzeba wydajnych algorytmów, które odpowiedzą na pytanie, co to za substancja i znajdą informacje o niej w bazie danych.

Jeśli uważasz, że wiesz już o izomorfizmach wszystko, to zapraszamy do następnej części – tu spojrzymy na izomorfizm pod kątem informatycznym.

 

4.727275
Twoja ocena: Brak Ocena: 4.7 (11 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com