Teoria grafów

Graf – to taka struktura danych, która składa się z wierzchołków i krawędzie, przy czym poszczególne wierzchołki (zwane też węzłami) mogą być połączone krawędziami (skierowanymi lub nieskierowanymi) w taki sposób, iż każda krawędź zaczyna się i kończy w którymś z wierzchołków. Wierzchołki i krawędzie mogą być numerowane, etykietowane i nieść pewną dodatkową informację – w zależności od potrzeby modelu, do którego konstrukcji są wykorzystane. W porównaniu do drzew w grafach mogą występować pętle i cykle. Krawędzie mogą mieć wyznaczony kierunek (wtedy graf nazywamy skierowanym), mogą mieć przypisaną wagę (pewną liczbę), kolor, etykietę, np. odległość pomiędzy punktami w terenie, rodzaj połączenia.
grafnaroznesposoby
W ogólności dopuszcza się krawędzie wielokrotne i pętle (czyli krawędzie, które rozpoczynają i kończą się w tym samym wierzchołku).

 

Mosty królewieckie – narodziny grafów

W osiemnastym wieku mieszkańcy Królewca lubili spacerować po mostach na rzece Pregole, których mieli w mieście siedem. Plan mostów pokazuje rysunek. Ale takie zwykłe spacerowanie po jakimś czasie im się znudziło i zaczęli zastanawiać się, czy jest taka trasa spacerowa, która przechodzi przez każdy most dokładnie raz, żadnego nie omija, i pozwala wrócić do punktu wyjścia.
Nie potrafili sami rozwiązać tego problemu, więc napisali do znanego już wtedy matematyka Leonharda Eulera. Euler pokazał, że nie istnieje rozwiązanie tego zadania. (Jeśli wejdzie się po raz trzeci na wyspę, nie ma jak z niej wyjść.) Można tę sytuację przedstawić jako graf o wielokrotnych krawędziach:
mostykrolewieckie
Euler wykazał, że jest to niemożliwe, a decyduje o tym nieparzysta liczba wylotów mostów zarówno na każdą z wysp, jak i na oba brzegi rzeki. Szukając rozwiązania rozważył problem ogólniejszy, starając się ustalić warunki, które muszą być spełnione, żeby dany graf spójny można było opisać linią ciągłą w taki sposób, żeby każda jego krawędź grafu była odwiedziona dokładnie raz (patrz graf eulerowski). Euler pokazał, że jest to możliwe wtedy i tylko wtedy, gdy liczba wierzchołków tego grafu, w których spotyka się nieparzysta liczba krawędzi, jest 0 lub 2, czyli trzeba w grafie znaleźć cykl lub drogę Eulera, czyli cykl lub drogę przechodzący przez wszystkie wierzchołki i wszystkie krawędzie tego grafu dokładnie raz.

Rodzaje grafów

