Matematické Fórum

Archiv diskusního fóra o matematice, 2006–2026

Toto je archiv Matematického Fóra. Fórum je dostupné jen ke čtení. Můžete se ale zaregistrovat na náš Discord server.

#1 05. 12. 2010 14:40

finch.cz
Místo: Ostrava
Příspěvky: 34
Reputace:   0 
 

hrana grafu

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?

Offline

 

#2 05. 12. 2010 16:18

petrkovar
Veterán
Místo: Ostrava/Krmelín
Příspěvky: 1012
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: hrana grafu

↑ 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.

Offline

 

#3 05. 12. 2010 16:35

finch.cz
Místo: Ostrava
Příspěvky: 34
Reputace:   0 
 

Re: hrana grafu

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

http://img703.imageshack.us/img703/5692/beznzvuem.png

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

Offline

 

#4 05. 12. 2010 20:07

petrkovar
Veterán
Místo: Ostrava/Krmelín
Příspěvky: 1012
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: hrana grafu

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).

Offline

 

Archiv Matematického Fóra · stav k 30. 8. 2026 · 633 258 příspěvků v 108 818 tématech