Usmerjeni graf

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Usmerjeni graf
Directed.svg
Usmerjeni graf.
Povezave v - 1
Kromatično število 2

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.

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 graf[uredi | uredi kodo]

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

Vhodna in izhodna stopnja[uredi | uredi kodo]

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 grafov[uredi | uredi kodo]

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 povezave[uredi | uredi kodo]