Lemat o uściskach dłoni
Dany jest graf prosty o wierzchołkach i krawędziach. Na mocy lematu o uściskach dłoni spełniona jest następująca własność:
Powyższą własność nietrudno jest zrozumieć intuicyjnie: każda krawędź łączy dwa wierzchołki, a zatem dodając do siebie stopnie sąsiadujących wierzchołków (czyli liczby krawędzi wychodzących z nich), liczymy każdą z krawędzi dwukrotnie, co potwierdza prawdziwość powyższej własności. Wynika z tego również fakt, że w dowolnym grafie liczba wierzchołków o nieparzystych stopniach jest parzysta.
Jako pierwszy zauważył tę własność Leonhard Euler w 1736 roku[1].
Przypisy
- ↑ Robin J Wilson: Wprowadzenie do teorii grafów. Warszawa: Wydawnictwo Naukowe PWN, 1998.
- p
- d
- e
Najważniejsze pojęcia |
więcej... |
---|---|
Wybrane klasy grafów |
|
Algorytmy grafowe | |
problemy grafowe | |
Inne zagadnienia |