Stopnja grafa

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Graf z označenimi stopnjami v vozliščih. Prikazan je tudi graf s stopnjo 0.

Stopnja (tudi valenca grafa) (oznaka  \deg (v) \,) vozlišča je v teoriji grafov število povezav, ki so vezane na vozlišče. Pri tem se zanke štejejo dvakrat. Stopnjo vozlišča označujemo z  deg(\nu) \,.

Lema o rokovanju[uredi | uredi kodo]

Lema o rokovanju pravi, da je za graf  G(V, E) \, dvojno število povezav enako vsoti vseh stopenj vozlišč v grafu. To zapišemo kot

\sum_{v \in V} \deg(v) = 2|E|\, .

kjer je

  •  \deg(v) \, stopnja vozlišča  v \,
  •  |E| \, število povezav v grafu.

Neusmerjeni grafi[uredi | uredi kodo]

V neusmerjenih grafih je stopnja  \deg \, enaka v grafih brez večkratnih povezav enaka številu sosedov vozlišča, v grafih, ki pa vsebujejo večkratne povezave, pa je v vsakem vozlišču enaka vsoti števila večkratnih povezav, ki so povezane z vozliščem (so incidentne z vozliščem).

Usmerjeni grafi[uredi | uredi kodo]

Usmerjeni grafz vpisanimi stopnjami za vozlišča: (vhodna stopnja, izhodna stopnja).

V usmerjenem grafu ima vsaka povezava začetek in konec. Zaradi tega lahko za vsako vozlišče določimo vhodno stopnjo (oznaka oznaka  deg^{+}(x) \,) in izhodno stopnjo (oznaka  deg^{+}(x) \,. Če pa imamo graf z večkratnimi povezavami pa je:

  • vhodna stopnja  deg^{-}(x) \, je v grafih brez večkratnih povezav enaka številu sosednjih vozlišč
  • v grafih z večkratnimi povezavami je v vsakem vozlišču vhodna stopnja enaka vsoti števila vseh vstopajočih povezav.
  • izhodna stopnja v grafih brez večkratnih povezav je enaka številu sosednjih vozlišč
  • izhodna stopnja v grafih z večkratnimi povezavami je v vsakem vozlišču izhodna stopnja enaka vsoti števila vseh izstopajočih povezav.

Posebni primeri[uredi | uredi kodo]

Neusmerjeni graf , z listi, ki pripadajo vozliščem 4, 5, 6, 7, 10, 11 in 12
  • Vozlišče, ki ima stopnjo enako 0, imenujemo izolirano vozlišče.
  • Vozlišče, ki ima stopnjo 1, se imenuje list

Nekatere lastnosti[uredi | uredi kodo]

  • Če ima vsako vozlišče grafa enako stopnjo, pravimo, da je graf k-regularni. V tem primeru pravimo tudi, da ima graf stopnjo k.
  • Usmerjeni graf je psevdogozd, če in samo, če ima vsako vozlišče izhodno stopnjo največ 1. Funkcionalno graf je posebni primer psevdogozda, če ima vsako vozlišče izhodno stopnjo 1.
  • Neusmerjeni povezani graf ima Eulerjevo pot, če in samo, če ima 0 ali 2 vozlišči z neparno stopnjo. Kadar ima nima vozlišč z neparno stopnjo je Eulerjeva pot Eulerjev krog.
  • Po Brooksovem izreku je v vsakem povezanem neusmerjenem grafu z največjo stopnjo  \delta \,, kromatično število grafa največ enako  \delta \, , razen, če je graf klika ali neparni cikel, v tem primeru pa je kromatično število enako  \delta + 1 \,.
  • Po izreku Vizinga ima vsak graf kromatično število enako  \delta + 1 \,.
  • k-degenerirani je graf v katerem ima vsak podgraf vozlišče s stopnjo največ  k \,.

Zunanje povezave[uredi | uredi kodo]