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  G = (V, A) \,, kjer je

  •  V \, množica vozlišč
  •  A \, urejen par vozlišč, ki jih imenujemo loki ali usmerjene povezave, včasih jim pravimo 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  x \, proti  y \, označujemo z  e = (x, y) \,. V tem primeru se  x \, imenuje glava in  y \, je rep.

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

Temeljni graf[uredi | uredi kodo]

Temeljni graf dobimo, če v digrafu vse usmerjene povezave nadomestimo z neusmerjenimi (odstranimo vse usmeritve).

Vhodna in izhodna stopnja[uredi | uredi kodo]

Vhodna stopnja (oznaka  deg^{-}(x) \,) je število povezav, ki se končajo v  x \,. Izhodna stopnja (oznaka  deg^{+}(x) \,) je število povezav, ki se pričnejo v  x \,. Vozlišče z  deg^{-}(v) = 0 \, se imenuje izvor, vozlišče z  deg^{+}(v) = 0 \,, pa se imenuje ponor.

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

\sum_{v \in V} \deg^+(v) = \sum_{v \in V} \deg^-(v) \, .

Kadar za vsako vozlišče  v \epsilon V \, velja \deg^+(v) = \deg^-(v), 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 ga dobimo tako, da izberemo smer povezave v neusmerjenem polnem grafu.

Zunanje povezave[uredi | uredi kodo]