Žil byl kdysi jeden pán,
Euler prý se jmenoval.
A tomu vrtal v hlavě brouk,
královeckých mostů blok.
Dá se přejít tam a zpět?
Na každém mostě posedět?
Kreslil, psal a počítal,
zlobil se a naříkal.
Nevzdal to a přišel na to,
dobrá rada je nad zlato!
Kam vlezeš odtud vylézt musíš
po nové cestě zas to zkusíš.
Tož velké díky Eulerovi,
za rébus jednotahový.
Chytl mě menší záchvat básnického střeva, snad odpustíte. Každopádně tato veršovaná pohádka je založená na skutečné události. Skutečně svého času žil matematik jménem Euler, od nějž pramení jednotahové hlavolamy, které jsem tu před časem hodila. Na některých obrázcích jsem si však vylámala zuby. Jde to vůbec nakreslit jedním tahem? A protože nejsem sama, kdo si kladl tuto otázku, vznikl tento článek.
Příběh sedmi mostů
Ono totiž stejnou otázku si položil už před 300 lety Euler. Jednoho dne přijeli Eulera navštívit přátelé. Euler je chtěl provést po Královci – městě kde zrovna pracoval. A jak už to tak bývá, nejpěknější procházka vedla po nábřeží. Královec se v té době pyšnil sedmi mosty a Euler je chtěl přátelům všechny ukázat. Ale jako matematik na tom nebyl s kondičkou moc slavně a tak si chtěl ušetřit zbytečného chození. Přemýšlel tedy, jak procházku zoptimalizovat tak, aby každý most prošli pouze jednou. Ale ať přemýšlel jak přemýšlel, ne a ne nalézt onu ideální procházku.
Př. 1: Dokážeš Eulerovi najít takovou trasu, aby prošel každým mostem na právě jednou? Mrkni na obrázek 2 vpravo.
Nám, ani tenkrát Eulerovi se to nepovedlo. Když však odebereme jeden most, je to snadné. Euler s přáteli si pak kreslili různé další teoretické města s různým počtem mostů a ostrůvku a bavili se hledáním ideálních procházek celé odpoledne. Na skutečnou procházku už úplně zapoměli.
Eulerovi vrtalo toto téma ještě dlouho hlavou. Mapy měst si zjednodušil do schématických obrázků, které nazval grafy. A založil matematický obor zvaný Teorie grafů.
Pozn.: Bacha na věc, tento Eulerův graf, je něco jiného než graf funkce.
Na obr.3 vidíš graf, který vznikl z kraloveckých mostu (na obr.2) Nepřipomíná ti to něco? Jj, Euler převedl problém projdi jednou sedm mostů, na problém nakresli graf jedním tahem (eulerovsým tahem). A tak vznikl první jednotahový obrázek (graf).
Zelené puntíky (pevninu) nazval uzly grafu a hnědé čáry (mosty) hranami grafu. A ještě jeden pojem z teorie grafů se nám bude hodit – stupeň uzlu je číslo, kterým označíme uzel (pevninu), podle toho kolik hran (mostů) z ní vede.
Př. 2: Dokážeš doplni stupně uzlů v grafu na obr.3 a obr.4? Správnou odpověď zobrazíš, kliknutím na graf.
Př. 3: Jak by mohla vypadat mapa města z grafu na obr.4?
Kdy se dá nakreslit obrázek jedním tahem?
A konečně se dostáváme k tomu, kdy se dá nakreslit obrázek jedním tahem a kdy ne. Euler uvažoval rozumě. Když na nějaký ostrov vlezu jedním mostem, musí tam být jiný, kterým vylezu. Stupně uzlů by měly být sudé (z každého ostrovu musí vést sudý počet mostů).
Toto logické pravidlo však nestačilo. V druhém příkladu jsem našli uzly třetího stupně u známého jednotahového domečku. Zkusíme ale přidat k jedmomu ze sudých uzlů tohoto domečku čárku. Nakreslíme to pak jedním tahem? A tak nějak Euler došel k druhému pravidlu a to že má-li graf uzly lichého stupně, musí být nanejvýš dva.