Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 05. 12. 2010 14:40

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

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:   
 

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

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson