Matematické Fórum

Freedy · 18. 12. 2015 22:32

Dobrý večer,

rád bych se zeptal, jak se řeší následující typ úloh, protože jsem jich moc (víceméně jenom zadání) nenašel, tak se ptám tady.
Mám úplný graf $K_n$ kde $V=\{1,2,...,n\}$ a ohodnocení hran, které je následující $\forall u,v\in V:\omega (\{u,v\})=u+v$ .
Mám najít váhu minimální kostry

Zde je to ještě jednoduché, protože nějakou intiucí můžu dojít k tomu, že kostra 1,2,...,n jistě bude kostrou, která je zároveň stromem (isomorfní cestě Pn) a součet vah bude jistě nejmenší, protože pokud bych začal hledat kostru (pomocí Jarníkova algrotimu), tak vyjdu z bodu 1, nejlevnější hrana je do 2, odtamtud do 3 atd.

Nicméně můj dotaz je spíš, když je zadání stejné, nicméně ohodnocení hran je následující:
$\forall u,v\in V:\omega (\{u,v\})=3u+2v$
Zde netuším, jak je to myšleno, protože $\{u,v\}$ je množina. Je to tedy to samé, jako $\{v,u\}$ , takže pro jednu hranu bych měl mít váhu $\bigg(\omega( \{u,v\})=3u+2v\bigg)\wedge \bigg(\omega( \{u,v\})=3v+2u\bigg)$ ?

A když by to bylo nějak jasně dané, řekněme, že se bere větší z těch možných hodnot, jak by se tedy postupovalo?.

Děkuji předem za nápady
Freedy

Freedy · 19. 12. 2015 17:43 — Editoval Freedy (20. 12. 2015 12:07)

;-/ nikoho nic nenapadá? Stačí jen nápad, nikoliv řešení. Děkuji

stále nikdo nic?

Freedy · 20. 12. 2015 12:07

nikdo nic? :/

petrkovar · 20. 12. 2015 19:14

Já myslím, že příklad není korektně zadaný. Váha hrany závisí na konkrétním označení, což není v pořádku.

Buďme shovívaví a dejme tomu, že bereme v větší než u. Potom bych ale řekl, že nejmenší příspěvek do váhy budou mít ty hrany, kde první vrchol je vždy u=1 a druhý vrchol je v=2,..n. Kostru bych proto čekal jako hvězdu, nikoliv cestu (mimochodem stejně u prvního příkladu.)
Zkusil bych zdůvodnit pomocí nerovnic s parametry u,v.

Freedy · 20. 12. 2015 21:40

jojo toto mě také napadlo, že by se musela brát jednička pro to "u".
Jinak díky aspoň že příspěvek ;) příklad není korektně zadaný, což není správné.

Matematické Fórum

#1 18. 12. 2015 22:32

Minimální kostra

#2 19. 12. 2015 17:43 — Editoval Freedy (20. 12. 2015 12:07)

Re: Minimální kostra

#3 20. 12. 2015 12:07

Re: Minimální kostra

#4 20. 12. 2015 19:14

Re: Minimální kostra

#5 20. 12. 2015 21:40

Re: Minimální kostra