From Wikipedia, the free encyclopedia
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 pravi, da je za graf dvojno število povezav enako vsoti vseh stopenj točk v grafu. To se zapiše kot:
kjer je:
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).
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:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.