Teorie grafů

Diplomová práce, MFF UK
Lukáš Jirovský
Matematika - MIUZV


3. Vybrané problémy / Jednotažky (eulerovské grafy)

Úvod

Kreslení grafů jedním tahem je jednou ze základních úloh teorie grafů - viz Eulerova úloha o procházení po mostech. Pro zjednodušení si úlohu předvedeme na neorientovaných grafech, podobný problém lze řešit i na orientovaných grafech.

Zadání

Nakreslete daný graf G = (V,E) jedním uzavřeným tahem bez zvednutí tužky papíru (žádna hrana se neobtahuje dvakrát). Tento tah začíná i končí ve stejném vrcholu.

Příklad (animace)

Krok animace (č. 1) Krok animace (č. 2) Krok animace (č. 3) Krok animace (č. 4) Krok animace (č. 5) Krok animace (č. 6) Krok animace (č. 7) Krok animace (č. 8) Krok animace (č. 9) Krok animace (č. 10) Krok animace (č. 11)

Animace

Poznámka

Nalezený tah není jediný možný. Tah může začínat (resp. končit) v libovolném vrcholu.

Návod

Graf G je eulerovský, právě když je souvislý a každý vrchol G má sudý stupeň.

Eulerova úloha Sedm mostů Königsbergu

Předchozí věta také vysvětluje, proč je úloha Sedmi mostů města Königsbergu (viz historie) neřešitelná - ačkoliv je graf souvislý, neplatí, že by všechny vrcholy měly sudý stupeň (naopak všechny mají lichý stupeň).

Proč nelze vyřešit úloha Sedmi mostů města Königsbergu
Obr. č. 3.5 - Proč nelze vyřešit úloha Sedmi mostů města Königsbergu?

Otevřené tahy

V literatuře také můžeme najít termín otevřený eulerovský tah - je definován stejně jako tah uzavřený, pouze se nevrací do původního bodu, kde začal.

Jsou-li v grafu právě dva vrcholy lichého stupně, pak existuje otevřený eulerovský tah začínající v jednom z těchto vrcholů a končící v druhém. [5]

Otevřený eulerovský tah
Obr. č. 3.6 - Otevřený eulerovský tah

Úlohy na procvičování


Úvod

Základní pojmy

Vybrané problémy

Procvičování