Graf (matematyka)

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

Graf to – w uproszczeniu – zbiór wierzchołków, które mogą być połączone krawędziami, w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków (ilustracja po prawej stronie). Grafy to podstawowy obiekt rozważań teorii grafów. Za pierwszego teoretyka i badacza grafów uważa się Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich.

Wierzchołki grafu zwykle są numerowane i czasem stanowią reprezentację jakichś obiektów, natomiast krawędzie mogą wówczas obrazować relacje między takimi obiektami. Krawędzie mogą mieć wyznaczony kierunek, a graf zawierający takie krawędzie jest grafem skierowanym. Krawędź może posiadać także wagę, to znaczy przypisaną liczbę, która określa na przykład odległość między wierzchołkami (jeśli na przykład graf jest reprezentacją połączeń między miastami). W grafie skierowanym wagi mogą być zależne od kierunku przechodzenia przez krawędź (np. jeśli graf reprezentuje trud poruszania się po jakimś terenie, to droga pod górkę będzie miała przypisaną większą wagę niż z górki).

Definicje

Różni autorzy stosują bardzo odmienne sposoby definiowania i oznaczania elementów grafu.

Graf

Graf nieskierowany

Graf, graf prosty lub graf nieskierowany to uporządkowana para G := (V,E) gdzie:

• V jest niepustym zbiorem. Elementy tego zbioru nazywamy wierzchołkami,
• E jest rodziną dwuelementowych podzbiorów zbioru wierzchołków V, zwanych krawędziami: $E\subseteq \{ \{u,v\} : u,v \in V,u \neq v\}$.

Wierzchołki należące do krawędzi nazywane są jej końcami. Zazwyczaj V (i co za tym idzie E) są określane jako zbiory skończone. Jednak powyższa definicja tego nie wymaga i w praktyce rozważa się też czasami grafy o nieskończonej liczbie wierzchołków (wtedy liczba krawędzi może być skończona, lub nieskończona).

Graf skierowany

Graf skierowany

Graf skierowany lub inaczej digraf to uporządkowana para G := (V,A) gdzie:

• V jest zbiorem wierzchołków,
• A jest zbiorem uporządkowanych par różnych wierzchołków ze zbioru V, zwanych krawędziami skierowanymi, lub łukami: $A \subseteq V \times V$.

Przyjmuje się, że krawędź e:=(x,y) jest skierowana z x do y, czyli wychodzi z x, a wchodzi do y.

Graf mieszany

Graf mieszany to uporządkowana trójka G:=(V,E,A) gdzie zbiory V,E,A są zdefiniowane jak wyżej, czyli może zawierać jednocześnie krawędzie skierowane i nieskierowane.

Warianty definicji

W wielu zastosowaniach tak zdefiniowane grafy nie są wystarczające i wprowadza się pewne modyfikacje.

Na przykład aby wprowadzić pętlę czyli krawędź, której oba końce są tym samym wierzchołkiem, w definicji grafu nieskierowanego należy dopuścić zbiory jednoelementowe {v} albo użyć dwuelementowego multizbioru {v,v}. W grafie skierowanym pętla jest naturalnie reprezentowana przez parę (v,v).

Czasami potrzebna jest możliwość połączenia dwóch wierzchołków przy pomocy więcej niż jednej krawędzi (w przypadku grafu skierowanego chodzi o łuki o takim samym zwrocie). Graf, który na to pozwala, nazywany jest multigrafem. Uzyskuje się go np. przez zdefiniowanie E, lub A jako multizbioru.

Przez zdefiniowanie funkcji z V, E, lub A w pewien zbiór X, można przypisać krawędziom lub wierzchołkom etykiety, służące do przechowywania dodatkowych informacji. Etykiety liczbowe są często nazywane wagami. Dla grafów z wagami zbiór tworzący graf jest rozszerzony o funkcję $\! \delta: E \to K$ taką, że dla każdej krawędzi $\! e \in E$, $\! \delta (e)$ jest wagą danej krawędzi

Przykłady odmiennych sposobów definiowania grafu:

• Graf może być też określony jako niepusty zbiór wierzchołków i dana na nim relacja binarna $\! R$ taka, że dla dowolnych wierzchołków $\! v$ i $\! u$ $\!vRu$ zachodzi wtedy i tylko wtedy, gdy istnieje krawędź łącząca $\! v$ i $\! u$. Dla grafów nieskierowanych relacja ta jest symetryczna (zob. też "macierz sąsiedztwa" poniżej).

