Usmerjeni graf

Usmerjeni graf
Usmerjeni graf.
Povezave	v - 1
Kromatično število	2

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 \,$ urejen par vozlišč, ki jih imenujemo loki ali usmerjene povezave, včasih jim pravimo 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 \,$ označujemo z $e = (x, y) \,$. V tem primeru se $x \,$ imenuje glava in $y \,$ je rep.

Kadar lahko neposredno pridemo od prvega ($x \,$) do drugega ($y \,$) zaporednega vozlišča, pravimo, da je vozlišče $x \,$ 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 dobimo, če v digrafu vse usmerjene povezave nadomestimo z neusmerjenimi (odstranimo vse usmeritve).

Vhodna in izhodna stopnja

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

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

$\sum_{v \in V} \deg^+(v) = \sum_{v \in V} \deg^-(v) \,$.

Kadar za vsako vozlišče $v \epsilon V \,$ velja $\deg^+(v) = \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 ga dobimo tako, da izberemo smer povezave v neusmerjenem polnem grafu.

Zunanje povezave

• Usmerjeni grafi (v slovenščini)
• Usmerjeni grafi (v angleščini)
• Poglavje 10 – usmerjeni grafi (v angleščini)
• Usmerjeni graf na MathWorld (v angleščini)
• Usmerjeni graf na PlanetMath (v angleščini)
• Značilnosti digrafov (v angleščini)