Vrchol alebo star?ie uzol ako pojem teorie grafov znamena akysi bod v grafe , ktory obvykle znazor?uje uzol ?i sidlo. V?etky vrcholy grafu G = (V, H) su zoskupene v mno?ine V .

Okolim vrcholu u nazyvame graf (resp. digraf) O(u) , ktoreho mno?ina vrcholov pozostava z druhych koncov hran incidentnych s vrcholom u a samotneho vrchola u . Hranova mno?ina okolia vrcholu pozostava zo v?etkych hran incidentnych s tymto vrcholom.

Ak je G = (V, H) digraf, potom doprednou hviezdou vrcholu u je graf F(u) , ktory je podgrafom okolia O(u) obsahujucim iba hrany, v ktorych je u za?iato?nym vrcholom a ich kone?ne vrcholy. Analogicky definicia spatnej hviezdy vrcholu u znie, ?e je to graf B(u) , ktory je podgrafom okolia O(u) , obsahujucim iba hrany, v ktorych je u koncovym vrcholom a ich za?iato?ne vrcholy.

Stupe? vrchola deg(u) v grafe G = (V, H) je rovny po?tu hran incidentnych s vrcholom u . Vstupnym (resp. vystupnym) stup?om sa potom rozumie po?et hran, ktore do vrchola v vstupuju (resp. z neho vychadzaju).

Vlastnosti [ upravi? | upravi? zdroj ]

• Su?et stup?ov v?etkych vrcholov grafu sa rovna dvojnasobku po?tu hran.

${\displaystyle \sum _{u\in V}deg(u)=2.|H|}$

Dokaz vety [ upravi? | upravi? zdroj ]

Budeme postupova? indukciou vzh?adom na ?islo ${\displaystyle q}$ (po?et hran). Ak ${\displaystyle q=0}$, tak v ${\displaystyle G}$ neexistuje hrana, preto v?etky vrcholy su izolovane. V tomto pripade tvrdenie vety je zrejme pravdive. Teraz predpokladajme, ?e tvrdenie je pravdive pre v?etky grafy, v ktorych ${\displaystyle q=n-1}$. Zoberme ?ubovolny graf ${\displaystyle G}$ o ${\displaystyle n}$ hranach. Vynechajme z ${\displaystyle G}$ jednu hranu ${\displaystyle ab}$; dostaneme graf ${\displaystyle G'}$ o ${\displaystyle n-1}$ hranach, ktoreho su?et stup?ov vrcholov je (pod?a induk?neho predpokladu) rovny ${\displaystyle 2(n-1)}$. Ak v?ak pridame naspa? hranu ${\displaystyle ab}$, zva??i sa o jednotku stupe? vrchola ${\displaystyle a}$ aj ${\displaystyle b}$, teda celkovy su?et vrcholov sa zva??i o 2 a bude sa rovna? ${\displaystyle 2n}$. Tym je dokaz ukon?eny.

Dosledok vety [ upravi? | upravi? zdroj ]

Z uvedenej vety a jej dokazu bezprostredne vyplyva, ?e v kone?nom neorientovanom grafe je po?et vrcholov neparneho stup?a parne ?islo. ?pecialny pripad tohto dosledku je fakt, ?e neexistuje graf, ktory by obsahoval jediny vrchol neparneho stup?a). Dokaz je zalo?eny na fakte, ?e su?et neparneho po?tu neparnych ?isel je neparne ?islo.

• Po?et vrcholov neparneho stup?a v ?ubovo?nom grafe je parny.
• Ak G = (V, H) je netrivialny graf, potom obsahuje aspo? dva vrcholy rovnakeho stup?a.

Literatura [ upravi? | upravi? zdroj ]

• Znam, ?: Kombinatorika a teoria grafov. Bratislava, Matematicko-fyzikalna fakulta Univerzity Komenskeho. 1982, s. 37