náhľad|Sedem mostov mesta Kaliningrad zobrazených ako graf
V teórii grafov sa termínom eulerovský ťah označuje taký ťah, ktorý obsahuje každú hranu grafu práve jeden krát. Zaviedol ho Leonhard Euler, keď sa v roku 1736 pokúšal vyriešiť slávny problém siedmych mostov cez Pregoľu v Kráľovci (, dnešný Kaliningrad) vo Východnom Prusku.
Ak existuje v grafe uzavrený eulerovský ťah, nazývame tento graf taktiež eulerovský.Základní pojmy z teorie grafů. Eulerovské grafy je možné nakresliť „jedným ťahom“. Eulerovské grafy majú každý vrchol párneho stupňa.
Definícia Eulerovský ťah v neorientovanom grafe je taký ťah v ktorom použijeme každú hranu práve raz. Ak takýto ťah existuje graf voláme „prejazdný“ alebo semi-eulerovský.Jun-ichi Yamaguchi, Introduction of Graph Theory .
Ak je neorientovaný graf a postupnosť, pre ktorú platí, že , nazývame túto postupnosť eulerovským ťahom. Ak je , nazývame tento ťah uzavretým.
Vlastnosti neorientovaný graf je eulerovský, ak je súvislý a každý jeho vrchol má párny stupeň, neorientovaný graf je eulerovský, ak je súvislý a ak má práve 2 vrcholy nepárneho stupňa (eulerov ťah bude potom otvorený), neorientovaný graf je eulerovský, ak je súvislý a ide ho rozložiť na hranovo disjunktné cykly.
Referencie
Iné projekty
Kategória:Teória grafov