#2 19. 12. 2013 08:23
- vojta_vorel
- Příspěvky: 70
- Škola: MFF UK
- Pozice: student
- Reputace: 5
Re: Kostra grafu
Ahoj
Neměl by to být problém, ber hrany od nejmenší po největší a každou přidej do kostry, pokud by se tím nevytvořila kružnice.
Někdy může existovat víc různých správných výsledků (ale se stejnou celkovou váhou).
Vojta
Offline
#3 19. 12. 2013 09:34
Re: Kostra grafu
↑ element1:
Dobrý den,
ještě si 'matně' vzpmínám na algoritmus:
- na grafu si vybrat libovolnou kružnici a vyškrtnout hranu s maximálním ohodnocením,
- opakovat tak dlouho, pokud na grafu existuje kružnice.
Pokud se tedy nemýlím.
Offline
#4 19. 12. 2013 09:42
Re: Kostra grafu
↑ vojta_vorel: Přesně tuto metodu používám, problémy mám ale např. u vrcholu e, kde jsou 3 hrany s hodnotou 1 a já nevím které si vybrat, abych došel k úplnému řešení. Stejný problém se vyskytne i u vrcholu c s hranou hodnoty 2.
Offline
#5 19. 12. 2013 10:33 — Editoval Jj (19. 12. 2013 10:36)
Re: Kostra grafu
↑ element1:
Metodou uvedenou tady ↑ Jj: jsem dospěl k výsledkům:
Vyšlo mi ohodnocení 35. Snad si vzpomínám dobře že jde o minimální kostru.
Další řešení jsem nehledal.
Pokud se tedy nemýlím.
Offline
#7 19. 12. 2013 12:39
- vojta_vorel
- Příspěvky: 70
- Škola: MFF UK
- Pozice: student
- Reputace: 5
Re: Kostra grafu
Proč ti přišlo, že je to špatně? Zajímá mě to, protože ještě možná budu někdy někomu kostry vysvětlovat.
Dík
Offline