Tekst źródłowy strony Graf skierowany

[[Plik:Kondenzace orientovaného grafu.svg|thumb|200px|Przykład grafu skierowanego]]

'''Graf skierowany''', '''sgraf'''<ref>{{cytuj książkę |nazwisko = Hopcroft |imię = John E. |nazwisko2 = Ullman |imię2 = Jeffrey D. |tytuł = Wprowadzenie do teorii automatów, języków i obliczeń |wydawca = Wydawnictwo Naukowe PWN |miejsce = Warszawa |rok = 2003 |isbn = 83-01-14090-9}}</ref>, '''graf zorientowany'''<ref name="epwn">{{Encyklopedia PWN | id = 3907380 | tytuł = graf | data dostępu = 2022-03-10 }}</ref> '''digraf''', od [[Język angielski|ang.]] ''directed graph'', '''DG''' – rodzaj [[graf (matematyka)|grafu]] rozważanego w [[teoria grafów|teorii grafów]]. Graf skierowany definiuje się jako [[para uporządkowana|uporządkowaną parę]] [[zbiór|zbiorów]]. Pierwszy z nich zawiera [[Wierzchołek (teoria grafów)|wierzchołki]] grafu, a drugi składa się z [[Krawędź grafu|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ą, [[Zwrot wektora|zwrotem]])<ref>{{Cytuj książkę |nazwisko = Diestel |imię = Reinhard |tytuł = Graph Theory |url=http://diestel-graph-theory.com/index.html |miejsce = Nowy Jork |rok = 2000 |strony = 25| isbn= 0-387-95014-1}}</ref>.

== Definicja formalna ==
Matematyczna definicja zakłada, że graf skierowany <math>G</math> to uporządkowana para <math>G := \langle V,A\rangle</math> spełniająca następujące warunki:
# <math>V</math> (''vertex'') to zbiór wierzchołków,
# <math>A</math> to zbiór uporządkowanych par nazywanych krawędziami skierowanymi, który jest podzbiorem [[iloczyn kartezjański|iloczynu kartezjańskiego]] <math>V \times V</math>
# Krawędź:
:: <math>e=(a,b)</math>
:: rozumiana jest jako skierowana z wierzchołka <math>a</math> do <math>b.</math>

Alternatywna definicja zakłada, że graf skierowany <math>G</math> definiuje dwójka: <math>G = \langle V;E\rangle,</math> gdzie <math>V</math> jest dowolnym, niepustym [[zbiór|zbiorem]] zwanym '''zbiorem wierzchołków''', natomiast <math>E</math> jest [[podzbiór|podzbiorem]] [[iloczyn kartezjański|iloczynu kartezjańskiego]] <math>V \times V,</math> czyli:
# <math>V \neq \varnothing,</math>
# <math>E \subseteq P_2(V).</math>

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

[[Moc zbioru]] <math>V</math> nazywamy '''rzędem grafu''' <math>G</math> i oznaczamy przez <math>|V|,</math> a moc zbioru <math>E</math> nazywamy jego '''rozmiarem''' i oznaczamy przez <math>\|G\|.</math> 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ż ==
* [[Skierowany graf acykliczny|acykliczny graf skierowany]] – tzw. DAG
* [[graf eulerowski]]
* [[graf hamiltonowski]]
* [[Graf (matematyka)|graf nieskierowany]]
* [[teoria grafów]]

== Przypisy ==
{{Przypisy}}

== Linki zewnętrzne ==
* {{otwarty dostęp}} ''[https://encyclopediaofmath.org/wiki/Graph,_oriented Graph, oriented]'' {{lang|en}}, Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-10-05].

{{Teoria grafów}}

{{Kontrola autorytatywna}}

[[Kategoria:Grafy|skierowany]]