Vrchol (teória grafov)

Z Wikipédie

Vrchol ako pojem teórie grafov znamená akýsi bod v grafe, ktorý obvykle znázorňuje uzol či sídlo. Všetky vrcholy grafu G = (V, H) sú zoskupené v množine V.

Okolím vrcholu u nazývame graf (resp. digraf) O(u), ktorého množina vrcholov pozostáva z druhých koncov hrán incidentných s vrcholom u a samotného vrchola u. Hranová množina okolia vrcholu pozostáva zo všetkých hrán incidentných s týmto vrcholom.

Ak je G = (V, H) digraf, potom doprednou hviezdou vrcholu u je graf F(u), ktorý je podgrafom okolia O(u) obsahujúcim iba hrany, v ktorých je u začiatočným vrcholom a ich konečné vrcholy. Analogicky definícia spätnej hviezdy vrcholu u znie, že je to graf B(u), ktorý je podgrafom okolia O(u), obsahujúcim iba hrany, v ktorých je u koncovým vrcholom a ich začiatočné vrcholy.

Stupeň vrchola deg(u) v grafe G = (V, H) je rovný počtu hrán incidentných s vrcholom u. Vstupným (resp. výstupným) stupňom sa potom rozumie počet hrán, ktoré do vrchola v vstupujú (resp. z neho vychádzajú).

[úprava] Vlastnosti

  • Súčet stupňov všetkých vrcholov grafu sa rovná dvojnásobku počtu hrán.
\sum_{u \in V} deg(u) = 2.|H|
  • Počet vrcholov nepárneho stupňa v ľubovoľnom grafe je párny.
  • Ak G = (V, H) je netriviálny graf, potom obsahuje aspoň dva vrcholy rovnakého stupňa.