Okolí a stupeň

  • Nechť je graf a jeho vrchol
    • Stupeň = počet hran obsahující vrchol
    • (Otevřené) okolí = množina všech sousedů (sousedních vrcholů) vrcholu
    • Uzavřené okolí (obsahuje i sám sebe)
  • Platí, že stupeň se rovná počtu vrcholů v okolí,

Vstupní stupeň

  • Kolik hran tam vchází
  • Značíme
  • Vrcholům se stupněm 0 se říká zdroje

Výstupní stupeň

  • Kolik hran vychází
  • Značíme
  • Vrcholům se stupněm 0 se říká stoky

Regulární graf

  • Graf je -regulární, pokud stupeň každého jeho vrcholu je (například 2-regulární, 3-regulární ...)
  • Graf je regulární, pokud je -regulární pro nějaké

Izolovaný vrchol

  • Vrchol stupně 0, tedy
  • Nemá žádné sousedy

Princip sudosti

  • Pro každý graf platí:
  • tj. součet všech stupňů se rovná 2× počet hran
  • Důkaz: Posčítáme-li stupně všech vrcholů, započítáme každou hranu přesně dvakrát, což dává součet
Důsledky
  • V každém grafu je počet vrcholů lichého stupně sudý
  • Každý regulární graf lichého stupně musí mít sudý počet vrcholů.

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25