Usmerjeni graf

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

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 $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.