A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Vrchol alebo staršie uzol 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ú).
Vlastnosti
- Súčet stupňov všetkých vrcholov grafu sa rovná dvojnásobku počtu hrán.
Dôkaz vety
Budeme postupovať indukciou vzhľadom na číslo (počet hrán). Ak , tak v neexistuje hrana, preto všetky vrcholy sú izolované. V tomto prípade tvrdenie vety je zrejme pravdivé. Teraz predpokladajme, že tvrdenie je pravdivé pre všetky grafy, v ktorých . Zoberme ľubovolný graf o hranách. Vynechajme z jednu hranu ; dostaneme graf o hranách, ktorého súčet stupňov vrcholov je (podľa indukčného predpokladu) rovný . Ak však pridáme naspäť hranu , zväčší sa o jednotku stupeň vrchola aj , teda celkový súčet vrcholov sa zväčší o 2 a bude sa rovnať . Tým je dôkaz ukončený.
Dôsledok vety
Z uvedenej vety a jej dôkazu bezprostredne vyplýva, že v konečnom neorientovanom grafe je počet vrcholov nepárneho stupňa párne číslo. Špeciálny prípad tohto dôsledku je fakt, že neexistuje graf, ktorý by obsahoval jediný vrchol nepárneho stupňa). Dôkaz je založený na fakte, že súčet nepárneho počtu nepárnych čísel je nepárne číslo.
- 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.
Literatúra
- Znám, Š: Kombinatorika a teória grafov. Bratislava, Matematicko-fyzikálna fakulta Univerzity Komenského. 1982, s. 37
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Binárny strom (teória grafov)
Cesta (teória grafov)
Chromatické číslo
Chromatický index
Cyklomatické číslo grafu
Eulerovský ťah
Excentricita (teória grafov)
Faktor grafu
Farbenie grafu
Farbenie vrcholov
Grafová postupnosť
Graf (matematika)
Hamiltonovská kružnica
Hamiltonovský graf
Hrana (teória grafov)
Komplement grafu
Komponent grafu
Kostra grafu
Kružnica (teória grafov)
Minimálna kostra grafu
Most (teória grafov)
Neplanárny graf
Nezávislá množina
Ohodnotený graf
Oreho veta
Orientované stromy
Párny graf
Petersenov graf
Podgraf
Priesečníkové číslo (teória grafov)
Problém obchodného cestujúceho
Problém siedmich mostov
Rovinný graf
Súvislý graf
Sled (teória grafov)
Spektrálna teória grafov
Strom (teória grafov)
Teória grafov
Teória grafov – grafová postupnosť
Topologická teória grafov
Vrchol (teória grafov)
Vzdialenosť (teória grafov)
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk