Rysunek grafu

Rozważmy następujące dwa grafy, w których wierzchołki oznaczone zostały liczbami z przedziału $[0,5]$.

RBRrpPyeY21Qu

Rysunek przedstawiający różne dwa grafy o wierzchołkach oznaczonych liczbami od 0 do 5. W obu grafach są połączenia, lecz różnią się wyglądem. 0: 1,2. 1:0, 3, 5. 2, 0, 3. 3: 2, 1, 4. 4: 3, 5. oraz 5: 4, 1.

Czy reprezentują one ten sam zbiór wierzchołków i krawędzi? Tak, ponieważ przedstawiają takie same wierzchołki wraz z zachowanymi połączeniami między nimi. Parametry takie jak długości krawędzi czy położenie wierzchołków nie mają tu żadnego znaczenia. Taką własność grafów nazywamy izomorfizmemizomorfizmizomorfizmem.

Gdyby grupie uczniów podano listę wierzchołków i krawędzi, a następnie poproszono o narysowanie reprezentującego je grafu, prawdopodobnie każda osoba wyobraziłaby go sobie zupełnie inaczej. Długości krawędzi czy ułożenie wierzchołków różniłyby się na każdym rysunku, a mimo to wszystkie ilustracje przedstawiałyby ten sam graf. Możemy zatem przyjąć, że jeżeli dowolne dwa wierzchołki na jednym rysunku grafu połączone są krawędzią i odpowiadające im wierzchołki na drugim rysunku również są połączone krawędzią, to obydwa rysunki przedstawiają ten sam graf.

Reprezentacje grafów prostych nieskierowanych bez wag krawędzi

Na początek omówmy sposoby reprezentacji podstawowych grafów, które nie zawierają krawędzi wielokrotnych ani pętli i mają krawędzie wyłącznie nieskierowane, a same krawędzie nie mają przypisanych wag.

Macierz sąsiedztwa

Poznaliśmy już jedną z reprezentacji grafów polegającą na przechowywaniu tablicy wierzchołków oraz tablicy krawędzi. Innym sposobem reprezentacji grafu jest wykorzystanie macierzy do przedstawienia połączeń między wierzchołkami.

Sposób ten to macierz sąsiedztwa. Jest to dwuwymiarowa tablica o rozmiarze $n\times n$, gdzie $n$ to liczba wierzchołków grafu. Jej wartości opisują, czy między dwoma wierzchołkami istnieje krawędź.

W grafach, których krawędzie nie mają przypisanych wag, wartość wyrazu $a_{ij}$ wynosi 1, jeśli istnieje krawędź od wierzchołka $i$ do wierzchołka $j$, lub 0, jeżeli taka krawędź nie istnieje. Przykład grafu oraz odpowiadającą mu macierz sąsiedztwa przedstawia następująca ilustracja:

R5lS56m04tSss

Rysunek przykładowego grafu z połączeniami: 0, 1. 0, 2. 1, 2. 2, 3. Po prawej stronie znajduje się odpowiadająca mu macierz sąsiedztwa.
kolumny jak i wiersze opisane są wartościami: 0, 1, 2, 3.
Wiersz zerowy: 0, 1, 1, 0.
Wiersz pierwszy: 1, 0 1, 0.
Wiersz drugi: 1, 1, 0, 1.
Wiersz trzeci: 0, 0, 1, 0.

Kolumny i wiersze macierzy sąsiedztwa opisane są indeksami wierzchołków. Wartości pól macierzy wskazują, czy dana krawędź istnieje, czy też nie. Przykładowo, wartość $a_{01}=1$ oznacza, że między wierzchołkami 0 i 1 istnieje krawędź, zaś $a_{03}=0$ oznacza, że między wierzchołkami 0 i 3 nie ma takiego połączenia.

Podstawowe czynności, takie jak dodawanie krawędzi, usuwanie krawędzi i sprawdzanie, czy istnieje krawędź między wierzchołkiem $i$ oraz wierzchołkiem $j$, są operacjami, które wymagają jedynie zmiany wartości lub jej odczytania z konkretnego pola tablicy.

Listy sąsiedztwa

Macierz sąsiedztwa dla grafów o małej liczbie krawędzi względem liczby wierzchołków zajmuje w pamięci komputera dużo miejsca, które nie zostanie wykorzystane. To główny powód, dla którego w pewnych przypadkach lepszym sposobem reprezentacji będzie wykorzystanie list sąsiedztwa, bardziej oszczędnych pod względem ilości wykorzystanej pamięci komputera.

Listy sąsiedztwa są sposobem reprezentacji grafu jako jednowymiarowej tablicy list. Tablica ta zawiera $n$ list, gdzie $n$ jest liczbą wierzchołków grafu. Każdy z wierzchołków ma więc przypisaną dokładnie jedną listę zawierającą indeksy wierzchołków, które są z nim połączone krawędzią.

Na poniższym przykładzie grafu i odpowiadających mu list sąsiedztwa można zauważyć, że sposób ten zajmuje mniej miejsca w pamięci komputera niż macierz sąsiedztwa - taka macierz miałaby rozmiar $5×5$, natomiast w reprezentacji wykorzystującej listy sąsiedztwa każda z list zawiera liczbę elementów równą liczbie sąsiadów danego wierzchołka (np. dla wierzchołka 1 są to jedynie dwa elementy).

RZ3M8aoEUHcYa

Rysunek grafu i odpowiadająca mu lista sąsiedztwa: 0: 1, 2, 3, 4.
1: 0, 2.
2: 0, 1, 4.
3: 0, 4.
4: 0, 2, 3.

Na powyższym przykładzie każdy z wierzchołków (o indeksach od 0 do 4) ma własną listę sąsiedztwa zawierającą indeksy sąsiadujących z nim wierzchołków. Przykładowo, lista sąsiedztwa wierzchołka o indeksie 4 zawiera wierzchołki, które są z nim połączone krawędziami: 0, 2 i 3.

Macierz incydencji

Macierz incydencji to kolejny sposób reprezentacji grafu. Jest ona dwuwymiarową tablicą, której wiersze reprezentują wierzchołki, a kolumny - krawędzie grafu (jak na poniższym przykładzie).

R1UQe9iRYbAdS

Rysunek grafu i odpowiadająca mu macierz incydencji.
Kolumny macierzy opisane krawędziami: e0, e1, e2, e3, e4, e5.
Wiersze węzłami: 0, 1, 2, 3, 4.
Wiersz zerowy: 1, 1, 0 ,0 ,0 ,0.
Wiersz pierwszy: 0, 0, 1, 1, 0, 0.
Wiersz drugi: 1, 0 ,1 ,0 ,1 ,0.
Wiersz trzeci: 0, 0, 0, 1, 0, 1.
Wiersz czwarty: 0, 1, 0 ,0 ,1, 1.

Wartość wyrazu $a_{ie}$ wynosi 1 lub 0, w zależności od tego, czy krawędź $e$ jest incydentnaincydencjaincydentna z wierzchołkiem $i$. Na powyższym grafie znajdziemy pięć wierzchołków i sześć krawędzi - zatem macierz incydencji będzie miała pięć wierszy i sześć kolumn. Pierwsza kolumna powyższej macierzy zawiera informację o tym, że w grafie istnieje krawędź $e0$, która łączy wierzchołek 0 i 2. Analogicznie interpretować można pozostałe kolumny macierzy.

Możemy zapisać, że macierz o rozmiarze $n\times m$ jest macierzą incydencji grafu, gdzie dla każdego wyrazu $a_{ie}$ mamy:

- jeśli krawędź $e$ jest incydentna z wierzchołkiem $i$. W przeciwnym razie:

Reprezentacje innych typów grafów

Opisane sposoby reprezentacji grafów prostych można wykorzystać do reprezentacji grafów ważonych, grafów skierowanych czy multigrafów.

Wagi krawędzi

W zadaniach dotyczących problemu najkrótszych ścieżeknajkrótsza ścieżkanajkrótszych ścieżek (opisanego w e‑materiale Algorytm DijkstryP1F65HeHZAlgorytm Dijkstry) czy sieci maksymalnego przepływuproblem maksymalnego przepływusieci maksymalnego przepływu (o czym możesz przeczytać w e‑materiale Problem niezawodności sieciPJAfYLZPnProblem niezawodności sieci) istotną zmienną, którą należy wziąć pod uwagę, jest waga krawędzi. W zależności od zagadnienia, z jakim się mierzymy, wagi mogą reprezentować różne parametry, np. odległość między dwoma sąsiednimi wierzchołkami.

Wagi krawędzi to istotny parametr teorii grafów. Z tego względu należy określić pewien sposób reprezentacji, który umożliwia zapisanie w pamięci wszystkich wag krawędzi wraz z informacją o połączeniach między wierzchołkami. Okazuje się, że każdą z dotychczasowych reprezentacji można w łatwy sposób dostosować do naszych potrzeb.

