Cez rieku pretekajúcu týmto mestom viedlo sedem mostov usporiadaných tak, ako je to zakreslené na obrázku. Euler si položil otázku, či existuje prechádzka, v rámci ktorej prejde človek všetky mosty, ale každý z nich len raz. Dá sa v rámci jednej prechádzky prejsť každý most práve jeden raz? Ak áno, ako – ak nie, prečo?
.odpoveď:
Touto úlohou sa začína takmer každá úvodná prednáška z teórie grafov. Pri jej riešení si Euler uvedomil, že celú úlohu možno prekresliť takto: každý z brehov aj ostrovov zakreslíme len ako jeden bod a mosty ako čiary spájajúce jednotlivé body (čím dostaneme takzvaný graf). Otázka o prechádzke sa dá teraz preformulovať ako otázka o grafe. Dá sa tento graf nakresliť jedným ťahom tak, aby sme nijakú čiaru neprešli viac ako raz?
Kľúčom k Eulerovej odpovedi je počet čiar vychádzajúcich z jednotlivých bodov. Ak sa dá nejaký graf nakresliť jedným ťahom, potom z každého bodu okrem začiatočného a konečného musí vychádzať párny počet čiar. Ku každej čiare, ktorou do tohto bodu prídeme, musí totiž existovať iná čiara, ktorou z tohto bodu odídeme.
Graf, ktorý sa dá nakresliť jedným ťahom, teda môže obsahovať najviac dva body s nepárnym počtom čiar (začiatočný a konečný bod). Graf, ktorý vznikol z Eulerovej prechádzky, má štyri body a zo všetkých vychádza nepárny počet čiar (z troch bodov po tri čiary, z jedného päť čiar). Tento graf sa teda jedným ťahom nakresliť nedá.
Keď už sme pri kreslení jedným ťahom, asi každý za nás si z detstva pamätá neúspešné pokusy nakresliť takýmto spôsobom listovú obálku (t. j. obdĺžnik aj s uhlopriečkami). Mnohí z nás si možno spomenú aj na to, že ak sme z obálky urobili domček, čiže ak sme k nej prikreslili ešte strechu, tak to zrazu išlo. Prečo to tak bolo? No ak spočítame čiary vychádzajúce z jednotlivých bodov obálky alebo obálkového domčeka, tak je jasné, prečo boli v jednom prípade všetky pokusy neúspešné a v druhom sa to dalo celkom jednoducho. Fascinujúce na Eulerovom riešení je to, že týmto spôsobom sa otázka nakresliteľnosti jedným ťahom dá veľmi rýchlo a jednoducho rozhodnúť pre ľubovoľne veľký a komplikovaný graf.
.otázka na tento týždeň:
Ak sa pozeráme cez okno z osvetlenej miestnosti do tmavej noci, vidíme v okne svoj zrkadlový obraz. Ak sa cez to isté okno pozeráme cez deň, nijaký odraz nevidíme. Vyzerá to tak, ako keby vonkajšia tma menila vlastnosti okenného skla – ak má sklo za sebou tmu, začne sa správať ako zrkadlo. Ako to tá tma robí, ako mení sklo z nezrkadla na zrkadlo?
Ak ste našli chybu, napíšte na web@tyzden.sk.