Grafy, drzewa binarne, izomorfizm Gruby: Szalom Narysuj wszystkie ukorzenione drzewa binarne o 7 wierzchołkach z dokładnością do izomorfizmu. Ukorzenione czyli jeden wierzchołek stopnia 2. Binarne czyli wierzchołek co najwyżej 3 stopnia. Wyszło mi tych drzew 10. https://drive.google.com/file/d/0B2rgm5NqbHvqTlRsV0RnV09DVGM/view?usp=sharing Za dużo, za mało czy może w sam raz?

Pytający: Ukorzenione, czyli jeden z wierzchołków jest szczególny, wybrany (korzeń) i jego stopień nie jest większy niż 2 (może być równy 1 czy nawet 0 dla drzewa o 1 wierzchołku). Oznaczmy przez f(n) liczbę ukorzenionych drzew binarnych o n wierzchołkach (z dokładnością do izomorfizmu). f(1)=1 f(2)=f(1)=1 // do korzenia jako gałęzie dokładasz drzewa: (0,1) elementowe

	f(1) 2
f(3)=f(2)+f(1)+		=1+1+0=2 // dokładasz drzewa: (0,2), (1,1) elementowe

f(4)=f(3)+f(1)f(2)=2+1*1=3 // dokładasz drzewa: (0,3), (1,2) elementowe

	f(2) 2
f(5)=f(4)+f(1)f(3)+f(2)+		=3+1*2+1+0=6 // (0,4), (1,3), (2,2)

f(6)=f(5)+f(1)f(4)+f(2)f(3)=6+1*3+1*2=11 // (0,5), (1,4), (2,3)

	f(3) 2
f(7)=f(6)+f(1)f(5)+f(2)f(4)+f(3)+		=11+1*6+1*3+2+1=23 // (0,6), (1,5), (2,4), (3,3)

A jeśli interesują Cię jedynie te drzewa, w których korzeń ma stopień 2, wystarczy w ostatnim kroku nie wliczać tych powstałych poprzez dorzucenie do korzenia jako gałęzi odpowiednio drzew 0 i 6 elementowych. Czyli takich drzew będzie 23−11=12.