• Jeśli pewne dwa wierzchołki $i$ oraz $j$ połączone są krawędzią, to wyraz $a_{ij}$ w macierzy sąsiedztwa jest równy wadze krawędzi, która je łączy. W wypadku, gdy wierzchołki $i$ oraz $j$ nie są sąsiednie, wyraz $a_{ij}$ jest równy 0.

• Lista sąsiadów wierzchołka $i$ w listach sąsiedztwa grafu zawiera pary postaci $(j,w(i,j\left)\right)$, gdzie $w(i,j)$ oznacza wagę krawędzi, która łączy wierzchołek $i$ z wierzchołkiem $j.$

• Jeśli w grafie istnieje krawędź $ij$ o indeksie $e$ i wadze $w$, to w macierzy incydencji wyrazy $a_{i,e}$ oraz $a_{j,e}$ są równe $w$, a wszystkie pozostałe wyrazy w kolumnie $e$ mają wartość 0.

RSnY18u4yrAQJ

Ilustracja przedstawia graf z wagami krawędzi i odpowiadające jej: Macierz sąsiedztwa, macierz incydencji, listę sąsiedztwa.
Macierz sąsiedztwa wiersz zerowy: 0, 4, 7, 0.
Wiersz pierwszy: 4, 0 ,5, 1.
Wiersz drugi: 7, 5, 0, 9.
Wiersz trzeci: 0, 1, 9, 0.
Macierz incydencji wiersz zerowy: 4, 7, 0 ,0 ,0.
Wiersz pierwszy: 4, 0 ,5, 1, 0.
Wiersz drugi: 0, 7, 5, 0, 9.
Wiersz trzeci: 0, 0, 0, 1, 9.
Lista sąsiedztwa 0 z 1, 4 i 2, 7.
1 z 0, 4 i 2, 5 i 3, 1.
2 z 0, 7 i 1, 5 i 3, 9.
3 z 1, 1 i 2, 9.

Powyżej pokazano przykładowy graf z wagami krawędzi wraz z jego reprezentacjami. W grafie tym krawędź $e0$ łącząca wierzchołki 0 i 1 ma wagę 4:

• W macierzy sąsiedztwa wyrazy $a_{01}$ i $a_{10}$ są równe 4.

• W liście sąsiedztwa wierzchołka 0 znajduje się więc wierzchołek 1 z przypisaną wagą 4, a w liście sąsiedztwa wierzchołka 1 znajduje się wierzchołek 0, również z przypisaną wagą 4.

• W macierzy incydencji w kolumnie $e0$ wartość 4 przypisana jest wierzchołkom 0 i 1.

Grafy skierowane

W grafie nieskierowanym krawędzie stanowią nieuporządkowaną parę pewnych dwóch wierzchołków $v$ oraz $w$.

Sytuacja wygląda inaczej w przypadku grafów skierowanych. Wierzchołki takiego grafu połączone są za pomocą łuków, czyli krawędzi mających kierunek (krawędzi skierowanych). Łuk jest uporządkowaną parą wierzchołków $(v,w)$, którą na rysunku grafu oznacza się strzałką.

Kolejność wierzchołków krawędzi skierowanej określa kierunek, w którym możemy przemieszczać się po grafie – oznacza to, że po krawędzi $(v,w)$ możemy przejść tylko od wierzchołka $v$ do $w$. Odwrotny kierunek przemieszczania się jest niemożliwy. Krawędzie $(v,w)$ i $(w,v)$ nie są więc traktowane jako ta sama krawędź.

Reprezentacje grafów skierowanych możemy zdefiniować następująco:

• Wyraz $a_{ij}$ w macierzy sąsiedztwa jest równy 1, jeśli istnieje krawędź od wierzchołka $i$ do $j$, lub równy 0, jeśli taka krawędź nie istnieje.

• W listach sąsiedztwa wierzchołek $j$ znajduje się na liście wierzchołka $i$, o ile istnieje krawędź skierowana od wierzchołka $i$ do $j$.

• Jeśli w grafie istnieje krawędź skierowana $(i,j)$ o indeksie $e$, to w macierzy incydencji wyraz $a_{ie}$ jest równy 1, wyraz $a_{je}$ jest równy -1, a wszystkie pozostałe wyrazy w kolumnie $e$ mają wartość 0.

RrEK4SDMfs4B8

