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

  • množica vozlišč
  • 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.
Usmerjeni graf
Directed.svg
Usmerjeni graf.
Povezavev - 1
Kromatično število2

Lok, ki je usmerjen od proti , se označuje z . V tem primeru se imenuje glava, pa je rep.

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

Temeljni grafUredi

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

Vhodna in izhodna stopnjaUredi

Vhodna stopnja (oznaka  ) je število povezav, ki se končajo v  . Izhodna stopnja (oznaka  ) je število povezav, ki se pričnejo v  . Vozlišče z   se imenuje izvor, vozlišče z  , pa se imenuje ponor.

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

 

Kadar za vsako vozlišče   velja  , se graf imenuje uravnoteženi graf.

 
Usmerjeni neciklični graf
 
Turnir s štirimi vozlišči.

Vrste usmerjenih grafovUredi

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 povezaveUredi