• Graf nieskierowany można też definiować jako trójkę $\! G=(V,E,\gamma)$, gdzie

• $\! V$ jest zbiorem wierzchołków
• $\! E$ zbiorem krawędzi
• $\! \gamma$ funkcją ze zbioru krawędzi w rodzinę jednoelementowych lub dwuelementowych podzbiorów zbioru wierzchołków – $\! \gamma : E \to (\{\{v,u\}:v,u \in V\}\cup \{\{w\}:w \in V\})$. Wówczas jeżeli $\! e$ jest krawędzią grafu to:

• kończy się ona wierzchołkami $\! u,v\in V$, gdy $\! \gamma(e)=\{u,v\}$
• jest ona pętlą wierzchołka $\! v$, gdy $\! \gamma(e)=\{v\}$

• Graf skierowany określa się też jako trójkę $\! G=(V,E,\gamma)$, gdzie zbiory $\! V$ i $\! E$ są zdefiniowane analogicznie do grafów nieskierowanych a $\! \gamma$ jest funkcją ze zbioru krawędzi w zbiór uporządkowanych par (kwadrat kartezjański, czyli iloczyn kartezjański zbioru ze sobą) wierzchołków – $\! \gamma : E \to V\times V$. Wówczas, jeżeli $\! e$ jest krawędzią grafu $\! G$ to istnieją takie wierzchołki $\! u,v\in V$, że $\! \gamma(e)=(u,v)$. W takim przypadku krawędź $\! e$ biegnie z $\! u$ do $\! v$.

Graf geometryczny

Dla każdego grafu istnieje nieskończenie wiele przedstawiających go rysunków, czasami jednak rozważane są w przypadku grafów własności stricte geometryczne (współrzędne geometryczne wierzchołków, tylko proste krawędzie, "zmieszczenie się" w pewnej przestrzeni itp.). Grafy rozpatrywane jako figury w przestrzeni (w której są one "zanurzone" i która nadaje im cechy charakterystyczne dla danej przestrzeni) nazywa się grafami geometrycznymi.

Pojęcia służące do opisu grafów

Alfabetyczna lista definicji

Wszystkie drogi w tym grafie są proste, nie ma cykli.

• Acentryczność wierzchołka grafu

To maksymalna odległości wierzchołka do innych wierzchołków grafu, lub inaczej długość najdłuższej ścieżki prostej zaczynającej się w danym wierzchołku.

• Cykl

Zamknięta droga prosta $e_a,e_b,\ldots ,e_z$, taka, że krawędź $e_z$ kończy się w początkowym wierzchołku drogi

• Droga

Wyznaczona przez krawędzie trasa polegająca na podróżowaniu od wierzchołka do wierzchołka po łączących je krawędziach. Jeżeli przez $e_i$ oznaczy się i-tą krawędź grafu, to droga może być jednoznacznie zapisana jako $e_a,e_b,\ldots,e_z$

• Droga prosta

Droga nie zawierająca dwóch tych samych krawędzi

• Długość drogi/ścieżki

To liczba krawędzi/wierzchołków tworzących daną drogę/ścieżkę

• Droga acykliczna

Droga nie zawierająca cyklu

• Gęstość grafu

Stosunek liczby krawędzi do największej możliwej liczby krawędzi: $\frac{2|E|}{|V|\,(|V|-1)}$.

Używa się również określeń: graf gęsty, jeżeli ma on dużo krawędzi w stosunku do liczby wierzchołków i podobnie graf rzadki, jeżeli ma on mało krawędzi w stosunku do liczby wierzchołków. Przy czym znaczenie słów mało i dużo może zależeć od kontekstu.

• Klika

Podzbiór wierzchołków danego grafu wraz z krawędziami je łączącymi takich, że każde dwa wierzchołki tego podzbioru są sąsiadami (czyli podgraf pełny).

• Kolorowanie grafu

To nadanie każdemu wierzchołkowi koloru, tak by żadne sąsiadujące ze sobą wierzchołki nie były pokolorowane tym samym kolorem.

• Krawędzie sąsiednie

Krawędzie kończące się w jednym wierzchołku. W przypadku grafów skierowanych zazwyczaj wymagana jest "zgodność kierunków" krawędzi, tj. dwie krawędzie są sąsiednie, jeżeli odpowiednio kończą się i zaczynają w tym samym wierzchołku.

• Krawędź/wierzchołek krytyczny

Krawędź/wierzchołek, po usunięciu której/którego ze zbioru pokrywającego zmniejsza się indeks pokrycia krawędziowego/wierzchołkowego.

• Liczba chromatyczna

Najmniejsza liczba kolorów potrzebna do prawidłowego pokolorowania grafu.

• Nadgraf grafu H

Taki graf, że H jest jego podgrafem.

Pętla

• Pętla

Krawędź zaczynająca i kończąca się w tym samym wierzchołku

• Podgraf grafu H

Graf G uzyskany poprzez usunięcie części wierzchołków z H, wraz z kończącymi się w nich krawędziami

• Graf r-regularny:

Graf, w którym każdy wierzchołek grafu jest stopnia r.

• Sąsiad:

Dwa wierzchołki są sąsiadami, jeśli istnieje krawędź pomiędzy nimi.

• Spójna składowa grafu G

Spójna składowa grafu to możliwie największy spójny podgraf grafu G. Graf spójny ma jedną spójną składową.

• Stopień wierzchołka v

Liczba kończących się w nim krawędzi. Oznaczenie: deg(v). W przypadku grafów skierowanych mówi się o stopniach wejściowym i wyjściowym – degIn(v), degOut(v)

• Ściana

Obszar zamknięty wyznaczony przez krawędzie grafu (tzw. krawędzie tworzące ścianę). Z pojęciem ściany ściśle powiązane jest twierdzenie Eulera.

Uwaga! Za ścianę uważa się też nieskończony obszar znajdujący się "na zewnątrz" grafu (a więc każdy graf ma co najmniej jedną ścianę)!

• Ściany sąsiadujące

Ściany są sąsiadujące, jeżeli mają co najmniej jedną wspólną krawędź tworzącą.

• Ścieżka

Intuicyjnie jest bardzo podobna do drogi, z tym, że jest wyznaczona przez wierzchołki, tj. można ją opisać poprzez ciąg wierzchołków $v_a,v_b,\ldots ,v_z$

• Ścieżka prosta

Ścieżka wyznaczona tak, by żaden wierzchołek na trasie nie powtarzał się

• Ścieżka zamknięta

Ścieżka $v_a,v_b,\ldots ,v_z,v_a$, czyli kończąca się w początkowym wierzchołku

• Usunięcie wierzchołka

Przez usunięcie wierzchołka rozumie się wymazanie go, oraz wszystkich kończących się w nim krawędzi z danego grafu

• Waga krawędzi

Często od grafu reprezentującego np. sieć połączeń komunikacyjnych oczekuje się nie tylko informacji o istniejącym połączeniu (krawędzi lub ścieżki), ale też o np. długości połączenia. Wprowadza się wtedy wagi, wartość przypisaną każdej krawędzi. Graf taki można wykorzystać np. do wyznaczenie optymalnej, w sensie przejechanych kilometrów trasy, lub, ogólniej rozwiązanie problemu komiwojażera, wyznaczenia optymalnego rozłożenia kabli w sieci, koordynowania wysyłania plików metodą peer to peer itp.

• Wierzchołek izolowany

Wierzchołek o stopniu 0, czyli nie będący końcem żadnej krawędzi.

• Wierzchołek pokrywający krawędź

Wierzchołek v pokrywa krawędź e, jeżeli e kończy się w v. W analogiczny sposób definiuje się krawędź pokrywającą dany wierzchołek – krawędź e kryje wierzchołek v, gdy się w nim kończy.

• Minimalny pokrywający podzbiór krawędzi/wierzchołków

To możliwie najmniejszy podzbiór krawędzi/wierzchołków grafu, taki, że pokrywają one wszystkie wierzchołki/krawędzie danego grafu.

Liczność minimalnego zbioru pokrywającego krawędzi/wierzchołków nazywa się indeksem pokrycia wierzchołkowego/krawędziowego. Wszystkie podzbiory o tej liczności i własności nazywa się pokryciem minimalnym.

• Wierzchołek rozspajający