Ilustracja przedstawia graf skierowany i odpowiadające jej: Macierz sąsiedztwa, macierz incydencji, listę sąsiedztwa.
Macierz sąsiedztwa wiersz zerowy: 0, 1, 0, 0.
Wiersz pierwszy: 0, 0 , 1, 1.
Wiersz drugi: 1, 0, 0, 1.
Wiersz trzeci: 0, 0, 0, 0.
Macierz incydencji wiersz zerowy: 1, -1, 0 ,0 ,0.
Wiersz pierwszy: -1, 0 ,1, 1, 0.
Wiersz drugi: 0, 1, -1, 0, 1.
Wiersz trzeci: 0, 0, 0, -1, -1.
Lista sąsiedztwa 0 z 1.
1 z 1 i 3.
2 z 0 i 3.
3 puste.

Powyżej przedstawiono przykładowy graf skierowany wraz z jego reprezentacjami. W grafie tym krawędź $e0$ skierowana jest od wierzchołka 0 do wierzchołka 1.

• W macierzy sąsiedztwa wyraz $a_{01}$ jest równy 1, a wyraz $a_{10}$ jest równy 0.

• W liście sąsiedztwa wierzchołka 0 znajduje się więc wierzchołek 1, ale w liście sąsiedztwa wierzchołka 1 nie ma wierzchołka 0.

• W macierzy incydencji w kolumnie $e0$ wartość 1 jest przypisana wierzchołkowi 0, a wierzchołkowi 1 wartość -1.

Krawędzie wielokrotne i pętle

W bardziej złożonych problemach możemy spotkać się z pojęciem pętli i krawędzi wielokrotnej. Pętla to taka krawędź, która łączy dany wierzchołek z samym sobą. Krawędź wielokrotna natomiast to zbiór zwielokrotnionych krawędzi $vw$. Graf, który zawiera co najmniej jedną krawędź wielokrotną lub pętlę, nazywamy multigrafem.

Wiedząc już, jak zmieniają się postacie reprezentacji dla grafów ważonych i skierowanych, możemy scharakteryzować analogiczną zmianę dla multigrafów.

• Każdy wyraz $a_{ij}$ macierzy sąsiedztwa jest równy liczbie krawędzi łączących wierzchołki $i$ z wierzchołkiem $j$. Pętlę wierzchołka $i$ zapisujemy wyrazem $a_{ii}$, który jest równy liczbie pętli tego wierzchołka.

• W liście sąsiedztwa wierzchołka $i$ jest tyle wierzchołków sąsiednich $j$, o ile zwielokrotniona jest krawędź łącząca wierzchołki $i$ oraz $j$. Jeśli istnieje pętla wierzchołka $i$, to w liście wierzchołka $i$ powinno się znaleźć tyle wierzchołków $i$, ile pętli ma ten wierzchołek.

• Dla macierzy incydencji każda krawędź ma swój unikalny indeks, podobnie każdą krawędź zwielokrotnioną podpisujemy innym indeksem. Aby oznaczyć krawędź $e$ incydentną z wierzchołkiem $i$, wyrazowi $a_{ie}$ przypiszemy wartość 1. Jeśli krawędź $e$ jest pętlą wierzchołka $i$, to w kolumnie $e$ jedynie wyraz $a_{ie}$ ma wartość 1.

RFKYGG2NS6Ihp

Ilustracja przedstawia graf zawierający pętle i odpowiadające jej: Macierz sąsiedztwa, macierz incydencji, listę sąsiedztwa.
Macierz sąsiedztwa wiersz zerowy: 2, 1, 1, 0.
Wiersz pierwszy: 1 ,0 ,2, 1.
Wiersz drugi: 1, 2, 1, 1.
Wiersz trzeci: 0, 1, 1, 0.
Macierz incydencji wiersz zerowy: 1, 1, 1, 1, 0, 0, 0 ,0 ,0.
Wiersz pierwszy: 0, 0, 1, 0 ,1 ,1, 1, 0 ,0.
Wiersz drugi: 0, 0, 1, 0 ,1, 1 ,1, 0, 0.
Wiersz trzeci: 0, 0 ,0 ,0 ,0 ,0 ,1 , 1, 0.
Lista sąsiedztwa 0 z 0, 0, 1, 2.
1 z 0, 2, 2, 3.
2 z 0, 1, 1, 2, 3.
3 z 1, 2.

Powyżej przedstawiono przykładowy multigraf wraz z jego reprezentacjami. W grafie tym krawędzie $e0$ i $e1$ są pętlami incydentnymi z wierzchołkiem 0:

• W macierzy sąsiedztwa wyraz $a_{00}$ jest zatem równy 2.

• W liście sąsiedztwa wierzchołka 0 dwukrotnie znajduje się więc wierzchołek 0.

• W macierzy incydencji w kolumnach $e0$ i $e1$ wartość 1 przypisana jest wierzchołkowi 0.

Słownik