Eulerovský ťah

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 (Šablóna:V jazyku, dnešný Kaliningrad) vo Východnom Prusku.

Ak existuje v grafe uzavrený eulerovský ťah, nazývame tento graf taktiež eulerovský. 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ý.

Ak je $G=(V,E)$ neorientovaný graf a $P=(v_0,e_1,v_1,\dots ,e_n,v_m)$ postupnosť, pre ktorú platí, že $\left|E\right|=n\text{ a }\mathrm{\forall }i,j=1,\dots ,n,i\ne j:e_i\ne e_j$, nazývame túto postupnosť eulerovským ťahom. Ak je $v_0=v_m$, 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.