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 05. 01. 2008 23:20
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Teorie grafů
Zvolme dva vrcholy A, B a spojeme je třemi disjunktními* cestami délek k, l, m. Kolik má takový graf koster?
A pro jakou trojici k,l,m je to rovno 1013?
No a pokud dojdeme k rovnici
mk+ml+kl=1013
nabízí se úprava
1013+m^2=(k+m)(l+m)
Zvolme m=1 a využijme vztahu 1014=13*78
*tím chtěl básník říci, že cesty mají společné pouze body A a B
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#4 06. 01. 2008 14:50
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Teorie grafů
Hledaný podgraf není C_1014. Už proto, že žádný podgraf nehledáme :) Navíc nalezený graf (pro k=12 a l=77) má jen 89 vrcholů a obsahuje cykly délek 77+12=89, 12+1=13 a 77+1=78
(odpověď na tvou druhou otázku je proto ano, návod využit byl, nalezený graf obshuje více cyklů.)
Doporučuji alespoň schematicky načrtnout.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#7 08. 01. 2008 20:13
Re: Teorie grafů
Kondr napsal(a):
Hledaný podgraf není C_1014. Už proto, že žádný podgraf nehledáme :) Navíc nalezený graf (pro k=12 a l=77) má jen 89 vrcholů a obsahuje cykly délek 77+12=89, 12+1=13 a 77+1=78
(odpověď na tvou druhou otázku je proto ano, návod využit byl, nalezený graf obshuje více cyklů.)
Doporučuji alespoň schematicky načrtnout.
Možná toho žádám přiliš ale mohl byste mi to nakreslit? Stačí jen náčrt na papír. Byl bych vám moc vděčný. Potřebuji za tenhle projekt dostat co nejvíc bodů. Děkuji
Offline
#9 10. 01. 2008 02:30
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Teorie grafů
↑ eagleson:Nic není nemožné :) Jen mi připadá, že už k tomu snad není co dodat...
Jediný krok, který jsem tam z "didaktických" důvodů přeskočil, byl od grafu s cestami délek k,l,m k rovnici
kl+lm+km=1013.
Je třeba si uvědomit, že pokud přerušíme jednu z cest na dou místech, narušíme spojitost grafu. Pokud přerušíme jen jednu cestu, nedostaneme kostru. Pokud přerušíme cesty všechny, dostaneme nespojitý graf. Proto je potřeba přerušit právě dvě cesty, každou na právě jednom místě. Pkud budeme přerušovat cesty délek k a l, máme kl možností. Pro další dvě dvojice cest jsou ty počty možností km a lm. Proto je počet koster
kl+lm+km=1013.
Jak s touto rovnicí dále nakládatuž jsem psal.
BRKOS - matematický korespondenční seminář pro střední školy
Offline