Stopnja grafa

Graf z označenimi stopnjami v točkah. Prikazan je tudi graf s stopnjo 0.

Stopnja (tudi valenca grafa) (oznaka $\mathrm{deg}(v)$) točke je v teoriji grafov število povezav, ki so vezane na točko. Pri tem se zanke štejejo dvakrat. Stopnjo točke se označuje z $\mathrm{deg}(\nu )$. Največja stopnja točke grafa $G$ je označena z $\mathrm{\Delta }(G)$. Najmanjša stopnja točke grafa je označena z $\delta (G)$.

Lema o rokovanju

Lema o rokovanju pravi, da je za graf $G(V,E)$ dvojno število povezav enako vsoti vseh stopenj točk v grafu. To se zapiše kot:

$\sum _{v\in V}\mathrm{deg}(v)=2|E|,$

kjer je:

• $\mathrm{deg}(v)$ stopnja točke $v$
• $|E|$ število povezav v grafu.

Neusmerjeni grafi

V neusmerjenih grafih je stopnja $\mathrm{deg}$ v grafih brez večkratnih povezav enaka številu sosedov točk, v grafih, ki vsebujejo večkratne povezave, pa je v vsaki točki enaka vsoti števila večkratnih povezav, ki so povezane s točko (so incidentne s točko).

Usmerjeni grafi

Usmerjeni graf z vpisanimi stopnjami za točke: (vhodna stopnja, izhodna stopnja).

V usmerjenem grafu ima vsaka povezava začetek in konec. Zaradi tega se lahko za vsako točko določi vhodno stopnjo (oznaka ${\mathrm{deg}}^{-}(x)$) in izhodno stopnjo (oznaka ${\mathrm{deg}}^{+}(x)$). Če se obravnava graf z večkratnimi povezavami, je:

• vhodna stopnja ${\mathrm{deg}}^{-}(x)$ v grafih brez večkratnih povezav enaka številu sosednjih vozlišč.
• v grafih z večkratnimi povezavami v vsaki točki vhodna stopnja enaka vsoti števila vseh vstopajočih povezav.
• izhodna stopnja v grafih brez večkratnih povezav enaka številu sosednjih točk.
• izhodna stopnja v grafih z večkratnimi povezavami v vsaki točki enaka vsoti števila vseh izstopajočih povezav.

Posebni primeri

Neusmerjeni graf z listi, ki pripadajo točkam 4, 5, 6, 7, 10, 11 in 12

• Točka, ki ima stopnjo enako 0, se imenuje izolirana točka.
• Točka, ki ima stopnjo 1, se imenuje list.

Nekatere značilnosti

• Če ima vsaka točka grafa enako stopnjo, je graf k-regularen. V tem primeru ima graf stopnjo k.
• Usmerjeni graf je psevdogozd, če in samo če ima vsaka točka izhodno stopnjo največ 1. Funkcionalno je graf posebni primer psevdogozda, če ima vsaka točka izhodno stopnjo 1.
• Neusmerjeni povezani graf ima Eulerjevo pot, če in samo, če ima 0 ali 2 točki s liho stopnjo. Kadar nima vozlišč z liho stopnjo je Eulerjeva pot Eulerjev krog.
• Po Brooksovem izreku je v vsakem povezanem neusmerjenem grafu z največjo stopnjo $\mathrm{\Delta }$ kromatično število grafa največ enako $\mathrm{\Delta }$, razen, če je graf klika ali sodi cikel, v tem primeru pa je kromatično število enako $\mathrm{\Delta }+1$.
• Po Vizingovem izreku ima vsak graf kromatično število enako $\mathrm{\Delta }+1$.
• k-izrojen je graf v katerem ima vsak podgraf točko s stopnjo največ $k$.

Zunanje povezave

• Osnove teorije grafov Predloga:Webarchive Predloga:Ikona sl
• Uvod v teorijo grafov Predloga:Ikona sl
• Stopnja (teorija grafov) – video Predloga:Ikona en