Czy dostrzegasz podobieństwo? cz.1
04.06.2009 - Damian Rusak
Jak myślisz, czy te grafy są takie same? 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.
O grzeCo 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:
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?
Kilka ciekawych przykładówNa 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źć?
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.
Zastosowania praktyczneIzomorfizmy 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.
(11 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com