Istnieje wiele rodzajów grafów, które mogą mieć wiele interesujących właściwości. Grafy mogą być, np.:

  • etykietowane – gdy wierzchołki przybierają pewne etykiety
  • ważone – gdy krawędzie posiadają pewne wartości (wagi)
  • skierowane – gdy możliwe jest przejście pomiędzy wierzchołkami tylko w jedną stronę (krawędź wtedy oznaczamy strzałką)
  • nieskierowane – gdy możliwe jest przejście pomiędzy wierzchołkami w obydwie strony
  • spójne – gdy istnieje ścieżka (droga) w grafie łącząca dowolne dwa wierzchołki.
  • niespójne – gdy takiej ścieżki (drogi) nie można wyznaczyć dla dowolnych dwóch wierzchołków.
  • eulerowskie – gdy możliwe jest skonstruowanie w nim cyklu Eulera, czyli drogi, która przechodzi przez każdą jego krawędź dokładnie raz i wraca do punktu wyjściowego:
    grafeulera
  • hamiltonowskie – gdy zawiera ścieżkę Hamiltona, czyli drogę, która przechodzi przez każdy jego wierzchołek dokładnie jeden raz, np. każdy graf pełny (o min. 3 wierzchołkach) jest grafem hamiltonowskim:
    grafhamiltonowski
  • regularne – czyli posiadające wszystkie wierzchołki tego samego stopnia, czyli z każdego wierzchołka grafu regularnego wychodzi dokładanie taka sama ilość krawędzi:
    grafyregularne
  • pełne (kliki) – gdy każde dwa wierzchołki w grafie są połączone ze sobą krawędzią:
    grafypelnekliki
  • dwudzielne – czyli takie, w których zbiór wierzchołków można podzielić na dwa rozłączne zbiory tak, że krawędzie nie łączą wierzchołków tego samego zbioru (Jeśli pomiędzy wszystkimi parami wierzchołków należących do różnych zbiorów istnieje krawędź, wtedy graf taki nazywamy pełnym grafem dwudzielnym lub kliką dwudzielną i oznaczamy Kn,m, gdzie n i m oznaczają liczności zbiorów wierzchołków), np. K3,3:
    grafk3.3
  • izomorficzne – gdy istnieje bijekcja (tj. relacja przyporządkowująca każdemu elementowi dziedziny dokładnie jeden element obrazu) zbioru wierzchołków jednego grafu na zbiór wierzchołków drugiego grafu, która zachowuje strukturę grafu (tj. krawędzie) – tzn. izomorficzne grafy są w zasadzie tym samym grafem (pod względem struktury) z tym, że wierzchołki poddane są jakiejś permutacji.
    grafyizomorficzne
  • homeomorficzne – gdy jeden graf z drugiego można otrzymać zastępując wybrane krawędzie prostymi łańcuchami krawędzi i wierzchołków lub zastępując łańcuchy krawędzi i wierzchołków pojedynczymi krawędziami:
    grafyhomeomorficzne
  • planarne – taki, który można narysować na płaszczyźnie tak, by krzywe obrazujące krawędzie grafu nie przecinały się ze sobą. Kryterium Kuratowskiego mówi, że graf skończony jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu homeomorficznego z grafem K5 ani z grafem K3,3:
    grafk5

 

Grafy w informatyce

Graf w informatyce jest najbardziej skomplikowaną podstawową strukturą danych. Stosy, kolejki, listy i drzewa można traktować jako szczególne przypadki grafu lub grafy uproszczone.
Grafy dostarczają nam potężne możliwości tworzenia różnego rodzaju relacji pomiędzy danymi, które można wiązać na wiele różnych sposobów, reprezentując lub modelując złożone zależności z otaczającego nas świata.
Grafy możemy zaimplementować w postaci tablicy określającej rodzaj połączenia oraz jego etykietę lub dynamicznie korzystając ze wskaźników.

 

 

Grafy i macierze 

Na początek kilka definicji:
W informatyce grafem nazywamy strukturę G=(V, E) składającą się z węzłów (wierzchołków, oznaczanych przez V) wzajemnie połączonych za pomocą krawędzi (oznaczonych przez E).
Grafy dzielimy na grafy skierowane i nieskierowane:

Graf nieskierowany Graf skierowany
Rys.1. Graf nieskierowany Rys.2. Graf skierowany

Jeśli krawędź łączy dwa wierzchołki to jest z nimi incydentna.
Pętla własna to krawędź łączące wierzchołek z samym sobą.
Stopień wierzchołka w grafie nieskierowanym to liczba incydentnych z nim krawędzi.
Istnieje kilka algorytmów do przechowania grafu w pamięci.
Omówmy najpierw macierz sąsiedztwa.
Budujemy tablicę o rozmiarach V*V, gdzie V-liczba wierzchołków. Następnie wypełniamy ją zerami- jeśli dwa wierzchołki nie są połączone krawędzią i jedynkami- jeśli dwa wierzchołki są połączone. Oto macierz sąsiedztwa dla grafu z rysunku 1:

1 2 3 4 5
1 0 1 1 0 1
2 1 0 1 1 1
3 1 1 0 1 0
4 0 1 1 0 1
5 1 1 0 1 0

Złożoność pamięciowa: O(V2)

Widać, że macierz jest symetryczna. Stosując tablicę dynamiczną można więc zmniejszyć rozmiar macierzy do połowy zapisując ją jako macierz dolno-(górno)-trójkątną.
Lista incydencji.
Należy utworzyć listę dla każdego wierzchołka v, w której przechowujemy zbiór wierzchołków połączonych krawędzią z v. Lista dla grafu z rysunku 1 wygląda następująco:

