Graf skierowany – Wikipedia, wolna encyklopedia Przejdź do zawartości

Graf skierowany

Z Wikipedii, wolnej encyklopedii
Przykład grafu skierowanego

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

[edytuj | edytuj kod]

Matematyczna definicja zakłada, że graf skierowany to uporządkowana para spełniająca następujące warunki:

  1. (vertex) to zbiór wierzchołków,
  2. to zbiór uporządkowanych par nazywanych krawędziami skierowanymi, który jest podzbiorem iloczynu kartezjańskiego
  3. 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ż

[edytuj | edytuj kod]

Przypisy

[edytuj | edytuj kod]
  1. 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.
  2. graf, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2022-03-10].
  3. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 25. ISBN 0-387-95014-1.

Linki zewnętrzne

[edytuj | edytuj kod]
  • publikacja w otwartym dostępie – możesz ją przeczytać Graph, oriented (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-10-05].