Programisto, nie zapominaj o algorytmach! #6

Jedną z częściej używanych struktur danych, a także z ciekawszych pod względem teoretycznym są grafy i ich bliscy krewni – drzewa. Przyjrzymy się dzisiaj grafom i ich przykładom. Będzie trochę teorii, ale liczę, że wytrwacie do końca!

Teoria grafów wywodzi się od bardzo znanego matematyka i fizyka Leonharda Eulera, który przebywając w Królewcu chciał odpowiedzieć na pytanie „czy możemy przejść kolejno przez wszystkie mosty tak, żeby każdy z nich przekroczyć dokładnie raz i powrócić do punktu wyjścia?”. Opis tego zagadnienia opublikowany przez Eulera w 1741 roku jest pierwszą pracą na temat teorii grafów.

Dzisiaj również rozwiążemy ten problem – ale zacznijmy od początku. Więc – czym jest graf? Formalnie jest to para G=(V,E), gdzie V to niepusty zbiór tzw. wierzchołków (od vertices), a E to rodzina dwuelementowych zbiorów oznaczających krawędzie (od edges). Spójrzmy na przykładzie:

Zbiór Zbiór
 {1,2,3,4}  {(1,2),(1,3),(2,3),(3,4)}

Powyżej widać graf G=(V,E), w tabelce natomiast wyjaśniliśmy zawartość obu zbiorów.

Zatem, przekształcając problem mostów królewieckich, dostaniemy następujący graf (gdzie mosty oznaczamy przez krawędzie):

Problem Eulera, można sparafrazować w następujący sposób – czy możliwe jest narysowanie tego grafu bez odrywania ołówka od kartki, przechodząc przez każdą krawędź dokładnie raz i wracając do punktu startu?

Na pewno spora część z Was zastanawiała się nad takim problemem w dzieciństwie – czy można narysować kopertę bez odrywania ołówka od kartki (ewentualnie wracając do pierwszego punktu)?

Nie udało się, prawda? Oba te obrazki mają jedną cechę wspólną, która powoduje, że takie przejście jest niemożliwe. Zaraz o niej powiemy. Będziemy jednak potrzebować kilku definicji, żeby ustalić wspólny język, którym będziemy rozmawiać o tych problemach.

Stopniem wierzchołka deg⁡(v) nazywamy liczbę krawędzi wychodzących z danego wierzchołka.
Trasą w grafie G nazywamy skończony ciąg krawędzi v0 v1,v1 v2,⋯,v(m-1) vm, zapisywany również w bardziej naturalnej postaci v0→v1→v2→⋯→v(m-1)→vm.

Liczba krawędzi przez które przechodzimy oznacza długość trasy.
Trasę w której nie powtarzają się żadne krawędzi nazywamy ścieżką. Jeśli natomiast w ścieżce wierzchołki są równe – będzie to droga.

Jeśli v0=v_m mówimy, że ścieżka (lub droga) jest zamknięta, a gdy zawiera co najmniej jedną krawędź nazwiemy ją cyklem (to bardzo ważny termin!).
Graf jest spójny dokładnie wtedy gdy każda para wierzchołków jest połączona drogą. Zauważcie, że wszystkie grafy narysowane jak dotąd w artykule były spójne (intuicyjnie: graf jest spójny, jeśli z każdego wierzchołka można dojść do każdego innego).

Mając te podstawy możemy podejść jeszcze raz do naszego problemu mostów królewieckich.
Spójny graf nazwiemy eulerowskim, jeżeli istnieje zamknięta ścieżka zawierająca każdą krawędź tego grafu. Nazwiemy taką ścieżkę: cyklem Eulera. Graf nazwiemy półeulerowskim, jeżeli istnieje w nim ścieżka (otwarta) zawierająca każdą krawędź.

Przykład grafu półeulerowskiego razem z kolejnością przejścia przez krawędzie.

Przykład grafu eulerowskiego razem z kolejnością przejścia przez krawędzie.

Zatem nasze wstępne pytanie sprowadza się do pytania – czy graf królewiecki jest grafem eulerowskim lub chociażby półeulerowskim? Ręczna analiza zdaje się wskazywać, że nie – nie umiemy go narysować bez odrywania ołówka od kartki. Potwierdza ten fakt również matematyka!

Twierdzenie 1 (Euler, 1736) Graf spójny G jest grafem eulerowskim wtedy i tylko wtedy, gdy stopień każdego wierzchołka grafu G jest liczbą parzystą.

Twierdzenie 2 Graf spójny G jest grafem półeulerowskim wtedy i tylko wtedy, gdy ma dokładnie dwa wierzchołki nieparzystych stopni.

Zainteresowana czytelniczka lub czytelnik znajdzie dowody tych twierdzeń np. w książce „Wprowadzenie do teorii grafów” Robina Wilsona (wydanej w Polsce przez Wydawnictwo Naukowe PWN).

Przeanalizujmy nasz graf, patrząc na stopień każdego wierzchołka.

Widzimy tutaj wyraźnie, że żaden z wierzchołków nie ma stopnia parzystego. Więc graf nie jest ani eulerowski, ani półeulerowski.

Dzięki tym dwóm prostym twierdzeniom wiemy już co nieco o grafach i potrafimy stwierdzić czy da się przejść wszystkie krawędzie bez odrywania ołówka od kartki.

Do dalszych zastosowań przyda nam się jeszcze jedna definicja: grafem z wagami (lub ważonym) nazwiemy graf który dla każdej krawędzi e posiada przypisaną wagę weg(e). Często również formalnie graf z wagami oznacza się jako trójkę Gω=(V,E,ω), gdzie przez ω oznaczamy funkcję która każdej z krawędzi przypisuje jej wagę.

Do czego możemy używać grafów (szczególnie ważonych)? Typowym zastosowaniem jest wyszukiwanie najkrótszej ścieżki w grafie – czyli sposobu przejścia między dwoma wybranymi wierzchołkami, minimalizując koszt przejścia (czyli sumę wag).

Możemy zobaczyć to na przykładzie. (w tym wypadku wewnętrznie wierzchołkami są wszystkie kwadraty, a krawędziami ich połączenia).

Grafy są również bardzo wygodnym narzędziem do reprezentowania danych, maszyn stanów (dla ciekawskich: automat skończony) i innych.

Bardzo mocno powiązanym pojęciem z grafem są drzewa i lasy. Lasem nazwiemy graf nie zawierający cykli, a drzewem las spójny. Drzewa są bardzo popularnymi strukturami w informatyce. Używane są do modelowania bardzo wielu zagadnień.

Wewnętrznie są również używane w bazach danych, sieciach komputerowych (dla zainteresowanych: Spanning Tree Protocol) i wielu innych.

Ale o drzewach przeczytacie w kolejnym odcinku 😉

 

Site Footer

Sliding Sidebar