Stopnja grafa

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

Stopnja (tudi valenca grafa) (oznaka ) 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 .

Lema o rokovanju[uredi | uredi kodo]

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

kjer je:

  • stopnja točke
  • število povezav v grafu.

Neusmerjeni grafi[uredi | uredi kodo]

V neusmerjenih grafih je stopnja 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[uredi | uredi kodo]

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 ) in izhodno stopnjo (oznaka ). Če se obravnava graf z večkratnimi povezavami, je:

  • vhodna stopnja 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[uredi | uredi kodo]

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

  • č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 sodo 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 kromatično število grafa največ enako , razen, če je graf klika ali sodi cikel, v tem primeru pa je kromatično število enako .
  • po Vizingovem izreku ima vsak graf kromatično število enako .
  • k-izrojen je graf v katerem ima vsak podgraf točko s stopnjo največ .

Zunanje povezave[uredi | uredi kodo]