Usmjereni Graf

To je onaj graf kojemu je svaka grana usmjerena odnosno orijentirana.

Graf je u gruboj definiciji skup objekata: vrhova, točaka ili čvorova koje povezuju bridovi odnosno crte (linije). Brid spaja dva čvora i to je odnos koji definira graf. Ako vrhove povezuje brid, grafove se prikazuje crtanjem točaka za svaki vrh i povlačenjem luka između dvaju vrhova.

Skup bridova u grafu obično se označava s E(G). Bridovi mogu biti usmjereni ili ne. Ako su grafu svi bridovi usmjereni, tad je graf usmjereni graf (digraf), u suprotnom je neusmjereni graf.

Za pravi graf uzima se da je neusmjeren i kod njega crta od točka u do točke v istovjetna je crti od v do točke u. Kod usmjerenog grafa ta dva smjera nisu istovjetna i smatra ih se različitim bridovima (lukovima). Brid kod usmjerenih grafova može biti usmjeren od jednog vrha prema drugome.

Jedan od uvjeta da graf bude jednostavan jest da ne smije biti usmjeren.

Usmjerenim grafom može se riješiti problem kineskog poštara i problem trgovačkog putnika.