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
#1 11. 01. 2012 23:06
Věž na šachovnici (grafy)
Ahoj,
už celý den se trápím s touto úlohou http://kam.mff.cuni.cz/~sbirka/show_exe … &e=420 .
Moje myšlenka je následující: Na modré pole můžeme pohlížet jako na vrcholy grafu. Hrany budou reprezentovat sousednost modrých polí. Jako soused se bere první nejbližší modré pole na stejném řádku nebo sloupci. Cílem je abych dokázal že graf obsahuje kružnici (cyklus). Mám hypotézu, že každé rozmístění modrých polí bude obsahovat minimálně 2m hran (bohužel nevím jak to dokázat, to je ten kámen úrazu). Následně mohu tvrdit, že pokud máme 2m vrcholů a minimálně stejný počet hran, pak graf bude obsahovat kružnici. Zdá se vám můj postup správný?
Díky za příspěvky
Offline
#3 12. 01. 2012 00:39
Re: Věž na šachovnici (grafy)
Je pozde, mel jsem nejaky napad, ale pak jsem to radsi smazal....
Nejdriv me napadlo jadro grafu, protoze mi to pripominalo jednu hru, ale asi to je blbost. Tvuj napad se mi zda dobrej, alespon myslenka dobra a ted to dotahnout. Ale nepamatuju si z hlavy vsechno co bych na to potreboval.
Taky nevim jestli to uplne dobre chapu - ty musis na nejblizsi modre pole, nebo si muzes vybrat? Ja myslim ze si muzes vybrat a ze ten cyklus tedy nemusi nutne obsahovat vsechna modra pole
Offline
#4 12. 01. 2012 00:44 — Editoval Barny (12. 01. 2012 00:50)
Re: Věž na šachovnici (grafy)
↑ Alkac: Podle mě si můžeš vybrat. Tedy pokud bude na jednom řádku/sloupci např. 6 modrých polí tak můžeš skočit z prvního na poslední. Pokud by to bylo tak, že můžeš jen na nejbližšího souseda, bylo by snadné najít protipříklad rozestavění, kdy věž už nemá pohyb.
No jasně, ten cyklus může mít klidně délku 4 :)
Ten graf nemusí být souvislý!
Offline
#6 13. 01. 2012 14:41
- ruamaixanh
- Místo: Tachov
- Příspěvky: 100
- Reputace: 11
Re: Věž na šachovnici (grafy)
Zdravím,
Mám jedno možné řešení:
Mějme bipartitní graf, kde vrcholy jsou sloupce a řádky. Hrany interpretují věže. Vzniklý graf má 2n hran, a proto má nějaký cyklus. Máme bipartitní graf, a proto zmíněný cyklus je hledaný cyklus na šachovnici.
Offline
#7 13. 01. 2012 21:15
- check_drummer
- Příspěvky: 4952
- Reputace: 106
Re: Věž na šachovnici (grafy)
Ahoj,
ruamaixanh napsal(a):
Zdravím,
Mám jedno možné řešení:
Mějme bipartitní graf, kde vrcholy jsou sloupce a řádky. Hrany interpretují věže. Vzniklý graf má 2n hran, a proto má nějaký cyklus. Máme bipartitní graf, a proto zmíněný cyklus je hledaný cyklus na šachovnici.
Hrany spíše interpretují možné pozice věží - případně modrá pole, že?
Z čeho plyne, že graf má cyklus? Sudý počet hran to sám o sobě nezaručuje...
Díky
"Máte úhel beta." "No to nemám."
Offline
#8 14. 01. 2012 01:19 — Editoval ruamaixanh (14. 01. 2012 01:20)
- ruamaixanh
- Místo: Tachov
- Příspěvky: 100
- Reputace: 11
Re: Věž na šachovnici (grafy)
↑ check_drummer:
tak jsem to napsal špatně, hrany interpretují modrá pole a ne věže. Graf s n vrcholy, který je strom nebo les, má nejvíce n-1 hran. Můžeme to dokázat indukcí. Myslím, že důkaz je možné vygooglit.
Offline