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 ${\displaystyle G=(V,A)\,}$, kjer je:

• ${\displaystyle V\,}$ množica vozlišč
• ${\displaystyle 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 ${\displaystyle x\,}$ proti ${\displaystyle y\,}$, se označuje z ${\displaystyle e=(x,y)\,}$. V tem primeru se ${\displaystyle x\,}$ imenuje glava, ${\displaystyle y\,}$ pa je rep.

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