Matematické Fórum

check_drummer · 21. 09. 2010 22:01

Dokažte, že pravděpodobnost, že pro náhodně vybraný strom na n vrcholech má jeho náhodně vybraný vrchol stupeň 1, je $(1-\frac{1}{n})^{n-2}$ . Každý strom a ve stromě každý vrchol mají stejnou pravděpodobnost, že budou vybrány.

petrkovar

↑ check_drummer:Zkusil bych:
1. rozlišovat vrcholy například označením
2. využít Cayleyho vzorec pro počet koster kompletního grafu
3. vrchol $x$ stupně 1 spojit s některým ze zbývajícíh $n-1$ vrcholů stromu (na $n-1$ zbývajícíh vrcholech)

check_drummer · 01. 10. 2010 18:28

↑ petrkovar:

Přesně tak. (Je to jedna z mála úloh, kterou jsem zadal, i když řešení znám. :-)
Na druhou stranu moje motivace byla vyhnout se Cayleyho formuli, pravděpodobnost spočítat jinak a tím Cayleyho formuli dokázat. :-) To se mi však nepodařilo.

petrkovar · 05. 10. 2010 22:52

↑ check_drummer:Aha! To trochu mění situaci.
A co důkaz Cayleyho formule pomocí "povykosů"? (Matoušek a Nešetřil, Kapitoly z diskrétní matematiky)

check_drummer · 06. 10. 2010 18:58

↑ petrkovar:
Ano, důkazů pár znám. A díky tomu, že je jich tolik jsem chtěl přijít ještě na nějaký další. :-)

Matematické Fórum

#1 21. 09. 2010 22:01

Pravděpodobnost, že vrchol stromu má stupeň 1

#2 01. 10. 2010 10:15 — Editoval petrkovar (01. 10. 2010 10:16)

Re: Pravděpodobnost, že vrchol stromu má stupeň 1

#3 01. 10. 2010 18:28

Re: Pravděpodobnost, že vrchol stromu má stupeň 1

#4 05. 10. 2010 22:52

Re: Pravděpodobnost, že vrchol stromu má stupeň 1

#5 06. 10. 2010 18:58

Re: Pravděpodobnost, že vrchol stromu má stupeň 1

Zápatí