Matematické Fórum

finch.cz · 05. 12. 2010 14:40

Zdravím

chtěl jsem se zeptat, jestli chápu dobře co to je cesta grafu. Podle toho, co jsem zatím spočítal to je hrana grafu krát dvě -> u neorientovaného grafu.

Tzn třeba pro K3

$E \binom 6 2 = 3$ to je počet hran. ale jelikož můžu jít cestou tam i zpět, tak krát 2.

pro K4 by pak počet hran byl 6, ale cest 12.

nebo se nějak pletu?

petrkovar · 05. 12. 2010 16:18

↑ finch.cz:Cesta v grafu je taková posloupnost vrcholů a hran, ve které se každý vrchol vyskytuje jen jednou. V uzavřené cestě dovolíme, aby poslední vrchol cesty byl stejný jako první. Proto nerozumím, co se myslí tím "cesta je hrana grafu krát dvě".
Každopádně v grafu $K_3$ rozlišíme 6 cest ochodního cestujícího a v grafu $K_4$ jich bude 24.

finch.cz · 05. 12. 2010 16:35

matematice popravdě moc nehovím, ale zkoušel jsem si nakreslit obrázek

kde mi po výpočtu $E \binom 6 2 = 3$ ale jelikož panáček si může chodit tam i zpět, tak proto jsem to dal dva krát (tudíž 6 cest), takhle jsem si myslel, že se počítá ona cesta. Ale jak to tak vypadá, tak je to permutace.

Díky za pomoc

petrkovar · 05. 12. 2010 20:07

Myslím, že jste počítal počet orientovaných hran. V $K_2$ by byly dvě a v $K_5$ jich je 20.
Pokud se jedná o projekt týkající se cest ochodního cestujícího, tak pojem cesta je zcela o něčem jiném (jak jsem už psal v předchozím příspěvku).

Matematické Fórum

#1 05. 12. 2010 14:40

hrana grafu

#2 05. 12. 2010 16:18

Re: hrana grafu

#3 05. 12. 2010 16:35

Re: hrana grafu

#4 05. 12. 2010 20:07

Re: hrana grafu

Zápatí