Matematické Fórum

↑ Kondr:

nepodařilo se mi to domyslet celé, pomůžeš?

Myslím, že jsem přišel na hezký způsob, jak vypočítat dvojku. Jde o výpočet, kolik koster používá danou hranu. Počet koster úplňáku bez této hrany pak bude samozřejmě počet všech koster úplňáku mínus počet koster procházejících jednou hranou.

Hlavní myšlenka:
Definujme kostlivce jako kostru grafu, ve které ještě speciálně zvolíme jednu hranu - tu nazvěme lebka. Nyní spočítáme dvěma způsoby celkový počet kostlivců v úplném grafu - jednak tak, že sečteme počet kostlivců s jednou kostrou přes všechny kostry, za druhé tak, že sečteme počet kostlivců s danou lebkou přes všechny lebky.

Nečiním si žádné nároky na originalitu (beztak na to přišel někdo přede mnou), ale po těch hodinách bojů s tou nehoráznou sumou (o které mluvil Kondr) mi to přišlo jako docela hezký důkaz.

↑ Olin:

http://en.wikipedia.org/wiki/Kirchhoff%27s_theorem

To je jako jit s kanonem na vrabce! :-)

> http://en.wikipedia.org/wiki/Cayley%27s_formula

Nevidim jak jsi to myslel? Co presne myslis sumou z Cayleho formule?

Dukaz pocitanim dvema zpusoby (Ty mu rikas pocitani kostlivcu) je to nejhezci,
co znam , nejak jsi to ale neodpocital, ze :-(?

PS: Ten contraction-deletion vzorec funguje take, ale opet jde o kanon na vrabce
(a navic mam dojem, ze umlatit to tim obecne bude docela pracne).

↑ PeterSheldon: A když to rozepíšu, oznámkuješ mi to? :D

↑ PeterSheldon: Suma z Cayleyho formule byla myšlena takto: opět budeme počítat kostry, které hranu obsahují. Po odstranění této hrany se kostra rozpadne na dvě komponenty (jedna může být degenerovaná do vrcholu). Takové komponenty sestavíme tak, že pevně rozdělíme vrcholy na skupiny o velikostech k a n-k,  v první zvolíme kostru způsoby, ve druhé způsoby, celkem máme způsobů. To dost připomíná konvoluci exponenciálních vytvořujících funkcí, ale stejně jako u Kirchhoffa, cesta k uzavřené formuli vypadá přinejmenším trnitě.

↑ Kondr:

mam jeste par otazek k tvemu reseni (aspon vidis, ze nad ulohou opravdu premyslim, a ze mi nejde pouze o tupe opisovani jiz napsanych reseni !! )


to co jsi napsal podle me neni patrne, proc by se mel uplnak po odstraneni jedne
hrany rozpadnout na komponenty souvislosti?! Stale si tedy trvam na svem, ze
tomu ani zamak nerozumim (a o 100% rigoroznost mi ted vazne nejde).

PS: co mi specialne nesedi, ze Ti pri dosazeni k=n vyjde pocet koster uplneho
grafu, neboli takhle Ti v te sume vyslo radove vic koster uplnaku bez hrany, nez
u uplnaku (a to je divne, ne?).

PPS: cesta z Matrix-Tree theoremu mozna nemusi byt tak slozita, ale nejsem si tim tak jisty... jak to tedy ma byt spravne prosim?


EDIT:

Uz chapu, co jsi chtel tou
sumou rict, ale neprijde Ti divne, ze by pocet koster uplnaku pouzivajici jednu
hranu byl vetsi, nez pocet vsech koster uplnaku?

↑ Kondr:

>  měl jsem tam chybu, ta suma má jít jen do n-1 (každá komponenta musí mít
> alespoň jeden vrchol).

Ted ale ta suma vypada take podezrele, napr. pro n=2 je to 2*1*1 = 2, ne? (a K_2
ma jen 1 kostru celkem.)

> A druhá nepřesnost byla v tom, že se na komponenty nerozpadne graf, ale
> kostra.

Jojo, cestou domu mi pak doslo, jak to myslis :-).

> Ikdyž i ta původní suma byla OK: poslední člen se násobí nulou.

Ta posledni suma nebyla rozhodne ok, nasobilo se to tam necim jako 0^-2, coz
neni zrovna dvakrat definovane :-).

PS: naopak tvoje reseni se mi libi, jen chci latku pochopit, proto se te prosim ptam zrovna tebe. Hlavne z toho duvodu, ze jsi na otazku odpovedel, a take jsi velmi schopnym pomocnikem na tomto foru. Za pomoc opravdu dekuji:)

↑ musixx: V tomhle má prvdu PetrSheldon -- .

↑ PeterSheldon: Ještě jsem tu sumu zapoměl vydělit dvěma -- na pořadí komponent nezáleží.

↑ Kondr:

A to je jeste vetsi nesmysl, ne?:(((( Preci zalezi na tom, jestli ta komponenta
obsahuje u, nebo jestli obsahuje v (kde uv je hrana, kterou jsi odebiral).
Navic, co by se potom stalo pri dosazeni napr. n=3? Jestli dosazuji spravne,
tak vyjde 3 (a to preci neni pravda).

Porad netusim jak to spocitat spravne:(

↑ FabulousDeniska:Tvrzaní neplatí pro K_{1,1}.

↑ Olin:

ten důkaz má hodně pěknou myšlenku a suma mi připadá zatím v pořádku..  díky:)