Udowodnij, że w dowolnym kopcu liczba wierzchołków zewnętrznych ( liści ) jest równa albo o 1 większa od liczby wierzchołków zewnętrznych ( pewnie krawędzi ).
A więc rozrysowałem to sobie ładnie i wyciągnąłem wniosek:
że dla \(\displaystyle{ 2k}\) liści potrzeba \(\displaystyle{ 2k-1}\) krawędzi ich łączących, natomiast przy \(\displaystyle{ 2k+1}\) liści potrzeba \(\displaystyle{ 2k}\) krawędzi ich łączących, gdzie \(\displaystyle{ k \in \mathbb{Z}}\), ale nie wiem za bardzo jak mam to udowodnić
Że: \(\displaystyle{ 2k>2k-1}\) oraz \(\displaystyle{ 2k+1>2k}\)
??
Lekki dowód dotyczący kopca.
-
Afish
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
Lekki dowód dotyczący kopca.
Coś tu chyba nie gra.józef92 pisze:liczba wierzchołków zewnętrznych (...) jest równa albo o 1 większa od liczby wierzchołków zewnętrznych
-
Afish
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
Lekki dowód dotyczący kopca.
Jeżeli miało być wierzchołków wewnętrznych, to nie chodzi o krawędzie, a o wszystkie wierzchołki, które nie są liśćmi. Przy czym wtedy teza nie jest prawdziwa. Dopiero gdy zażądamy, aby kopiec był zupełny, wtedy jest to prawda i podejrzewam, że o takie coś chodziło.
Co się tyczy samego dowodu, to narysuj dowolny kopiec i policz liście. Reszta "udowodni się sama"
Możesz też próbować pokazywać indukcyjnie, że po odcięciu dowolnego liścia albo nie zmieniliśmy liczby wierzchołków zewnętrznych, albo zmniejszyliśmy liczbę wierzchołków zewnętrznych o 1, ale przy tym przybył nam dodatkowy liść.
Co się tyczy samego dowodu, to narysuj dowolny kopiec i policz liście. Reszta "udowodni się sama"
Możesz też próbować pokazywać indukcyjnie, że po odcięciu dowolnego liścia albo nie zmieniliśmy liczby wierzchołków zewnętrznych, albo zmniejszyliśmy liczbę wierzchołków zewnętrznych o 1, ale przy tym przybył nam dodatkowy liść.
-
Afish
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
Lekki dowód dotyczący kopca.
Tak na szybko, mogą być błędy.
Jeżeli kopiec ma wysokość \(\displaystyle{ h}\) i na ostatnim poziomie jest \(\displaystyle{ k}\) wierzchołków, wtedy cały kopiec ma \(\displaystyle{ 2^{h-1}-1 + k}\) wierzchołków. Rozpatrzmy dwa przypadki: \(\displaystyle{ k}\) jest parzyste, lub jest nieparzyste. Ja zajmę się przypadkiem parzystości, nieparzysty zrobisz sam, jest analogiczny. Na przedostatnim poziomie jest \(\displaystyle{ 2^{h-2}}\) wierzchołków, z czego \(\displaystyle{ \frac{k}{2}}\) to wierzchołki wewnętrzne. Zatem liści jest \(\displaystyle{ 2^{h-2} - \frac{k}{2} + k = 2^{h-2} + \frac{k}{2}}\). Teraz wierzchołków wewnętrznych jest \(\displaystyle{ 2^{h-1}-1+k - \left(2^{h-2} + \frac{k}{2}\right) = 2^{h-1} - 1 + k - 2^{h-2} - \frac{k}{2} = 2^{h-2} + \frac{k}{2} - 1}\), czyli o jeden mniej od liści. Teraz policz to samo dla drugiego przypadku i gotowe.
Jeżeli kopiec ma wysokość \(\displaystyle{ h}\) i na ostatnim poziomie jest \(\displaystyle{ k}\) wierzchołków, wtedy cały kopiec ma \(\displaystyle{ 2^{h-1}-1 + k}\) wierzchołków. Rozpatrzmy dwa przypadki: \(\displaystyle{ k}\) jest parzyste, lub jest nieparzyste. Ja zajmę się przypadkiem parzystości, nieparzysty zrobisz sam, jest analogiczny. Na przedostatnim poziomie jest \(\displaystyle{ 2^{h-2}}\) wierzchołków, z czego \(\displaystyle{ \frac{k}{2}}\) to wierzchołki wewnętrzne. Zatem liści jest \(\displaystyle{ 2^{h-2} - \frac{k}{2} + k = 2^{h-2} + \frac{k}{2}}\). Teraz wierzchołków wewnętrznych jest \(\displaystyle{ 2^{h-1}-1+k - \left(2^{h-2} + \frac{k}{2}\right) = 2^{h-1} - 1 + k - 2^{h-2} - \frac{k}{2} = 2^{h-2} + \frac{k}{2} - 1}\), czyli o jeden mniej od liści. Teraz policz to samo dla drugiego przypadku i gotowe.