Własności
Grafem skierowanym (digrafem) $D$ nazywamy graf składający się z niepustego i skończonego zbioru wierzchołków $V(D)$ oraz skończonej rodziny łuków $A(D)$ uporządkowanych par elementów zbioru $V(D)$. W grafie skierowanym $D$ $zw$ oznacza łuk poprowadzony z wierzchołka $z$ do wierzchołka $w$, gdzie kolejność wierzchołków łuku $zw$ oznaczona jest za pomocą strzałki. Czyli łuki $zw$ i $wz$ nie są łukami wielokrotnymi, ponieważ tutaj uwzględniamy pewną kolejność. Jeśli z digrafu $D$ usuniemy "strzałki" (czyli zastąpimy każdy łuk postaci $zw$ krawędzią $zw$) to powstały graf będziemy nazywać szkieletem digrafu.
W grafach skierowanych możemy przechodzić przez łuki tylko w kierunku zgodnym z oznaczeniem. Na przykład łuk $zw$ można przejść tylko od $z$ do $w$. Odwrotne przejście jest niedopuszczalne w tym przypadku.
Definicje
Większość definicji związanych z grafami skierowanymi będzie miała podobą formę to tych, które dotąd poznaliśmy. Digraf $D$ jest prosty, jeśli wszystkie łuki są różne i $D$ nie posiada pętli. Dwa digrafy są izomorficzne, jeśli istnieje izomorfizm szkieletów zachowujący kolejność wierzchołków.
Dwa wierzchołki $v$ i $w$ są sąsiednie, jeśli w rodzinie $A(D)$ istnieje łuk postaci $vw$ lub $wv$. Wtedy oba wierzchołki są incydentne z tym łukiem. Oprócz tego wszystkie defnicje dotyczące grafów nieskierowanych można w naturalny sposób uogólnić na przypadek digrafów, jeśli nie będzie to prowadziło do żadnych nieporozumień.
Poruszanie się w grafie skierowanym
Stopniem wyjściowym wierzchołka $v$ digrafu $D$ nazywamy liczbę łuków poprowadzonych z wierzchołka $v$. Stopień wyjściowy wierzcholka $v$ oznaczamy symbolem $\mathrm{outdeg}(v)$. Analogicznie, stopieniem wejściowym wierzchołka $v$ w digrafie $D$ będzie liczba łuków poprowadzonych do wierzchołka $v$, który oznaczamy symbolem $\mathrm{indeg}(v)$.
Wierzchołek digrafu $D$ mający stopień wyjściowy równy $0$ nazywamy ujściem digrafu, a wierzchołek digrafu $D$ mający stopień wejściowy równy $0$ nazywamy żródłem digrafu $D$.
Spójnosć
Graf nazywamy silnie spójnym jeśli dla dowolnych dwóch wierzchłków $v$ i $w$ istnieje droga z $v$ do $w$. Grafem orientowalnym $G$ jest graf nieskierowany, którego można skierować w taki sposób, by otrzymany graf skierowany stał się silnie spójny. O warunku koniecznym i wystarczającym na to, aby dany graf stał się grafem orientowalnym mówi twierdzenie sformułowane przez H. E. Robbinsa.
- Niech $G$ będzie grafem spójnym. Wówczas graf $G$ jest orientowalny wtedy i tylko wtedy, gdy każda krawędź $G$ jest zawarta w co najmniej jednym cyklu.
Digrafy eulerowskie
Digraf spójny $D$ nazywamy digrafem eulerowskim, jeśli istnieje zamknięta ścieżka zawierająca każdy łuk digrafu $D$. Taką ścieżkę nazywamy ścieżką eulerowską. Digraf spójny $D$ nazwiemy półeulerowskim jeśli nie jest grafem eulerowskim, ale istnieje ścieżka zawierająca każdy łuk $D$. Digraf, którego szkielet jest grafem eulerowskim, nie musi być grafem eulerowskim
Warunkiem koniecznym i wystarczającym na to, aby digraf spójny był eulerowski jest to, aby ten digraf był silnie spójny. Oprócz tego kolejny warunek jest zawarty w podstawowym twierdzeniu o digrafach eulerowskich.
- Digraf spójny jest digrafem eulerowskim wtedy i tylko wtedy, gdy dla każego wierzchołka $v$ digrafu $D$ zachodzi równość $\mathrm{outdeg}(v) = \mathrm{indeg}(v)$.
Digrafy hamiltonowskie
Digraf $D$ nazywamy hamiltonowskim, jeśli istnieje cykl zawierający każdy wierzchołek. Digraf nie będący digrafem hamiltonowskim, w którym występuje droga przechodząca przez każdy wierzchołek, nazywamy digrafem półhamiltonowskim.
Zname jest ważne twierdzenie, które pomaga określić czy dany digraf jest hamiltonowski. Twierdzenie to jest właściwie uogólnieniem twierdzenia Diraca dla grafów nieskierowanych.
- Niech $D$ będzie digrafem silnie spójnym mającym $n$ wierzchołków. Jeśli $\mathrm{outdeg}(v) \ge n/2$ oraz $\mathrm{indeg}(v) \ge n/2$ dla każdego wierzchołka $v$, to digraf $D$ jest hamiltonowski.
