Co to jest graf?

GrafgrafGraf to struktura, która składa się z dwóch rodzajów elementów – wierzchołkówwierzchołekwierzchołków i krawędzikrawędźkrawędzi.

Wierzchołek grafu jest elementem, który stanowi reprezentację pewnego obiektu, miejsca czy rzeczy. W zależności od struktury, jaka została przedstawiona w formie grafu, jego wierzchołkami (inaczej nazywanymi węzłami) mogą być np. samochody, planety, miasta na mapie czy cząsteczki chemiczne.

Krawędź grafu to z kolei powiązanie między dwoma wierzchołkami. Może ona mieć postać materialną (jak w przypadku kabli łączących komputery w sieci czy też dróg między miastami) lub niematerialną (jak relacje społeczne – np. przyjaźnie łączące uczniów danej klasy). Każda krawędź reprezentowana jest przez parę wierzchołków.

Oznaczenia i definicje

Mianem grafu prostego $G$ określamy parę $G=\left(V,E\right)$, w której $V$ jest skończonym zbiorem elementów (wierzchołków lub inaczej węzłów), a $E$ – skończonym zbiorem nieuporządkowanych par różnych elementów (krawędzi) zbioru $V$. W takim przypadku $V$ oznacza zbiór wierzchołków, a $E$ – zbiór krawędzi grafu $G$.

Posługując się grafami, często pomijamy cechy geometryczne, takie jak odległość między punktami – umiejscowienie wierzchołków służy jedynie przejrzystej wizualizacji.

R17JwVf9PGbu3

Ilustracja przedstawia trzy grafy.
1: Połączone 5 punktów, z których każdy połączony jest dodatkowo z szóstym punktem środkowym.
2: Graf przedstawia połączenie sześciu punktów z nieregularnymi połączeniami.
3: Graf łączy 6 punktów tworząc kształt gwazdy.

Wierzchołki grafu zwykle oznaczamy kolejnymi liczbami naturalnymi lub literami (jak na rysunku poniżej: $p$, ${q}$, $r$ itd.), natomiast krawędzie będące nieuporządkowaną parąpara nieuporządkowananieuporządkowaną parą wierzchołków, np. $\{p,q\}$, możemy zapisać jako $pq$. Mówimy wtedy, że krawędź $pq$ łączy wierzchołki $p$ i $q$.

RET85GKwO8DtD

Ilustracja przedstawia graf.
Węzły grafu podpisane są literami: r, q, p, s, v, y.
Każdy z węzłów łączy się z węzłem środkowym zawierającym literę u.

Ważne!

Przedstawione wcześniej przykłady grafów to grafy proste. Gdyby dopuścić jednak, że krawędzie grafu mogą łączyć także wierzchołek sam ze sobą oraz że pary wierzchołków mogą być połączone więcej niż jedną krawędzią, mielibyśmy do czynienia z multigrafem. Krawędź łączącą wierzchołek sam ze sobą nazywamy pętlą, zaś krawędź, która łączy wierzchołki już połączone – krawędzią wielokrotną.

Oto przykłady pętli oraz krawędzi wielokrotnych:

Rc3qpc8Blle3c

Ilustracja przedstawia przykład pętli oraz krawędzi wielokrotnych.
Po lewej stronie zielonym kolorem zaznaczono pętle linię która tworzy pętlę powracającą do tego samego węzła.
Po prawej stronie zaznaczono zakrzywione linie łączące węzły przedstawiające krawędzie wielokrotne.

Wiele algorytmów grafowych korzysta z wag krawędzi, które można interpretować na różne sposoby. Przykładem może być algorytm DijkstryP1F65HeHZalgorytm Dijkstry (czyli algorytm wyszukujący najkrótsze połączenie między dwoma wierzchołkami) – wagi krawędzi traktujemy wówczas jako odległość między wierzchołkami i na tej podstawie algorytm znajduje najkrótszą ścieżkę między dwoma węzłami grafu. Graf, w którym krawędzie mają przypisane wagi, nazywamy grafem ważonym.

R1ANkZTZ7oYfe

Ilustracja przedstawia graf o połączeniach węzeł prosta węzeł: A, 10, C.
C, 5, D.
D, 6, E.
E, 4, B.
B, 14, F.
F, 7, A.
F, 8, C.
C, 2, B.
D, 1, B.

Dwa wierzchołki nazywamy sąsiednimi, gdy są one połączone krawędzią. Możemy wtedy również powiedzieć, że wierzchołki te są incydentne z tą krawędzią. Jeśli krawędzie mają jeden wspólny wierzchołek, również określamy je jako sąsiednie.

