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

Barny
Zelenáč
Příspěvky: 20
Reputace:   
 

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

 

#2 12. 01. 2012 00:04

Barny
Zelenáč
Příspěvky: 20
Reputace:   
 

Re: Věž na šachovnici (grafy)

Nikdo neví, nebo je prostě už moc pozdě? :)

Offline

 

#3 12. 01. 2012 00:39

Alkac
Příspěvky: 181
Reputace:   10 
 

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)

Barny
Zelenáč
Příspěvky: 20
Reputace:   
 

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

 

#5 12. 01. 2012 13:45

Barny
Zelenáč
Příspěvky: 20
Reputace:   
 

Re: Věž na šachovnici (grafy)

Pořád nikdo nic? Docela nutně to už dneska potřebuji.

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: 4821
Reputace:   105 
 

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

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson