Matematické Fórum

Pekna uloha. Ja by som postupoval takto.

Ahoj ↑ Iktomi:,
Este jedno zabavne cvicenie na 2-farbenie.

↑ vanok:
K té nové úloze by to asi chtělo nějaké upřesnění (omezení). Zdá se mi, že by se asi nepočítalo "okolí" té jednotahové malůvky. Kdyby se počítalo, pak např. tato situace (která jde namalovat jedním tahem) by nebyla řešitelná - dva stejné čtverečky sousedící jeden s druhým stěnou. Možná, že tato podmínka je dána pojmem "mapa", matematicky se v tom moc nevyznám. Tah se může křížit?

↑ vanok:
Iktomi zrejme myslel to ci sa moze ist po jednej ciare 2x a to sa zrejme nemoze, ale jednobodovy (diskretnobodovy?) samopriesek by nemal vadit.

Skrytý text:

Nie je to nejaka Jordanova veta? Ja som jej dokaz nikdy nepozeral, ale pocul som, ze je dost dlhy. Pointa je tusim v tom, ze ta ciara bude nejake vhodne zobrazenie do a vyuzije sa to ze deli rovinu na 2 casti, nie?

Cize presnesie by sa to dalo formulovat, ze mame mapu=:graf s konecnym poctom vrcholov ktory sa da "vnorit" do roviny: taku ze sa da prejst po nom tak, ze po kadzej hrane ideme prave raz(!).

Totizto mne hned chodili po rozume vselijake krivky co nekonecne vela krat pretinaju sami seba - trivialny priklad, ze sa to potom neda je to co uviedol ↑ Iktomi: a menej trivialny, kde si ani niesom isty ci sa to da alebo nie, alebo co by sa tym vlastne myslelo je Hilbertova krivka (co vyplni celu rovinu).

Uz to mam, aj ked neviem ci je to najjednoduchsia verzia, ale zda sa mi pomerne prehladna.

Skrytý text:

Graf sa da nakreslit jednym tahom prave vtedy ked su vsetky vrcholy parneho stupna. Teraz urobme dualny graf , t.j. ploskam priradime vrcholy a tie spojime hranou, ak su tie plosky v povodnom grafe susedne. A chceme teraz ofarbit vrcholy dvomi farbami tak, aby susedne dva mali vzdy roznu farbu. Najprv si vsimnime ze take male kruznicky v co obiehaju jeden vrchol z maju parnu dlzku a z toho sa nahliadne, ze vsetky kruznice v maju parnu dlzku. Dalo by sa to indukciou vzhladom na pocet vrcholov z ktore obieha. budeme farbit tak, ze si vyberieme lubovolny vrchol a potom bude biely, ak je jeho najmensia vzdialenost od parna a cierny ak neparna. Predpokladajme, ze toto farbenie je nevyhovujuce, cize existuju susedne s rovnakou farbou. Nech vzdialenost potom kedze su susedne, tak a kedze maju rovnaku farbu (t.j. vzdialenost ma rovnaku paritu) dostaneme a teda mame kruznicu dlzky co je spor.

↑ vanok:

↑ vanok:
Dokoncil som moj dokaz, co som vcera nemal chut dopisat.
Na dobre pochopnie je uzitocne si urobit jednu mapu... a na nej pracovovat.

Slovo parita ( francuzky parité, anglicky parity  ... je latiskeho povodu) a v matematike znamena: su  zaroven parne  alebo zaroven neparne.

↑ Brano:,

↑ Iktomi:,
Poznamka:
Skutocne, ak ma nklame moja pamät, mame takyto vysledok.
Kazdy graf, ktory ma
alebo len  vrcholy parneho stupna,
alebo vsetki vrcholy  parneho stupna az na dva
Moze byt
nakresleny jednym tahom
a opacne:
Graf nakresleny jednym tahom je taky ako ten popisany vysie.

Poznamka: ak graf ma prave dve vrcholy neparneho stupna, vtedy jeho jednotahove kreslenie zacina v jednom takom vrchole a konci v druhom.

Cize vdaka tomu dokaz co kolega Brano ako aj ja sme urobili je platny aj v takej formulacii ako pises.(inac v 3°, mojho dokazu ↑ vanok:, som predpokladal tuto situaciu co sa tyka parity vrcholov). No vsak na strednej skole, je lepsie ( podla mna ...a to vdaka empirickej situacii: moznosti ziakov  "skusat" a naviac  ide o intuitivnu situaciu: kde netreba im davat ziadne definiciei)