Informatyka MIMUW

Czym jest graf

Wyruszając w daleką podróż zabieramy ze sobą mapę samochodową. Głównymi elementami graficznymi zawartymi w mapie są punkty (małe kółka) symbolizujące miasta, oraz odcinki (lub łuki) obrazujące drogi pomiędzy nimi. Taka mapa jest z grubsza przedstawieniem rzeczywistości za pomocą grafu. Chcąc na przykład znaleźć drogę z Bydgoszczy do Krakowa, szukamy ciągu kolejno połączonych miast zaczynającego się w Bydgoszczy i kończącego się w Krakowie. Jest to nic innego, jak znalezienie odpowiedniej ścieżki w grafie połączeń między miastami.

Graf to para $\mathbf{G}=( V,E )$, gdzie:

• $V$ jest zbiorem wierzchołków,

(czasami zwanymi węzłami lub punktami grafu)

• $E$ jest rodziną (być może powtarzających się) krawędzi,

czyli jedno- i dwu-elementowych podzbiorów $V$.

Graf prosty to para $\mathbf{G}=( V,E )$, gdzie:

• $V$ jest zbiorem wierzchołków,
• $E$ jest zbiorem krawędzi między różnymi wierzchołkami,

czyli dwu-elementowych podzbiorów $V$.

Graf ogólny (a.) oraz prosty (b.)

Uwaga

W grafie w odróżnieniu od grafu prostego dopuszczamy pętle oraz krawędzie wielokrotne. Wierzchołek nazywany jest czasem także węzłem, jak i punktem grafu. Krawędź łącząca $v$ z $w$ oznaczana będzie jako $vw$. Jeśli istnieje krawędź $vw$ to mówimy, że $v$ i $w$ są sąsiadami; oraz że krawędź $vw$ jest incydentna do $v$ ($w$). Ponadto, dla grafu $\mathbf{G}$ symbolem ${\sf V}\!(\mathbf{G})$ będziemy oznaczać jego zbiór wierzchołków, zaś symbolem ${\sf E}\!(\mathbf{G})$ jego zbiór krawędzi. Czasem, dla odróżnienia grafu od grafu prostego, graf będziemy nazywać też grafem ogólnym.

Stopień wierzchołka $v$ w grafie $\mathbf{G}$ to liczba krawędzi incydentnych z $v$. Stopień wierzchołka $v$ oznaczany jest jako ${\sf deg}\ v$.

Obserwacja 12.1

Jeśli $\mathbf{G}=( V,E )$ jest grafem ogólnym, to

$\displaystyle\sum_{v\in V}{\sf deg}\ v=2\vert E \vert.$

A zatem liczba wierzchołków o nieparzystym stopniu jest parzysta.

Dowód

Każda krawędź jest incydentna do dwóch wierzchołków. Zliczając krawędzie incydentne do kolejnych wierzchołków, a następnie sumując te wartości, każda krawędź $vw$ zostanie zliczona dwa razy: raz przy rozpatrywaniu wierzchołka $v$, a drugi raz przy $w$.

Jeśli $\mathbf{G}$ miałby nieparzyście wiele wierzchołków o nieparzystym stopniu to suma $\displaystyle\sum_{v\in V}{\sf deg}\ v$ byłaby nieparzysta, wbrew temu, że jest liczbą parzystą $2\vert E \vert$.

Uwaga

Dla grafów $\mathbf{G}=( V,E )$, $\mathbf{G}_1=( V_1,E_1 )$, $\mathbf{G}_2=( V_2,E_2 )$ definiujemy następujące pojęcia:

• suma grafów $\mathbf{G}_1\cup\mathbf{G}_2=( V_1\cup V_2,E_1\cup E_2 )$,

• przecięcie grafów $\mathbf{G}_1\cap\mathbf{G}_2=( V_1\cap V_2,E_1\cap E_2 )$,

• różnica grafów $\mathbf{G}_1-\mathbf{G}_2=( V_1- V_2,E_1- E_2 )$,

• podgraf grafu $\mathbf{G}$ to graf $\mathbf{H}$, w którym ${\sf V}\!(\mathbf{H})\subseteq{\sf V}\!(\mathbf{G})$ i ${\sf E}\!(\mathbf{H})\subseteq{\sf E}\!(\mathbf{G})$,

• restrykcja grafu $\mathbf{G}$ do podzbioru $X\subseteq V$ to $\mathbf{G}|_X=( X,\lbrace vw:v,w\in X \rbrace )$,

• podgraf indukowany grafu $\mathbf{G}$ to graf będący restrykcją grafu $\mathbf{G}$,

• iloraz grafu $\mathbf{G}$ przez relację równoważności $\theta\subseteq V\times V$ na zbiorze jego wierzchołków to graf postaci

$\mathbf{G}/\theta=( V/\theta,\lbrace \lbrace v/\theta,w/\theta \rbrace:\lbrace v,w \rbrace\in E \rbrace ),$

• ściągnięcie zbioru wierzchołków $X\subseteq V$ w grafie $\mathbf{G}$ to szczególny przypadek ilorazu $\mathbf{G}/\theta$, w którym klasy równoważności wszystkich wierzchołków spoza $X$ są jednoelementowe, a $X$ stanowi dodatkową klasę, tzn. $V/\theta=\lbrace \lbrace v \rbrace:v\in V- X \rbrace\cup\lbrace X \rbrace$. W ten sposób zbiór $X$ został ściągnięty do punktu, którego sąsiadami są sąsiedzi jakiegokolwiek wierzchołka z $X$. Z drugiej strony, jeśli $\theta\subseteq V\times V$ jest relacją równoważności o klasach $X_1,\ldots,X_k$, to ściągając w grafie $\mathbf{G}$ kolejno zbiory $X_1,\ldots,X_k$ otrzymamy graf ilorazowy $\mathbf{G}/\theta$.

W dotychczasowej interpretacji grafów, jako mapy dróg zakładaliśmy, że istnienie drogi np. z Krakowa do Zakopanego, gwarantowało także możliwość powrotu po tej samej trasie. To oczywiście nie musi być zawsze prawdą, np. w miastach jest wiele dróg jednokierunkowych. Chcąc rozważać również takie jednokierunkowe trasy, tzn uwzględniać kierunek relacji między dwoma obiektami, będziemy mówić o grafach skierowanych.

Graf skierowany (lub inaczej digraf) to para $\mathbf{D}=( V,E )$, gdzie

• $V$ jest zbiorem wierzchołków,

• $E$ jest zbiorem krawędzi skierowanych, czyli $E\subseteq V\times V$.

Uwaga

Krawędź digrafu (czyli uporządkowaną parę) $vw$ graficznie przedstawiamy jako strzałkę $v\ \bullet\!\longrightarrow\!\bullet\ w$.

Graf szkieletowy digrafu $\mathbf{D}$ to graf otrzymany z $\mathbf{D}$ poprzez zaniedbanie (usunięcie) kierunku krawędzi, ale nie samych krawędzi.