Wierzchołek, po usunięciu którego zwiększa się liczba spójnych składowych grafu. Nazywany przegubem tworzy "wąskie gardło" grafu – tj. istnieją w grafie dwa wierzchołki takie, że każda łącząca je droga musi przejść przez wierzchołek rozspajający.

• Most

Krawędziowy "odpowiednik" wierzchołka rozspajającego – krawędź, po usunięciu której wzrasta liczba spójnych składowych grafu.

Oznaczenia formalne

Często dla danego grafu G stosuje się skrócone oznaczenia oparte na alfabecie greckim oraz łacińskim:

$n\ =\ |V(G)|$ liczba wierzchołków G

$m\ =\ |E(G)|$ liczba krawędzi G

$\! \delta (G)$ najmniejszy stopień wierzchołka w G

$\! \Delta (G)$ największy stopień wierzchołka w G

$\! \chi (G)$ liczba chromatyczna G

$\! \chi' (G)$ indeks chromatyczny G

$\! \omega (G)$ liczba spójnych składowych G

Przykład dla konkretnego grafu

Graf nieskierowany

To przykład grafu nieskierowanego G wraz z jego ilustracją:

$\! V(G) = \{ v_1, v_2, v_3, v_4, v_5, v_6 \}$

$\! E(G) = \{ \{v_1, v_2\}, \{v_1, v_5\}, \{v_5, v_4\}, \{v_4, v_6\}$,

$\!\{v_4, v_3\}, \{v_3, v_2\}, \{v_2, v_5\} \}$

Jego własności:

• Przykładową ścieżką prostą może być $\! v_6,v_4,v_5,v_1$ a cyklem $\! v_5,v_4,v_3,v_2,v_5$
• Stopnie wierzchołków:

$\! deg(v_1)\ =\ 2$

$\! deg(v_2)\ =\ 3$

$\! deg(v_3)\ =\ 2$

$\! deg(v_4)\ =\ 3$

$\! deg(v_5)\ =\ 3$

$\! deg(v_6)\ =\ 1$

• Krawędź $\! \{v_1,v_5\}$ jest sąsiednia z $\! \{v_5,v_2\}$, ale nie jest z $\! \{v_2,v_3\}$
• Graf G ma trzy ściany – zewnętrzną oraz dwie wyznaczone odpowiednio przez ścieżki np. $\! v_2,v_3,v_4,v_5$ i $\! v_1,v_5,v_2$
• Graf G jest spójny, czyli ma jedną spójną składową. Natomiast podgraf grafu G, składający się z wierzchołków $\! v_1,v_2,v_5,v_6$ i incydentnych z nimi krawędziami, ma dwie spójne składowe – cykl $\! v_1,v_2,v_5,v_1$ i wierzchołek izolowany $v_6$.

Izomorfizm i homeomorfizm grafów

Graficzna reprezentacja grafów (w postaci kropek i łączących je krzywych) jest tylko sposobem przedstawienia relacji zachodzącej między wierzchołkami. Dla każdego grafu istnieje nieskończenie wiele przedstawiających go jednoznacznie wykresów, rysunków. Co więcej, właściwości grafów (takie jak większość podanych w następnej sekcji) są niezależne od sposobu numerowania wierzchołków, kolejności ich rysowania itp. Grafy różniące się tylko sposobem ich przedstawienia, lub indeksami nadanymi wierzchołkom, nazywamy izomorficznymi.

Dwa grafy są homeomorficzne, jeśli z jednego grafu można otrzymać drugi zastępując wybrane krawędzie łańcuchami prostymi lub łańcuchy proste pojedynczymi krawędziami. Mówiąc obrazowo, chodzi o dorysowywanie na krawędziach dowolnej liczby wierzchołków, bądź wymazywanie ich.

Klasy grafów

Grafy można podzielić ze względu na różne własności, zazwyczaj zachowane w obrębie izomorfizmów danego grafu. Najczęściej dotyczą one tylko grafów prostych (nie zawierających pętli i krawędzi wielokrotnych), część z tych własności można rozszerzyć na multigrafy. Najczęściej spotykane klasy grafów to:

• graf prosty (właściwy)

Graf nie zawierający pętli ani krawędzi wielokrotnych. Graf nieprosty nazywany jest multigrafem. Z reguły zdanie G jest grafem oznacza w domyśle, że G jest grafem prostym

• graf pełny

Graf, którego każdy wierzchołek jest połączony bezpośrednio krawędzią z każdym innym. Graf pełny o n wierzchołkach oznacza się $\! K_n$.

• graf regularny stopnia k

Graf, którego każdy wierzchołek jest stopnia k

• graf kubiczny

Specjalne określenie dla grafów regularnych stopnia 3

• graf acykliczny

Graf nie zawierający żadnej drogi zamkniętej

• graf spójny

Graf, w którym dla każdego wierzchołka istnieje droga do każdego innego wierzchołka

• graf k-spójny

Graf posiadający k spójnych składowych

• drzewo

Spójny graf acykliczny

• las

Graf, którego wszystkie spójne składowe są drzewami

• graf dwudzielny

Graf, którego wierzchołki mogą być podzielone na dwa zbiory, tak by w obrębie jednego zbioru żaden wierzchołek nie był połączony z innym

• graf dwudzielny pełny

Graf dwudzielny taki, że każdy wierzchołek z jednego zbioru jest połączony krawędzią z każdym wierzchołkam ze zbioru drugiego. Pełny graf dwudzielny o $\! n_1\ + n_2$ wierzchołkach oznacza się $\! K_{n_1,n_2}$

• graf k-dzielny

To naturalne rozszerzenie klasy grafów dwudzielnych – jest to graf, którego zbiór wierzchołków można podzielić na k parami rozłącznych podzbiorów takich, że żadne dwa węzły należące do tego samego zbioru nie są połączone krawędzią

• pełny graf k-dzielny

Jeżeli zbiór wierzchołków dzieli się na k nie połączonych między sobą podzbiorów wierzchołków, to jeżeli dla każdego wierzchołka $\! v_i$ z $\! j$-tego przedziału $\! v_i$ jest połączony z każdym wierzchołkiem z każdego z przedziałów poza j, to jest to pełny graf k-dzielny

• graf eulerowski

Graf posiadający drogę prostą przechodzą przez każdą krawędź.

• graf hamiltonowski

Graf posiadający ścieżkę prostą przechodzą przez każdy wierzchołek.

• graf planarny

Graf, dla którego istnieje graf izomorficzny, który można przedstawić na płaszczyźnie tak, by żadne krawędzie się nie przecinały (oczywiście, nie w sensie "spotkania się" w jednym wierzchołku).

Kazimierz Kuratowski udowodnił, że grafy pełne $K_5$ i $K_{3,3}$ są nieplanarne, oraz że każdy inny graf nieplanarny musi posiadać podgraf homeomorficzny z którymś z tych grafów.

• graf płaski

To izomorficzne przedstawienie grafu takie, że żadne dwie krawędzie się nie przecinają

• graf platoński

Graf, którego przedstawienie tworzy siatkę wielościanu foremnego

• graf komórkowy

Graf płaski, którego wszystkie ściany są utworzone przez drogi zamknięte tej samej długości

• graf krytyczny

Graf, którego każdy wierzchołek/krawędź jest krytyczny/krytyczna

• graf symetryczny

Graf skierowany taki, że jeżeli istnieje krawędź $\! (u,v)$ to istnieje też krawędź $\! (v,u)$. Graf asymetryczny ma własność: jeżeli istnieje krawędź $\! (u,v)$ to nie istnieje krawędź $\! (v,u)$

• graf podstawowy grafu skierowanego

To niemal ten sam, ale nieskierowany, bo bez zwrotów na krawędziach

• turniej

To graf pełny, w którym zorientowano krawędzie, lub inaczej, graf skierowany którego graf podstawowy jest grafem pełnym

Operacje na grafach

Operacje binarne

Suma grafów

Definicja: $G_1 \cup G_2\ =\ (V_1 \cup V_2,E_1 \cup E_2)$

Jeżeli dane są dwa grafy $\! G_1=(V_1,E_1)$ oraz $\! G_2=(V_2,E_2)$, to ich sumą jest graf, którego zbiór wierzchołków i krawędzi tworzą wszystkie wierzchołki i krawędzie tych grafów.

Przecięcie grafów

Definicja: $G_1 \cap G_2\ =\ (V_1 \cap V_2,E_1 \cap E_2)$

