Witam,
Mam takie zadanie: Wykazać, że ukorzenione drzewo binarne ( każdy wierzchołek wewnętrzny ma stopień \(\displaystyle{ 3}\) o \(\displaystyle{ n}\) wierzchołkach wewnętrznych ma \(\displaystyle{ n+1}\) liści nie licząc korzenia.
Jest to logiczne, że tak jest ale nie potrafię tego udowodnić w sposób matematyczny.
Z góry dziękuje za pomoc.
Drzewo binarne wykazać
- kerajs
- Użytkownik
- Posty: 8570
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 306 razy
- Pomógł: 3347 razy
Re: Drzewo binarne wykazać
Może indukcją?
Niech \(\displaystyle{ L_k}\) to liczba liści.
\(\displaystyle{ k=1}\) i \(\displaystyle{ k=2}\) to przypadki wyłączone przez założenia.
\(\displaystyle{ k=3}\) wierzchołków wewnętrznych:
Jest tylko jedna opcja: korzeń, dwa wierzchołki wewnętrzne i 4 liście ( wierzchołki zewnętrzne), więc \(\displaystyle{ L_3=4}\)
\(\displaystyle{ k=4}\) wierzchołków wewnętrznych:
Jeden z liści staje się wierzchołkiem wewnętrznym i wypuszcza 2 liście. \(\displaystyle{ L_4=L_3-1+2=5}\)
Załóżmy że jest n wierzchołków wewnętrznych i \(\displaystyle{ L_n =n+1}\). Wtedy dla \(\displaystyle{ k=n+1}\) powinno być \(\displaystyle{ L_{n+1} =n+2}\)
Jeden z liści staje się wierzchołkiem wewnętrznym i wypuszcza 2 liście.
\(\displaystyle{ L=L_{n+1}=L_n -1+2 =n+1-1+2=n+2=P}\)
Niech \(\displaystyle{ L_k}\) to liczba liści.
\(\displaystyle{ k=1}\) i \(\displaystyle{ k=2}\) to przypadki wyłączone przez założenia.
\(\displaystyle{ k=3}\) wierzchołków wewnętrznych:
Jest tylko jedna opcja: korzeń, dwa wierzchołki wewnętrzne i 4 liście ( wierzchołki zewnętrzne), więc \(\displaystyle{ L_3=4}\)
\(\displaystyle{ k=4}\) wierzchołków wewnętrznych:
Jeden z liści staje się wierzchołkiem wewnętrznym i wypuszcza 2 liście. \(\displaystyle{ L_4=L_3-1+2=5}\)
Załóżmy że jest n wierzchołków wewnętrznych i \(\displaystyle{ L_n =n+1}\). Wtedy dla \(\displaystyle{ k=n+1}\) powinno być \(\displaystyle{ L_{n+1} =n+2}\)
Jeden z liści staje się wierzchołkiem wewnętrznym i wypuszcza 2 liście.
\(\displaystyle{ L=L_{n+1}=L_n -1+2 =n+1-1+2=n+2=P}\)