Usmerjeni graf

Usmerjeni graf ali digraf (di izhaja iz angleške besede directed, kar pomeni usmerjeno) je par $G=(V,A)$, kjer je:

• $V$ množica vozlišč
• $A$ urejeni par vozlišč, ki se imenujejo loki ali usmerjene povezave, včasih se imenujejo tudi kar puščice. Nekateri usmerjene grafe imenujejo tudi enostavni digrafi, da ga tako razlikujejo od usmerjenega multigrafa. V multigrafu povezave tvorijo večkratne množice in ne množice urejenih parov vozlišč. V enostavnem grafu so dovoljene tudi zanke. To so povezave, povezujejo vozlišča s samim seboj.

Lok, ki je usmerjen od $x$ proti $y$, se označuje z $e=(x,y)$. V tem primeru se $x$ imenuje glava, $y$ pa je rep.

Kadar se lahko neposredno pride od prvega ($x$) do drugega ($y$) zaporednega vozlišča, se vozlišče $x$ imenuje predhodnik, vozlišče $y$ pa je naslednik. Lok, ki ima obratno smer, je obrnjeni lok. Graf se imenuje simetričen, če grafu $G$ pripadajo tudi vsi obrnjeni loki grafa.

Temeljni graf

Temeljni graf se dobi, če se v digrafu vse usmerjene povezave nadomesti z neusmerjenimi (odstrani se vse usmeritve).

Vhodna in izhodna stopnja

Vhodna stopnja (oznaka $de{g}^{-}(x)$) je število povezav, ki se končajo v $x$. Izhodna stopnja (oznaka $de{g}^{+}(x)$) je število povezav, ki se pričnejo v $x$. Vozlišče z $de{g}^{-}(v)=0$ se imenuje izvor, vozlišče z $de{g}^{+}(v)=0$, pa se imenuje ponor.

Za vhodno in izhodno stopnjo (če je v grafu končno število vozlišč) velja:

$\sum _{v\in V}{\mathrm{deg}}^{+}(v)=\sum _{v\in V}{\mathrm{deg}}^{-}(v).$

Kadar za vsako vozlišče $vϵV$ velja ${\mathrm{deg}}^{+}(v)={\mathrm{deg}}^{-}(v)$, se graf imenuje uravnoteženi graf.

Usmerjeni neciklični graf

Turnir s štirimi vozlišči.

Vrste usmerjenih grafov

Usmerjeni neciklični graf je graf, ki nima usmerjenih ciklov.

Turnir je orientirani graf, ki se ga dobi tako, da se izbere smer povezave v neusmerjenem polnem grafu.

Zunanje povezave

• Usmerjeni grafiPredloga:Slepa povezava Predloga:Ikona sl
• Usmerjeni grafi Predloga:Ikona en
• Poglavje 10 – usmerjeni grafi Predloga:Webarchive Predloga:Ikona en
• Predloga:MathWorld
• Usmerjeni graf Predloga:Webarchive na PlanetMath Predloga:Ikona en
• Značilnosti digrafov Predloga:Ikona en