Stopień wierzchołkastopień wierzchołkaStopień wierzchołka $w$ grafu oznaczamy symbolem $\deg(w)$. Jest to liczba krawędzi incydentnych z wierzchołkiem $w$. Zbiór wierzchołków sąsiednich dla wierzchołka $w$ nazywamy sąsiadami wierzchołka $w$.

Trasy, drogi, cykle

Trasą w grafie nazywamy ciąg krawędzi: $v_1v_2,v_2v_3,\ldots,v_{k-1}v_k$, w którym każde dwie kolejne krawędzie ze sobą sąsiadują lub są identyczne. Taka trasa wyznacza kolejno ciąg wierzchołków, które łączy: $v_1,v_2,v_3,\ldots,v_{k-1},v_k$. W trasie tej $v_1$ nazywamy wierzchołkiem początkowym, zaś $v_k$ – wierzchołkiem końcowym. Liczbę krawędzi wchodzących w skład trasy nazywamy jej długością. Szczególny przypadek trasy, gdzie wszystkie krawędzie są różne, nazywamy ścieżką. Ścieżkę, w której wierzchołki są różne (z wyjątkiem wierzchołka początkowego i końcowego), nazywamy drogą.

R11lQKShCIs93

Ilustracja przedstawia graf połączonych liter: u, q, r, t, s, v, p, x, w.
Proste łączące litery r, s, q, t z literą u są koloru niebieskiego.

Na powyższym grafie zaznaczono ścieżkę $t,u,q,r,u,s$, w której $t$ jest wierzchołkiem początkowym, a $s$ – wierzchołkiem końcowym. W tym przypadku długość ścieżki jest równa $5$. Warto zauważyć, że wierzchołek $u$ powtarza się na powyższej ścieżce dwukrotnie – z tego powodu nie możemy nazwać jej drogą.

Przykładową drogę $t,u,s,v,p,w$, w której $t$ jest wierzchołkiem początkowym, a $w$ wierzchołkiem końcowym, przedstawiono na grafie:

RCViTV3sWTqWi

Ilustracja przedstawia graf połączonych liter: u, q, r, t, s, v, p, x, w.
Proste łączące litery t, u, s, v, p  są koloru niebieskiego.

Jeśli dla pewnej ścieżki $v_1v_2\ldots v_{k-1}v_k$ zachodzi równość $v_1=v_k$, to ścieżkę tę nazywamy ścieżką zamkniętą. Ścieżka zamknięta, która zawiera co najmniej jedną krawędź, to cykl. Oznacza to, że jedyną ścieżką zamkniętą niebędącą cyklem, jest ścieżka niezawierająca żadnej krawędzi.

RU06weaVPBZMC

Ilustracja przedstawia dwa grafy.
1: przedstawia graf połączonych liter: u, q, r, t, s, v, p, x, w.
Proste łączące litery p, q, r, t, s, v są koloru niebieskiego.
2: przedstawia graf połączonych liter: u, q, r, t, s, v, p, x, w.
Proste łączące litery r, q, u są koloru niebieskiego.

Powyżej zaznaczono dwa cykle: $t,s,v,p,q,r,t$ oraz $r,u,q,r$. Możemy je znaleźć w tym samym grafie. Jeśli chcemy wiedzieć, czy dany graf zawiera cykl, możemy skorzystać z następującej własności:

Izomorfizm

Grafy $G$ i $H$ są izomorficzneizomorfizmizomorficzne, jeżeli między ich wierzchołkami istnieje podobieństwo polegające na tym, że liczba krawędzi łączących wybraną parę wierzchołków grafu $G$ oraz liczba krawędzi łączących dwa odpowiadające im wierzchołki grafu $H$ są takie same. Izomorfizm zapisujemy jako wyrażenie $G≃H$, a odpowiedniość wierzchołków $w$ i $p$ oznaczamy symbolem $w↔p$.  Grafy izomorficzne mają taką samą strukturę, mogą różnić się tylko nazwami wierzchołków i krawędzi.

R5s0w2cQJ8rtp

Ilustracja przedstawia dwa grafy.
1: W kształcie sześciokąta gdzie każda litera łączy się z literą sąsiednią oraz z literą na przeciw niej, zawiera w węzłach litery: s, r, q, p, u, t.
2: Graf izomorficzny względem pierwszego to graf z literami p prim, t prim, r prim, s prim, q prim, u prim.
Ułożone są w dwóch rzędach po trzy węzły, każdy węzeł z jednego rzędu łączy się z każdym węzłem z rzędu drugiego.

Na przedstawionym rysunku wierzchołki grafu G odpowiadają wierzchołkom grafu H. Przykładowo, wierzchołek $p$ grafu G ma trzech sąsiadów, co oznacza że odpowiada wierzchołkowi $p'$ w grafie H, czyli $p↔p'$.

Słownik