Stránky: 1
- Hlavní strana
- » Projekty a příklady z Diskrétní matematiky
- » Kostra s nejmenší možnou vahou
#1 30. 12. 2013 22:20
- Sandrastrelcova
- Příspěvky: 36
- Škola: VŠE
- Reputace: 0
Kostra s nejmenší možnou vahou
Je dan uplny graf na n vrcholech {1,2,...,n}. Jeho hrana {i,j} ma vahu w({i,j}) = i+j. Najdete vahu kostry s nejmensi moznou vahou.
Absolutně nevím jak si mám ty hrany ohodnotit podle mého zadání ..a potom jak dokázat kolik to bude, prosím kohokoliv o pomoc, opravdu v tom plavu. Děkuji
Offline
#2 04. 01. 2014 11:48
Re: Kostra s nejmenší možnou vahou
↑ Sandrastrelcova:Doporučuji vyzkoušet na malém příkladu, třeba pro čtyři vrcholy. Hrana mezi vrcholem 1 a 2 bude ohodnocena 1+2=3, hrana mezi 2 a 4 bude ohodnocena 2+4=6.
Podobně pro pět a více vrcholů. Ukáže se, že kostra bude velmi speciálního tvaru.
Offline
#3 04. 01. 2014 13:49
Re: Kostra s nejmenší možnou vahou
Já bych udělal úplný graf o 4 vrcholech, které bych místo A,B,C,D označil jako x, x+1, x+2, x+3. Následně bych určil ceny hran s použitím názvů vrcholu. Tedy
AB = (x) + (x+1) = 2x+1
AC = (x) + (x+2) = 2x+2
AD = (x) + (x+3) = 2x+3
BD = (x+1) + (x+3) = 2x+4
atd...
Protože jsou ceny hran všude 2x+y, podle y bych hledal hladovým algoritmem minimální kostru. Bude to cesta (ab, ac, ad). Cena takové kostry bude (2x+1) + (2x+2) + (2x+3), jinak také 2x(1+2+3). No a z toho bych zkusil odvodit nějakou obecnou definici.
Možná 2(n-1) + (n(n-1) / 2) kde n je počet vrcholů úplného grafu. Ale je to jen tip.
Offline
Stránky: 1
- Hlavní strana
- » Projekty a příklady z Diskrétní matematiky
- » Kostra s nejmenší možnou vahou