WYKLAD

TEORIA GRAFÓW

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

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