Jest definowane analogicznie do sumy. Jeżeli dane są dwa grafy $\! G_1=(V_1,E_1)$ i $\! G_2=(V_2,E_2)$, to ich przecięciem jest graf, którego wierzchołki i krawędzie wchodzą w skład obu tych grafów.

Zespolenie grafów

Definicja: $\! G_1 + G_2 = (V_1 \cup V_2,E_1 \cup E_2 \cup \{\{v_1,v_2\}:v_1 \in V_1,v_2 \in V_2\})$

Zespoleniem grafów $\! G_1=(V_1,E_1)$ i $\! G_2=(V_2,E_2)$ nazywamy graf w którym z każdego wierzchołka $\! G_1$ poprowadzono krawędzie do każdego wierzchołka $\! G_2$.

Operacje unarne

• graf krawędziowy grafu prostego G

Graf który dla każdej krawędzi z G ma wierzchołek połączony z wierzchołkami reprezentującymi pozostałe krawędzie sąsiadujące ze sobą w G.

Etapy konstrukcji grafu krawędziowego:

• 

  G-1

• 

  G-2

• 

  G-3

• 

  G-4

• dopełnienie grafu

Dopełnieniem grafu $\! G$ nazywamy graf $\! \overline{G}$ w którym dwa wierzchołki są sąsiednie wtedy i tylko wtedy, gdy nie były sąsiednie w $\! G$. Inaczej mówiąc w dopełnieniu dwa wierzchołki są połączone krawędzią wtedy, gdy nie były połączone w grafie wyjściowym.

Grafy dualne

• graf dualny grafu G

Graf, którego wierzchołki odpowiadają ścianom w G. Wierzchołki te są połączone, jeżeli odpowiednie ściany w G są sąsiednie.

Dopisek: rysunek tłumaczy doskonale jak zrobić graf dualny do grafu planarnego, dla grafu nieplanarnego musimy znaleźć dwuwymiarową przestrzeń (osadzoną w wielowymiarze) w której ten graf jest "planarny" – na przykład K5 nie można bez przecięć narysować na kuli, ale da się na torusie i tam możemy znaleźć jego graf dualny

• domknięcie przechodnie grafu G

Graf posiadający te same wierzchołki co G; dowolne dwa wierzchołki są w nim połączone wtedy i tylko wtedy, gdy w G istnieje między nimi droga.

Sposoby reprezentacji grafów

Każdy graf może być jednoznacznie reprezentowany na wiele sposobów. Dla człowieka w przypadku grafów o "rozsądnej" liczbie wierzchołków i krawędzi najwygodniejszy jest rysunek grafu. Pozostałe sposoby reprezentacji wykorzystywane są w komputerach. Każda z tych reprezentacji ma swoje wady i zalety, generalnie ograniczające są dwa warunki – ilość pamięci przeznaczonej na reprezentację i jej możliwości szybkiego odpowiadania na pytania typu czy między wierzchołkami v i u jest krawędź?. W przypadku grafów rzadkich listy sąsiedztwa okazują się wystarczająco szybkie by zrezygnować z pamięciożernych tablic.

Najwygodniejszy dla człowieka jest rysunek grafu, reprezentujący wierzchołki i łączące je krawędzie (rys. obok). Wierzchołki oznaczane są zazwyczaj kropkami lub kołami, niekiedy zawierającymi indeksy bądź inne dodatkowe informacje. Krawędzie reprezentowane są krzywymi bądź prostymi, w przypadku krawędzi ważonych, waga umieszczona jest bezpośrednio nad krawędzią.

Innymi najczęściej stosowanymi metodami reprezentacji grafów są macierze sąsiedztwa, listy sąsiedztwa i macierze incydencji. W przypadku implementacji algorytmów grafowych wybiera się tę metodę, za pomocą której dla danego problemu uzyska się program działający z mniejszą złożonością obliczeniową.

Macierz sąsiedztwa

Najprostszą ze struktur danych umożliwiających przedstawienie skomplikowanego grafu lub jego przechowywanie w pamięci komputera jest macierz sąsiedztwa, zawierająca dane na temat połączeń między wierzchołkami. Macierz jest rozmiaru $\! |V(G)|$ na $\! |V(G)|$, wyraz leżący z i-tego wiersza i j-tej kolumny zawiera wartość będącą liczbą krawędzi łączących i-ty i j-ty wierzchołek. Sposób ten pozwala na reprezentację zarówno grafów prostych, jak i grafów zawierających krawędzie wielokrotne oraz pętle własne. W przypadku grafów prostych wyrazami w macierzy będą wartości boole'owskie – jest krawędź, bądź nie ma krawędzi).

