Matematické Fórum

babca · 18. 02. 2010 03:48

Dobry den, nevite nekdo nahodou kolik kruznic obsahuje bipartitni graf $K_{n,m}$ ?

petrkovar

↑ babca:Nápověda: mějme $m\le n$ . Každý cyklus musí být sudé délky 2k kde $2\le k\le m$ . Z každé partity musím vybrat k vrcholů...
Edit: Předpokládám, že dvě kružnice jsou různé, pokud se liší v alespoň alespoň jedné hraně.

petrkovar · 23. 02. 2010 15:37

↑ babca:Další nápověda: kolik existuje způsobů, jak vybrat k vrcholů z m?
Doporučuji zkusit najít kružnice "ručně" pro $K_{2,3}$ a pak konfrontvat s výpočty.

babca · 23. 02. 2010 22:11

dobrej hint, ale pokud bych to bral jako soucet kombinacniho cisla m nad k, tak uz pro $K_{3,3}$ to neplati :( a nebo to spatne chapu :(

Olin · 23. 02. 2010 22:15

Ještě je nutné vrcholy v obou partitách seřadit.

Pavel Brožek

Postupoval bych tak, že si jeden vrchol z první partity zafixuji, z druhé můžu vybrat k způsoby pokračování kružnice, z první pak k-1 způsoby, z druhé k-1 způsoby, ... To ještě musím vydělit dvěma, protože kružnici mohu procházet dvěma směry (každou kružnici jsem započetl dvakrát). Tedy celkový počet kružnic by měl být

$\sum_{k=2}^m{m\choose k}{n\choose k}\frac{k!\cdot(k-1)!}2$

Je to dobře?

petrkovar · 24. 02. 2010 10:04

↑ BrozekP:Ano. Pokud se dotáhne nápověda o výběru (uspořádaném) do konce, tak dostaneme totéž.

babca · 25. 02. 2010 00:11

Mockrat vam vsem dekuji. Omlouvam se, za jsem nebyl schopnej na to prijit sam, ale uz diky vysvetli od BrozekP jsem to pochopil :). Jeste jednou dekuji :)

Matematické Fórum

#1 18. 02. 2010 03:48

Kruznice v bipartitnim grafu

#2 18. 02. 2010 20:33 — Editoval petrkovar (18. 02. 2010 21:10)

Re: Kruznice v bipartitnim grafu

#3 23. 02. 2010 15:37

Re: Kruznice v bipartitnim grafu

#4 23. 02. 2010 22:11

Re: Kruznice v bipartitnim grafu

#5 23. 02. 2010 22:15

Re: Kruznice v bipartitnim grafu

#6 23. 02. 2010 22:46 — Editoval BrozekP (23. 02. 2010 22:47)

Re: Kruznice v bipartitnim grafu

#7 24. 02. 2010 10:04

Re: Kruznice v bipartitnim grafu

#8 25. 02. 2010 00:11

Re: Kruznice v bipartitnim grafu

Zápatí