Lekki dowód dotyczący kopca.

józef92
Użytkownik
Użytkownik
Posty: 660
Rejestracja: 13 gru 2008, o 21:01
Płeć: Mężczyzna
Lokalizacja: Bolesławiec
Podziękował: 263 razy
Pomógł: 3 razy

Lekki dowód dotyczący kopca.

Post autor: józef92 » 6 wrz 2011, o 11:46

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}\)

??

Afish
Moderator
Moderator
Posty: 2823
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 354 razy

Lekki dowód dotyczący kopca.

Post autor: Afish » 6 wrz 2011, o 13:07

józef92 pisze:liczba wierzchołków zewnętrznych (...) jest równa albo o 1 większa od liczby wierzchołków zewnętrznych
Coś tu chyba nie gra.

józef92
Użytkownik
Użytkownik
Posty: 660
Rejestracja: 13 gru 2008, o 21:01
Płeć: Mężczyzna
Lokalizacja: Bolesławiec
Podziękował: 263 razy
Pomógł: 3 razy

Lekki dowód dotyczący kopca.

Post autor: józef92 » 6 wrz 2011, o 17:05

No na końcu cytowanego fragmentu wewnętrznych, ale łatwo się domyśleć

Afish
Moderator
Moderator
Posty: 2823
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 354 razy

Lekki dowód dotyczący kopca.

Post autor: Afish » 6 wrz 2011, o 17:36

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ść.

józef92
Użytkownik
Użytkownik
Posty: 660
Rejestracja: 13 gru 2008, o 21:01
Płeć: Mężczyzna
Lokalizacja: Bolesławiec
Podziękował: 263 razy
Pomógł: 3 razy

Lekki dowód dotyczący kopca.

Post autor: józef92 » 6 wrz 2011, o 18:10

Afish, widzę to, teraz kwestia zapisania tego formalnie Nie wiem naprawdę jak to "sformalizować"....

Afish
Moderator
Moderator
Posty: 2823
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 354 razy

Lekki dowód dotyczący kopca.

Post autor: Afish » 6 wrz 2011, o 19:11

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.

józef92
Użytkownik
Użytkownik
Posty: 660
Rejestracja: 13 gru 2008, o 21:01
Płeć: Mężczyzna
Lokalizacja: Bolesławiec
Podziękował: 263 razy
Pomógł: 3 razy

Lekki dowód dotyczący kopca.

Post autor: józef92 » 6 wrz 2011, o 20:15

Ostatnie równanie dobrze wyprowadziłeś? )

Afish
Moderator
Moderator
Posty: 2823
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 354 razy

Lekki dowód dotyczący kopca.

Post autor: Afish » 6 wrz 2011, o 23:05

Tak.

józef92
Użytkownik
Użytkownik
Posty: 660
Rejestracja: 13 gru 2008, o 21:01
Płeć: Mężczyzna
Lokalizacja: Bolesławiec
Podziękował: 263 razy
Pomógł: 3 razy

Lekki dowód dotyczący kopca.

Post autor: józef92 » 7 wrz 2011, o 07:36

k nieparzyste przyjmie postać 2k+1, teraz nie dziele tego tak jak w przypadku k parzystego. Po prostu 2k+1. Wyszło ok

ODPOWIEDZ