Pewne drzewo ma 102 wierzchołki stopnia 4, 14 wierzchołków stopnia 3 i 45 wierzchołków stopnia 2. Jeśli pozostałe wierzchołki to liście, to ile wierzchołków jest w tym grafie?.
Witam otóż mam problem taki że za bardzo nie wiem jak w tym przypadku obliczyć ilość liści powiem Wam co wiem :
ilość krawędzi w drzewie o n wierzchołkach \(\displaystyle{ n-1}\)
Suma stopni wierzchołków w drzewie to \(\displaystyle{ 2n-2}\)
Z góry dziękuję
ilość wierzchołków w drzewie
-
- Użytkownik
- Posty: 79
- Rejestracja: 27 wrz 2009, o 11:26
- Płeć: Mężczyzna
- Lokalizacja: szczebrzeszyn
- Podziękował: 5 razy
-
- Użytkownik
- Posty: 89
- Rejestracja: 14 kwie 2010, o 22:00
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 7 razy
- Pomógł: 9 razy
ilość wierzchołków w drzewie
Hmmm mnie to wygląda na to, że możesz sobie złożyć dwa równania, jeżeli x to ilość liści i n to całkowita ilośc wierzchołków, to mamy:
\(\displaystyle{ 102 + 14 + 45 + x = n}\) (suma wierzchołków)
\(\displaystyle{ 102*4 + 14*3 + 45*2 + x*1 = 2n - 2}\) (suma stopni wierzchołków)
Rozwiąż dla x i n i gotowe.
\(\displaystyle{ 102 + 14 + 45 + x = n}\) (suma wierzchołków)
\(\displaystyle{ 102*4 + 14*3 + 45*2 + x*1 = 2n - 2}\) (suma stopni wierzchołków)
Rozwiąż dla x i n i gotowe.