— — Kreslení grafu jedním tahem

Kreslení grafu jedním tahem

Sled: v_{0}, e_{1}, v_{1}, e_{2}, …, e_{n}, v_{n}; e_{i} = {v_{i−1}, v_{i}} Tah: Sled, e_{i} ≠ e_{j} (pro i ≠ j) Uzavřený tah: Tah, v_{0} ≤ v_{m} “Cesta”: Tah, v_{i} ≠ v_{j}

Eulerovský graf

G = (V, E) je Eulerovský (lze nakreslit jedním uzavřeným tahem), pokud existuje uzavřený tah v_{0}, e_{1}, …, e_{m}, v_{m} takový, že:

∀e ∈ E ∃! i : e = e_{i} ∧ ∀v ∈ V ∃ i : v = v_{i}

VĚTA ():

G je eulerovský graf, právě když je G souvislý a všechny stupně jsou sudé.

DŮKAZ:

“⇒”

Uzavřený eulerovský tah dává souvislost (mezi každými 2 vrcholy existuje tah, tedy i sled) i sudé stupně (degv = 2|{i ∈ {1, …, m} : v = v_{i}}|).

“⇐”

Pozorování: Pokud jsou všechny stupně sudé, každou hranou vede uzavřený tah.

Důkaz: Nejdelší tah danou hranou je nutně uzavřený. Q.E.D. G = (V, E) souvislý, všechny stupně sudé. Ukážeme (sporem), že nejdelší

uzavřený tah T v G je eulerovský.

Co by bylo, kdyby nebyl: Ze souvislosti víme, že existuje v ∈ V (T), e ∈ E \ E(T), v ∈ e. V grafu G′ = (V, E \ E(T)) jsou všechny stupně sudé, tedy v G′ existuje uzavřený tah T′, obsahující e.

Ve vrcholu v propojíme T, T′ do jednoho tahu. Schematicky: T-O-D-O: Fig. D0

⇒ nový delší tah, ale T měl být nejdelší! ♯̸ Spor

/L:1 1