1: 2, 3, 5
2: 1, 3, 4
3: 1, 2, 4
4: 2, 3, 5
5: 4, 1    Złożoność pamięciowa: O(V+E)

Lista krawędzi jest to lista, na której przechowujemy wszystkie krawędzie występujące w grafie.
Przykład dla grafu skierowanego z rys.2:

  • 1 – 2
  • 2 – 4
  • 2 – 5
  • 3 – 1
  • 3 – 2
  • 4 – 3
  • 5 – 1
  • 5 – 4

Zapisując przy pomocy tej reprezentacji graf, w którym występują krawędzie skierowane i nieskierowane należy w przypadku krawędzi nieskierowanej z u do v zapisać krawędź dwukrotnie: u – v oraz v – u.

Złożoność pamięciowa: O(E)

Macierz incydencji to tablica o rozmiarach V*E. Składa się ona z E kolumn i V wierszy, jeśli krawędź wychodzi z danego wierzchołka to piszemy w odpowiedniej kolumnie (-1), jeśli do niego wchodzi piszemy (+1), jeśli wierzchołek nie należy do krawędzi piszemy 0, jeśli jest to pętla własna piszemy 2.
Oto przykład dla grafu z rys. 2.

1 2 3 4 5
1 – 2 -1 1 0 0 0
1 – 3 1 0 -1 0 0
1 – 5 1 0 0 0 -1
2 – 4 0 -1 0 1 0
2 – 5 0 -1 0 0 1
2 – 3 0 1 -1 0 0
3 – 4 0 0 1 -1 0
5 – 1 1 0 0 0 -1
5 – 4 0 0 0 1 -1

Złożoność pamięciowa: O(E*V)

Macierz grafu została opracowana w Instytucie Informatyki PP przez dr M. Sternę. Jest to trochę bardziej skomplikowana reprezentacja grafu niż poprzednie.
Należy utworzyć tablicę o rozmiarach (V+2)2. Wiersze i kolumny numerujemy od 0 do V+1. Najpierw zajmiemy się częścią macierzy ograniczoną przez indeksy od 1 do V.Zał. że w wierszach mamy i-te wierzchołki a w kolumnach j-te wierzchołki. Liczby, które mogą znaleźć się na skrzyżowaniu wierzchołka i oraz j można podzielić na 3 grupy:

  • od 1 do V – istnieje krawędź skierowana: i <- j
  • od V+1 do 2*V – istnieje krawędź skierowana: i -> j
  • od (-V) do (-1) – brak incydentnych krawędzi

Cały sekret macierzy grafu polega jednak na tym, że odczytana wartość nie tylko informuje nas, czy istnieje krawędź łącząca wierzchołki i oraz j, ale zawiera też adres następnego wierzchołka, który jest w takiej samej relacji z wierzchołkiem i co wierzchołek j.
Podam teraz kilka przykładów dla grafu z rys. 2. Liczba wierzchołków jest równa 5. Prześledzimy sytuację dla wierzchołka 1. w grafie mamy następujące krawędzie zawierające ten wierzchołek:

  • 1 -> 2
  • 1 <- 3
  • 1 <- 5

