Drzewo binarne wykazać

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
yooko34
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 19 sty 2017, o 22:50
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 3 razy

Drzewo binarne wykazać

Post autor: yooko34 »

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.
Awatar użytkownika
kerajs
Użytkownik
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ć

Post autor: kerajs »

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