Ile jest drzew n wierzchołkowych - dowód

wena · Post autor: **wena** » 11 lip 2010, o 18:06

Witam.

Mam za zadanie wskazać ile jest n wierzchołkowych drzew (etykietowanych).
Wiem, że chodzi tutaj o wzór Caley'a ( \(\displaystyle{ n^{n-2}}\) ).
Jednak muszę udowodnić go za pomocą kodu Prüfer'a. Niestety nie mam pojęci jak to zrobić.

Z góry dzięki za pomoc.

miodzio1988 · Post autor: **miodzio1988** » 11 lip 2010, o 18:08

wzór Cayley'a dowód wpisz w google i Ci wyskoczy dowód.

wena · Post autor: **wena** » 11 lip 2010, o 18:16

Skoro napisałem temat tutaj to dość jasne jest, iż google nie dało mi wystarczającej odpowiedzi. W wynikach znalazłem albo ogólnikowe opisanie dowodu, albo alternatywne jego wersje.

miodzio1988 · Post autor: **miodzio1988** » 11 lip 2010, o 18:18

Jednak muszę udowodnić go za pomocą kodu Prüfer'a

Musi być tym sposobem akurat? Skąd ten przymus?

wena · Post autor: **wena** » 11 lip 2010, o 18:25

Od prowadzącego przedmiot, na którym dostałem owe zadanie.

miodzio1988 · Post autor: **miodzio1988** » 11 lip 2010, o 18:31

A nie możesz sobie przerobić np dowodu indukcyjnego tak, żeby był on określony w terminach tego kodu?

wena · Post autor: **wena** » 11 lip 2010, o 18:52

Znalazłem rozwiązanie:

Kod: Zaznacz cały

Dowód:W oparciu o algorytmy kodu Prüfera i metodę Prüfera, wykazuemy
wzajemnie jednoznaczne przyporządkowanie pomiędzy zbiorem drzew
n wierzchołków a wszystkimi ciągami postaci zaetykietowanych mających
(a1 , a2 , ..., an−2 ), których każdy wyraz ai jest liczbą naturalną i 1 ≤ ai ≤ n.
  
                                           
Stąd wynika teza, ponieważ istnieje n−2 takich ciągów (tyle ile wariacji n − 2 wyrazowych zbioru n−elementowego.

abc666 · Post autor: **abc666** » 11 lip 2010, o 20:21

wena, tylko dowód polega na tym żeby tą bijekcję wskazać. O ile mnie pamięć nie myli dowód można znaleźć w Teorii grafów, Wilsona