Matematické Fórum

Zdravím,

Rád bych si udělal jasno v definicích. Z toho co vím tak:
---
Eulerovským grafem nazýváme graf ve kterém existuje eulerovský tah.

Eulerovský tah je takový tah, který obsahuje každou hranu grafu.

Tah je sled kde se neopakují hrany.
---

Teď  k mému dotazu. Už vícekrát jsem narazil na to, že nutnou podmínkou aby graf byl eulerovský je  jeho souvislost. Je to uvedeno třeba http://www.algoritmy.net/article/33838/Cycle-finding nebo http://cs.wikipedia.org/wiki/Eulerovský_tah (zde to plyne z tvrzení, že ho lze nakreslit jedním tahem).

Nicméně na anglické wikipedii je nutná podmínka formulovaná trochu jinak a daným definicím, které jsem uvedl nijak neodporuje.

An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component.

To by samozřejmě znamenalo, že z toho, že je graf eulerovský neplyne, že ho lze nakreslit jedním tahem.

Zajímal by mě váš názor na toto :)