Graf (matematyka)

Z Wikipedii

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

Najważniejsze pojęcia
graf
podgraf
cykl
klika
stopień wierzchołka
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
Breadth-first search
Depth-first search
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
najbliższego sąsiada

Zagadnienia przedstawiane jako problemy grafowe
problem komiwojażera
problem chińskiego listonosza
problem kojarzenia małżeństw

Inne zagadnienia
kod Graya
diagram Hassego

edytuj ten szablon

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 mogą stanowić reprezentację jakichś obiektów rzeczywistych, natomiast krawędzie mogą obrazować połączenia 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 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ź (jeśli graf będzie reprezentował trud poruszania się po jakimś terenie, to droga pod górkę będzie miała większą wagę niż z górki).

[edytuj] Definicje

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

[edytuj] Graf

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

V jest zbiorem wierzchołków,
E jest rodziną dwuelementowych podzbiorów zbioru wierzchołków V, zwanych krawędziami: $E\subseteq \{ \{u,v\} : u,v \in 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 ilości wierzchołków i/lub krawędzi.

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

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

[edytuj] 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 funcji z V, E, lub A w pewnien zbiór X, można przypisać krawędziom lub wierzchołkom etykiety, służące do przechowywania dodatowych 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ę jedno- i dwuelementowych podzbiorów zbioru wierzchołków - $\! \gamma : E \to \{\{v,u\}:v,u \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ą, 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$ .

[edytuj] Pojęcia

[edytuj] Podstawowe

Wszystkie drogi w tym grafie są proste
nie ma cykli
istnieją dwie drogi o długości 4

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,\cdots ,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ę

Cykl

Zamknięta droga prosta $e_a,e_b,\cdots ,e_z$ , taka, że krawędź

e z

kończy się w początkowym wierzchołku drogi

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.

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.

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

Nadgraf grafu H

Taki graf, że H jest jego podgrafem.

klika

Podzbiór wierzchołków danego grafu, z których każdy jest sąsiadem każdego innego (czyli podgraf pełny).

Sąsiad:

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

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)

Graf r-regularny:

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

Ś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,\cdots ,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,\cdots ,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

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.

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.

[edytuj] Zaawansowane

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ę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.

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.

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ą.

Ś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ą.

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.

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.

[edytuj] Przykład

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\} \}$

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$ .

[edytuj] Izomorfizm i homeomorfizm grafów

Zobacz więcej w osobnym artykule: 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.

Zobacz więcej w osobnym artykule: 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 ilości wierzchołków, bądź wymazywanie ich.

[edytuj] Grafy geometryczne

Zobacz więcej w osobnym artykule: Grafy geometryczne.

Dla każdego grafu istnieje nieskończenie wiele przedstawiających go rysunków, czasami jednak pożądane 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.

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

Ta sekcja jest zalążkiem. Jeśli możesz, rozbuduj ją.

[edytuj] 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 mulitigrafem. 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

[edytuj] Operacje na grafach

[edytuj] Operacje binarne

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

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

[edytuj] 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$ .

[edytuj] 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 sąsiadujące ze sobą w G krawędzie.

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.

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.

[edytuj] 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" ilości 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ąca 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ą.

[edytuj] Macierz sąsiedztwa

Zobacz więcej w osobnym artykule: 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).

$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.

[edytuj] 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 ilości 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.

[edytuj] 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ą wszyskie 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]$

[edytuj] 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 routing 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.

[edytuj] Bibliografia

Kenneth Ross, Charles Wright, Matematyka dyskretna, PWN, 2003
Robin Wilson, Wprowadzenie do teorii grafów, PWN, 2004
Witold Lipski, Kombinatoryka dla programistów, WNT, 2004
Juliusz Kulikowski, Zarys teorii grafów, PWN, 1986
Marek Kubale, Optymalizacja dyskretna. Modele i metody kolorowania grafów, WNT, 2002

[edytuj] Zobacz też

Zobacz galerię na Wikimedia Commons:
Graf (matematyka)

Sławni badacze właściwości grafów:

[edytuj] Linki zewnętrzne

ŚWIAT 24/7

Schwytanie byłego przywódcy Serbów bośniackich Radovana Karadzicia, podróż Baracka Obamy na Bliski Wschód i do Europy oraz Komisja Europejska, która grozi USA w sprawie wiz - to najważniejsze zagraniczne tematy, o których pisaliśmy w ostatnim tygodniu w tvn24.pl.

Kalifornia bez tłuszczu

Gubernator Kalifornii Arnold Schwarzenegger podpisał rozporządzenie, które zakazuje używania tłuszczów nienasyconych (trans tłuszczy) w restauracjach w całej Kalifornii. Tłuszcze te odpowiedzialne są między innymi za chorobę wieńcową serca.

Rosja gani Busha za zrównanie komunizmu z nazizmem

Rosyjskie Ministerstwo Spraw Zagranicznych oświadczyło w sobotę, że prezydent USA George W. Bush zranił weteranów II wojny światowej zrównując nazizm z komunizmem.

Piraci porwali 8 obcokrajowców

W sobotni poranek piraci porwali 8 pracowników kompanii naftowej w delcie Nigru. W ciągu ostatnich 48 godzin już 16 naftowców znalazło się w rękach porywaczy.

Pijana kobieta wymusiła lądowanie samolotu

26-letnia pijana Brytyjka usiłowała wydostać się z lecącego na wysokości 10 tys. metrów samolotu. Próby otwarcia drzwi skończyły się awaryjnym lądowaniem.

Linki: Strona g��wna

Encyklopedia