szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 1 cze 2017, o 01:48 
Użytkownik

Posty: 8
Lokalizacja: Polska
Witam,

Mam takie zadanie: Wykazać, że ukorzenione drzewo binarne ( każdy wierzchołek wewnętrzny ma stopień 3 o n wierzchołkach wewnętrznych ma 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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 1 cze 2017, o 07:14 
Użytkownik
Avatar użytkownika

Posty: 6108
Może indukcją?

Niech L_k to liczba liści.
k=1 i k=2 to przypadki wyłączone przez założenia.

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 L_3=4

k=4 wierzchołków wewnętrznych:
Jeden z liści staje się wierzchołkiem wewnętrznym i wypuszcza 2 liście. L_4=L_3-1+2=5

Załóżmy że jest n wierzchołków wewnętrznych i L_n =n+1. Wtedy dla k=n+1 powinno być L_{n+1} =n+2
Jeden z liści staje się wierzchołkiem wewnętrznym i wypuszcza 2 liście.
L=L_{n+1}=L_n -1+2 =n+1-1+2=n+2=P
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 wykazać przez indukcję  lampid  1
 Ciagi binarne 1/-1  gomgli  1
 Ciągi binarne - zadanie 8  karaoke120  3
 drzewo i graf krawędzowy  glupiablondyna  3
 wykazać równość - zadanie 9  robin5hood  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl