Graf skierowany


Graf skierowany w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania Przykład grafu skierowanego

Graf skierowany (digraf, od ang. directed graph, sgraf[1], 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)[2].

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

  1. V {\displaystyle V} (vertex) to zbiór wierzchołków,
  2. A {\displaystyle A} to zbiór uporządkowanych par nazywanych krawędziami skierowanymi, który jest podzbiorem iloczynu kartezjańskiego V × V {\displaystyle V\times V}
  3. Krawędź:
e = ( a , b ) {\displaystyle e=(a,b)} rozumiana jest jako skierowana z wierzchołka a {\displaystyle a} do b . {\displaystyle b.}

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

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

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

Moc zbioru V {\displaystyle V} nazywamy rzędem grafu G {\displaystyle G} i oznaczamy przez | V | , {\displaystyle |V|,} a moc zbioru E {\displaystyle E} nazywamy jego rozmiarem i oznaczamy przez G . {\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ż | edytuj kod

Przypisy | 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. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 25. ISBN 0-387-95014-1.
Na podstawie artykułu: "Graf skierowany" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy