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
#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