Witam mam problem z tym zadaniem
liczba krawędzi w grafie\(\displaystyle{ k_{n}}\) jest równa liczbie wierzchołków w pewnym drzewie.Obliczyć sumę stopni wierzchołków w tym drzewie.
Byłbym wdzięczny jeżeli ktoś udzieliłby wskazówek
Liczba krawędzi grafu, liczba wierzchołków w drzewie.
-
abc666
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Liczba krawędzi grafu, liczba wierzchołków w drzewie.
A suma stopni wierzchołków w dowolnym grafie jest równa podwojonej liczbie krawędzi (który to fakt znany jest też jako lemat o uściskach dłoni).
Q.
Q.