Weźmy pierwszą krawędź: wierzchołek 2 jest jedynym następnikiem wierzchołka 1, więc w macierzy w komórce [1,2] musimy podać adres wierzchołka 2. Aby obliczyć adres wierzchołka nr. 2 (mamy do czynienia z następnikiem) wystarczy dodać do niego liczbę wierzchołków w grafie: 2+5=7. Taką liczbę zapisujemy w komórce [1,2].
Przejdźmy do krawędzi drugiej: wierzchołek 3 jest poprzednikiem wierzchołka 1, ale (w przeciwieństwie do następników) nie jedynym: także wierzchołek 5 jest poprzednikiem wierzchołka 1 (ostatnia krawędź na naszej liście). W komórce [1,3] musimy więc podać adres wierzchołka 5. Ponieważ jest to poprzednik, więc adresem wierzchołka 5 jest 5.
Przechodzimy do ostatniej krawędzi: wierzchołek 5 jest poprzednikiem wierzchołka, ponieważ jest jego ostatnim poprzednikiem (pierwszym był wierzchołek 3) w komórce [1,5] podajemy adres wierzchołka 5, czyli znów wpisujemy 5.
W naszej macierzy musimy podać także wierzchołki, które nie są połączone z wierzchołkiem 1 krawędzią. Punktem wyjściowym listy tych wierzchołków dla każdego wierzchołka i jest on sam (stąd: macierz grafu nie nadaje się dla grafów z pętlami własnymi), lista ta zaczyna się więc w komórce [i,i]. A więc wiemy, że wierzchołek 1 nie jest połączony krawędzią ze sobą samym oraz wierzchołkiem 4. W komórce [1,1] musimy podać adres wierzchołka 4, z godnie z tyum co napisałem powyżej, adresy wierzchołków, które nie są połączone z danym wierzchołek podaje się poprzedzając numer wierzchołka znakiem „-„. Więc w komórce [1,1] piszemy (-4). Jednocześnie wierzchołek 4 jest ostatnim wierzchołkiem, z którym nie łączy się wierzchołek 1, więc w komórce [1,4] podajemy znów adres wierzchołka 4, czyli [1,4]=(-4).
Teraz zajmiemy się pozostałą częścią macierzy: kolumną nr. 0 i (V+1) oraz wierszem nr. 0 i (V+1). Bez nich można by już zapisać graf za pomocą macierzy, lecz dzięki nim będziemy mieli dostęp do listy poprzedników i następników w czasie O(E). A więc: komórka [i,0] zawiera pierwszy poprzednik wierzchołka i-tego natomiast komórka [0,i] ostatni poprzednik.
W przykładzie (dotyczącym wierzchołka 1) zapiszemy [1,0]=3, [0,1]=5, ponieważ pierwszym poprzednikiem wierzchołka 1 jest 3 a ostatnim poprzednikiem tego wierzchołka jest 5. Podobnie jest z następnikami: [i,V+1] rozpoczyna listę następników wierzchołka i-tego a [V+1,i] kończy, a więc [1,6]=2, [6,1]=2, gdyż pierwszym i ostatnim następnikiem wierzchołka 1 jest 2. W ten sposób wypełniliśmy pierwszy wiersz macierzy grafu.
Dodam jeszcze, że jeżeli jakiś wierzchołek nie ma następników lub poprzedników to na początku i końcu listy odpowiednio: następników lub poprzedników wpisujemy 0. Poniżej zamieszczam całą macierz dla grafu z rys. 2 (w kolumnach znajdują się wierzchołki j, w wierszach wierzchołki i).

0 1 2 3 4 5 6
0 X 5 3 4 5 2 X
1 3 -4 7 5 -4 5 2
2 1 3 -2 3 10 10 4
3 4 7 7 -5 4 -5 1
4 2 -1 5 8 -1 5 3
5 2 9 2 -3 9 -3 1
6 X 2 5 2 3 4 X

Dla lepszego zrozumienia macierzy grafu proponuję narysować graf na podstawie macierzy i sprawdzić, czy jest to graf z rys. 2.

Dzięki dodatkowym kolumnom i wierszom zyskujemy listy następników i poprzedników:

  • w kolumnie 0: wskaźnik do pierwszego elementu na liście poprzedników
  • w wierszu 0: wskaźnik do ostatniego elementu na liście poprzedników
  • w kolumnie V+1: wskaźnik do pierwszego elementu na liście następników
  • w wierszu V+1: wskaźnik do ostatniego elementu na liście następników
  • na głównej przekątnej: wskaźnik do pierwszego elementu na liście elementów nie będących ani następnikami ani poprzednikam

Literatura:

GRAFY I SIECI Autor: Wojciechowski Jacek, Pieńkosz Krzysztof
14570501061240359.jpg

 

Wprowadzenie do teorii grafów; Autor: Wilson Robin J.

105530733o


Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj /  Zmień )

Zdjęcie na Google

Komentujesz korzystając z konta Google. Wyloguj /  Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj /  Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj /  Zmień )

Połączenie z %s