Graf skierowany

Graf skierowany, sgraf^[1], graf zorientowany^[2] digraf, od ang. directed graph, DG – rodzaj grafu rozważanego w teorii grafów. Graf skierowany definiuje się jako uporządkowaną parę zbiorów. Pierwszy z nich zawiera wierzchołki grafu, a drugi składa się z krawędzi grafu, czyli uporządkowanych par wierzchołków. Ruch po grafie możliwy jest tylko w kierunkach wskazywanych przez krawędzie. Graf skierowany można sobie wyobrazić jako sieć ulic, z których każda jest jednokierunkowa. Ruch pod prąd jest zakazany. Najczęściej grafy skierowane przedstawia się jako zbiór punktów reprezentujących wierzchołki połączonych strzałkami (stąd nazwa) albo łukami zakończonymi grotem (strzałką, zwrotem)^[3].

Definicja formalna

Matematyczna definicja zakłada, że graf skierowany ${\displaystyle G}$ to uporządkowana para ${\displaystyle G:=\langle V,A\rangle }$ spełniająca następujące warunki:

1. ${\displaystyle V}$ (vertex) to zbiór wierzchołków,
2. ${\displaystyle A}$ to zbiór uporządkowanych par nazywanych krawędziami skierowanymi, który jest podzbiorem iloczynu kartezjańskiego ${\displaystyle V\times V}$
3. Krawędź:

${\displaystyle e=(a,b)}$

rozumiana jest jako skierowana z wierzchołka ${\displaystyle a}$ do ${\displaystyle b.}$

Alternatywna definicja zakłada, że graf skierowany ${\displaystyle G}$ definiuje dwójka: ${\displaystyle G=\langle V;E\rangle ,}$ gdzie ${\displaystyle V}$ jest dowolnym, niepustym zbiorem zwanym zbiorem wierzchołków, natomiast ${\displaystyle E}$ jest podzbiorem iloczynu kartezjańskiego ${\displaystyle V\times V,}$ czyli:

1. ${\displaystyle V\neq \varnothing ,}$
2. ${\displaystyle E\subseteq P_{2}(V).}$

Elementy rodziny ${\displaystyle E(G)}$ są nazwane krawędziami grafu. Krawędź ${\displaystyle \{u,v\}}$ można w skrócie oznaczać ${\displaystyle uv.}$ Mówimy, że krawędź ${\displaystyle e=uv}$ łączy wierzchołki ${\displaystyle u}$ i ${\displaystyle v.}$

Moc zbioru ${\displaystyle V}$ nazywamy rzędem grafu ${\displaystyle G}$ i oznaczamy przez ${\displaystyle |V|,}$ a moc zbioru ${\displaystyle E}$ nazywamy jego rozmiarem i oznaczamy przez ${\displaystyle \|G\|.}$ Niekiedy w definicjach krawędzi zakłada się, że kierunek ruchu pomiędzy nimi jest określany przez kolejny zbiór. W takim podejściu mamy podstawowy graf nieskierowany oraz zbiór określający, które z kierunków ruchu są w nim dozwolone. W efekcie powstaje struktura równoważna dla grafu skierowanego.

Zobacz też

• acykliczny graf skierowany – tzw. DAG
• graf eulerowski
• graf hamiltonowski
• graf nieskierowany
• teoria grafów

Przypisy