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

Posty: 9
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: 6332
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ć warunek na niezmiennik pętli  drago77  1
 metoda wlaczen i wylaczen, kolorowanie grafu,drzewo binarne  anna_y  0
 drzewo prowdopodobieństwo  kasia0074  5
 mnożenie binarne przez 1010  panczo12d  2
 Drzewo - graf planarny  katbest  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl