Prijeđi na sadržaj

Usmjereni graf

Izvor: Wikipedija

Usmjereni graf (digraf), vrsta grafa iz teorije grafova.

To je onaj graf kojemu je svaka grana usmjerena odnosno orijentirana.[1]

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.[2]

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.[2]

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.[2]

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

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

Izvori

[uredi | uredi kôd]
  1. Sveučilište u Zagrebu, Geodetski fakultet, Zavod za kartografiju i fotogrametrijuArhivirana inačica izvorne stranice od 19. kolovoza 2019. (Wayback Machine) Nada Vučetić: OSNOVE GEOINFORMATIKE: Neki pojmovi i definicije iz teorije grafova, Osnove teorije skupova (pristupljeno 8. siječnja 2020.)
  2. a b c d e math.e, hrvatski matematički elektronički časopis Maja Fošner i Tomaž Kramberger: Teorija grafova i logistika br. 14, ISSN ISSN 1334-6083 (pristupljeno 23. prosinca 2019.)