Irányított gráf

Bejövő fokszám ((  )): Egy csúcsra érkező élek száma.
Kimenő fokszám ((  )): Egy csúcsból induló élek száma.
Út: Csúcsok sorozata, ahol minden csúcsot egy irányított él köt össze a következő csúccsal.
Kör: Olyan út, amely ugyanabba a csúcsba tér vissza, ahonnan indult.

Sablon:Label Legyen $A$ egy halmaz, $ρ$ egy reláció $A$ -n. Ekkor az $(A, ρ)$ rendezett párt irányított gráfnak hívjuk. Az $A$ halmaz elemeit a gráf pontjainak, a $ρ$ relációt pedig a gráf éleinek nevezzük. Egy $(a, b) \in ρ$ él esetében az $a$ pontot az él kezdőpontjának, a $b$ pontot pedig az él végpontjának hívjuk. Egy $(a, a)$ élt hurokélnek nevezünk.

Az irányított gráf (digraph, directed graph) egy speciális gráf, ahol az élek (kapcsolatok) irányítottak, tehát minden él egy rendezett pár ( (u, v) ), ahol az él csak ( u )-ból ( v )-be vezet, és nem fordítva (kivéve, ha egy másik él külön ezt is definiálja). Az irányított gráfokat gyakran használják olyan rendszerek modellezésére, ahol a kapcsolatok aszimmetrikusak.

Formális definíció

Egy irányított gráf ( G ) egy rendezett pár: [ G = (V, E) ] ahol: - ( V ): a gráf csúcsainak (pontjainak) halmaza, - ( E ): rendezett élek halmaza (( E V V )).

Példa

Egy irányított gráf ( G = (V, E) ), ahol: - ( V = {A, B, C} ), - ( E = {(A, B), (B, C), (C, A)} ).

Ez azt jelenti, hogy van egy él ( A )-ból ( B )-be, egy él ( B )-ből ( C )-be, és egy él ( C )-ből ( A )-ba.