Graf (matematyka)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
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


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


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ę[1] 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[edytuj | edytuj kod]

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

Graf[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Information icon.svg Osobny artykuł: 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Alfabetyczna lista definicji[edytuj | edytuj kod]

Wszystkie drogi w tym grafie są proste, nie ma cykli.
  • Acentryczność wierzchołka grafu
To maksymalna odległość 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.
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
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.
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).
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 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
Krawędź zaczynająca i kończąca się w tym samym wierzchołku
Graf G uzyskany poprzez usunięcie części wierzchołków z H, wraz z kończącymi się w nich krawędziami
  • Rozmiar grafu G
Rozmiarem grafu G nazywamy liczbę jego krawędzi, oznaczamy ||G||
  • Rząd grafu G
Rzędem grafu G nazywamy liczbę jego wierzchołków, oznaczamy |G|
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 to możliwie największy spójny podgraf grafu G. Graf spójny ma jedną spójną składową.
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)
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ą.
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
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 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, 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.
Krawędziowy "odpowiednik" wierzchołka rozspajającego – krawędź, po usunięciu której wzrasta liczba spójnych składowych grafu.

Oznaczenia formalne[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Information icon.svg Osobny artykuł: Izomorfizm 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.

Information icon.svg Osobny artykuł: Homeomorfizm grafów.

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[edytuj | edytuj kod]

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 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, 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, którego każdy wierzchołek jest stopnia k
Specjalne określenie dla grafów regularnych stopnia 3
Graf nie zawierający żadnej drogi zamkniętej
Graf, w którym dla każdego wierzchołka istnieje droga do każdego innego wierzchołka
Graf posiadający k spójnych składowych
Spójny graf acykliczny
Graf, którego wszystkie spójne składowe są drzewami
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łkiem ze zbioru drugiego. Pełny graf dwudzielny o \! n_1\ + n_2 wierzchołkach oznacza się \! K_{n_1,n_2}
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 posiadający drogę prostą przechodzą przez każdą krawędź.
Graf posiadający ścieżkę prostą przechodzą przez każdy wierzchołek.
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.
To izomorficzne przedstawienie grafu takie, że żadne dwie krawędzie się nie przecinają
Graf, którego przedstawienie tworzy siatkę wielościanu foremnego
Graf płaski, którego wszystkie ściany są utworzone przez drogi zamknięte tej samej długości
Graf, którego każdy wierzchołek/krawędź jest krytyczny/krytyczna
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)
To niemal ten sam, ale nieskierowany, bo bez zwrotów na krawędziach
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[edytuj | edytuj kod]

Operacje binarne[edytuj | edytuj kod]

Suma grafów[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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:
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, 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
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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Information icon.svg Osobny artykuł: 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'owskiejest 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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.

Przypisy

Bibliografia[edytuj | edytuj kod]

Zobacz też[edytuj | edytuj kod]

Wikimedia Commons

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

Linki zewnętrzne[edytuj | edytuj kod]