Matematické Fórum

flicek · 28. 11. 2011 21:41 — Editoval flicek (28. 11. 2011 21:44)

Ahoj, je nejaky obecny vzorecek jak zjistit pocet vsech ruznych cest mezi dvema vrcholy v uplnem grafu?Na kombinatoriku jsem celkem levak.Napadlo me to nejak pocitat pres cesty delky 1,...,n a pak to poscitat, bohuzel i tady mi moje kombinatoricke schopnosti moc nepomohly.
A kdyz uz tu pisu a jsem u te kombinatoriky,kolik podgrafu bude mit uplny graf?

FailED · 29. 11. 2011 00:17

Ahoj,

nápad je správný, zafixujeme první a poslední vrchol, přes ostatní můžeme jít libovolně. Dostaneme řadu $\sum_{0}^{n-2}i!{n-2 \choose i}=$ https://oeis.org/A000522

Počet podgrafů: vybereme podmnožinu vrcholů a v ní podmnožinu hran, vyjde
$\sum_{i=0}^n {n \choose i}2^{i \choose 2}$ https://oeis.org/A006896

Kozuch · 25. 05. 2014 15:07

Mě by se hodil vzoreček pro výpočet této úlohy, ale s omezením pro délku cesty. Např. počet všech cest délky 7 v úplném grafu K12 mezi vrcholy A a B.

Matematické Fórum

#1 28. 11. 2011 21:41 — Editoval flicek (28. 11. 2011 21:44)

Teorie grafu - pocet cest mezi dvema vrcholy v uplnem grafu

#2 29. 11. 2011 00:17

Re: Teorie grafu - pocet cest mezi dvema vrcholy v uplnem grafu

#3 25. 05. 2014 15:07

Re: Teorie grafu - pocet cest mezi dvema vrcholy v uplnem grafu

Zápatí