Korzystając z kodu Prufera uzasadnić że ...

bananajoe · Post autor: **bananajoe** » 20 sty 2008, o 16:57

Miło by było jak by mi ktoś to zadanie rozwiązał i mniej więcej wytłumaczył co i jak Z góry dziękuje

Korzystając z kodu Prufera uzasadnić że :

\(\displaystyle{ t( d_{1}, d_{2},..., d_{n})= {n-2 \choose d_{1}-1, d_{2}-1,..., d_{n}-1}}\)

Dodam tyle ze Prufera posiada dwie kropki nad "u"

UNIX_admin · Post autor: **UNIX_admin** » 21 sty 2008, o 21:38

zeby bylo "ladnie matematycznie" mozna stwierdzic, ze liczba drzew wynosi tyle ile napisales, nastepnie, dla formalnosci sprawdzic, ze zaleznosc zachodzi dla n=2, zalozyc, ze teza jest prawdziwa dla liczby wierzcholkow mniejszej od n. teraz wystarczy wybrac wierzcholek , ktorego stopien jest rowny 1 (w kazdym drzewie taki istnieje) i nazwac go "n", potem usunac krawedz przy tym wierzcholku, a wierzcholem "z drugiej strony krawedzi" oznaczyc przez "j", policzyc (z tezy) ile jest drzew dla ustalonego "j", no a liczba wszystkich mozliwych drzew, to suma po wszystkich mozliwych "j", czyli tyle ile w twierdzeniu.

mozna tez analogicznie jak w zadaniu: ile roznych slow mozna utworzyc z wyrazu MATEMATYKA, czyli podzielic wszystkie permutacje liter przez mozliwe powtorzenia. Podobnie jak w tym zadaniu w drzewie nie jest wazna kolejnosc wierzcholkow o tym samym stopniu.

bananajoe · Post autor: **bananajoe** » 27 sty 2008, o 16:05

hmm to jest rozwiazanie czy podpowiedz jak to rozwiac? naprawde jestem ciemny i nie wiem jak to zrobic ...