Graf skierowany
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5f/Kondenzace_orientovan%C3%A9ho_grafu.svg/200px-Kondenzace_orientovan%C3%A9ho_grafu.svg.png)
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 to uporządkowana para spełniająca następujące warunki:
- (vertex) to zbiór wierzchołków,
- to zbiór uporządkowanych par nazywanych krawędziami skierowanymi, który jest podzbiorem iloczynu kartezjańskiego
- Krawędź:
- rozumiana jest jako skierowana z wierzchołka do
Alternatywna definicja zakłada, że graf skierowany definiuje dwójka: gdzie jest dowolnym, niepustym zbiorem zwanym zbiorem wierzchołków, natomiast jest podzbiorem iloczynu kartezjańskiego czyli:
Elementy rodziny są nazwane krawędziami grafu. Krawędź można w skrócie oznaczać Mówimy, że krawędź łączy wierzchołki i
Moc zbioru nazywamy rzędem grafu i oznaczamy przez a moc zbioru nazywamy jego rozmiarem i oznaczamy przez 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
- ↑ John E. Hopcroft, Jeffrey D. Ullman: Wprowadzenie do teorii automatów, języków i obliczeń. Warszawa: Wydawnictwo Naukowe PWN, 2003. ISBN 83-01-14090-9.
- ↑ graf, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2022-03-10] .
- ↑ Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 25. ISBN 0-387-95014-1.
- p
- d
- e
Najważniejsze pojęcia |
więcej... |
---|---|
Wybrane klasy grafów | |
Algorytmy grafowe | |
problemy grafowe | |
Inne zagadnienia |
- Britannica: topic/directed-graph