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.

- 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.