Graf odpowiadający tej macierzy

Macierz sąsiedztwa dla rozważanego wcześniej grafu nieskierowanego:

$A=\left[ \begin{matrix} 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{matrix}\right]$

Aby dowiedzieć się, ile krawędzi łączy wierzchołki $v_i\ i\ v_j$, wystarczy sprawdzić wartość komórki $\! A[i,j]$.

Tak zaimplementowana komputerowa struktura danych gwarantuje, że operacje sprawdzenia, czy $(v_i, v_j) \in E(G),$ dodania oraz usunięcia krawędzi odbywają się w stałym czasie. Do jej wad należy duża ilość potrzebnej pamięci – O(n²), oraz fakt, że czas potrzebny do przejrzenia zbioru krawędzi jest proporcjonalny do kwadratu liczby wierzchołków (złożoność obliczeniowa wynosi O(n²), zamiast do liczby krawędzi.

Lista sąsiedztwa

Drugą popularną reprezentacją grafu są tzw. listy sąsiedztwa – dla każdego wierzchołka zapamiętywana jest lista sąsiadujących z nim wierzchołków, np.:

$v_1\ \to \ v_2,v_5$

$v_2\ \to \ v_1,v_5,v_3$

$v_3\ \to \ v_2,v_4$

$v_4\ \to \ v_3,v_5,v_6$

$v_5\ \to \ v_1,v_2,v_4$

$v_6\ \to \ v_4$

W implementacji tej metody stosuje się listy jednokierunkowe oraz jednowymiarową tablicę wskaźników o rozmiarze $|V(G)|$, gdzie i-ty element tablicy jest wskaźnikiem do początku listy przechowującej sąsiadów i-tego wierzchołka.

W odróżnieniu od macierzy sąsiedztwa, lista sąsiedztwa wymaga ilości pamięci proporcjonalnej do liczby krawędzi, także przejrzenie całego zbioru krawędzi jest proporcjonalne do jego rozmiaru. W stosunku do macierzy sąsiedztwa większą złożoność mają jednak operacje elementarne – sprawdzenie, czy $\{v_i, v_j\} \in E(G)$ wymaga czasu proporcjonalnego do mniejszego ze stopni wierzchołków, a np. usunięcie krawędzi – do większego z nich.

Macierz incydencji

Macierz incydencji M wymiaru $\! |V(G)|$ na $\! |E(G)|$ zawiera informacje takie, że $M_{i,j}=1$ tylko, gdy j-ta krawędź kończy się w i-tym wierzchołku (czyli jest z nim incydentna). W przeciwnym wypadku $M_{i,j}=0$

Niech

$e_1\ =\ \{1,2\}$

$e_2\ =\ \{1,5\}$

$e_3\ =\ \{5,4\}$

$e_4\ =\ \{4,6\}$

$e_5\ =\ \{4,3\}$

$e_6\ =\ \{3,2\}$

$e_7\ =\ \{5,2\}$

oznaczają wszystkie krawędzie grafu z przykładu. Macierz incydencji o kolumnach $e_i$ i wierszach $v_i$ może wyglądać tak:

$M=\left[ \begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{matrix}\right]$

Zastosowania

Drzewo binarne

Kiedy rozwój informatyki pozwolił na reprezentowanie grafów za pomocą komputera, okazało się, że algorytmy na nich oparte znajdują wiele praktycznych zastosowań. Szczególny rodzaj grafów zwanych drzewami okazał się przydatny do reprezentacji hierarchii. Przedstawione na rysunku obok drzewo binarne może opisywać np. mistrzostwa sportowe czy drzewo genealogiczne, a po dodaniu etykiet może służyć np. do tworzenia kodów Huffmana, do opisu rozwoju populacji bakterii w laboratorium albo niedeterministycznego automatu skończonego.

Kiedy komputery stały się powszechne okazało się, że grafy można zastosować w wielu problemach. Jako graf przedstawiono sieć dróg. Skrzyżowania stały się wierzchołkami grafu, a ulice jego krawędziami. Potem w podobny sposób przedstawiono sieci pomieszczeń i korytarzy w budynkach. Taka reprezentacja pozwoliła komputerom na poszukiwanie najlepszej drogi ze swojego obecnego położenia do pożądanego celu. Oprogramowanie oparte na algorytmach analizujących grafy znalazło zastosowanie w przenośnych urządzeniach PDA wyposażonych w GPS, które potrafią wskazać kierowcy trasę w nieznanym mieście.

Innym przykładem wykorzystania grafów stały się gry komputerowe, gdzie system sztucznej inteligencji musiał odszukać najlepszą drogę dla postaci sterowanych przez program, która pozwoli zaatakować ludzkiego przeciwnika. Sztuczna inteligencja mogła rozwiązać to zagadnienie tylko dzięki odpowiedniej reprezentacji mapy wirtualnego otoczenia jako grafu.

Projektanci robotów mobilnych również skorzystali z podobnych algorytmów, aby ich maszyny mogły bez udziału człowieka odnaleźć trasę w trudnym terenie. Przedstawienie sieci komputerowych w postaci grafów pozwoliło na stworzenie oprogramowania usprawniającego trasowanie w Internecie.

Aby zwiększyć wydajność pracy w dużych organizacjach, realizację zlecanych przez klientów zadań przedstawiono w postaci grafów. Pracownikom odpowiadać mogą wierzchołki, a przepływ zadań między nimi opisać można za pomocą krawędzi. Zaprojektowano oprogramowanie pozwalające automatycznie śledzić pracę tak opisanej organizacji, co miało służyć wzrostowi wydajności. Rozwiązania tego typu znalazły zastosowanie w działach wsparcia technicznego klientów dużych korporacji.

Uogólnienia

W hipergrafach krawędź może łączyć więcej niż dwa wierzchołki.

Geometryczny graf nieskierowany może być traktowany jako kompleks symplicjalny złożony z 1-sympleksów (krawędzi) i 0-sympleksów (wierzchołków). Tym samym kompleksy symplicjalne są uogólnieniem grafów, gdyż pozwalają też na większą liczbę wymiarów.

W teorii modeli graf jest szczególnym przypadkiem struktury matematycznej. W tym przypadku jednak nie ma ograniczenia na liczbę krawędzi: może to być dowolna liczba kardynalna.

Bibliografia

• Kenneth A. Ross, Charles R.B. Wright: Matematyka dyskretna. z ang. przeł. E. Sepko-Guzicka, W. Guzicki, P. Zakrzewski. Warszawa: Wydaw. Naukowe PWN, 2005. ISBN 83-0114-380-0.  (pol.)
• Robin J. Wilson: Wprowadzenie do teorii grafów. z ang. tł. Wojciech Guzicki. Warszawa: Wydaw. Naukowe PWN, 1998. ISBN 83-0112-641-8.  (pol.)
• Witold Lipski, Tomasz Czajka: Kombinatoryka dla programistów. Warszawa: Wydawnictwa Naukowo-Techniczne, 2004. ISBN 83-204-2968-4.  (pol.)
• Juliusz Lech Kulikowski: Zarys teorii grafów : zastosowanie w technice. Warszawa: Państ. Wydaw. Naukowe, 1986. ISBN 83-0105-277-5.  (pol.)
• Marek Kubale: (red.) Optymalizacja dyskretna. Modele i metody kolorowania grafów. Wydawnictwa Naukowo-Techniczne, 2002. ISBN 83-204-2747-9.  (pol.)

Zobacz też

Niektórzy badacze właściwości grafów:

• Leonhard Euler
• Sir William Rowan Hamilton
• Kazimierz Kuratowski
• Gustav Kirchhoff

Linki zewnętrzne

• Reinhard Diestel: Graph Theory (ang.). [dostęp 24 października 2011]. – Książka dostępna w internecie na temat teorii grafów
• Chris K. Caldwell: Graph theory tutorial (ang.). [dostęp 24 stycznia 2009].
• Algorithms. Tutoring web page (ang.). [dostęp 24 stycznia 2009]. – Aplety obrazujące niektóre algorytmy teorii grafów
• Example graphs (ang.). [dostęp 24 stycznia 2009]. – Galeria grafów reprezentujących rzeczywiste problemy