Eulerovský tah

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Sedm mostů města Královce.

V teorii grafů se termínem eulerovský tah označuje takový tah, který obsahuje každou hranu grafu právě jednou. Zavedl jej Leonhard Euler, když se roku 1736 pokoušel vyřešit slavný problém sedmi mostů města Královce.

Existuje-li v grafu uzavřený eulerovský tah, nazýváme tento graf rovněž eulerovský. Eulerovské grafy lze nakreslit „jedním tahem“.

Definice[editovat | editovat zdroj]

Je-li G = (V, E) neorientovaný graf a P = (v_0, e_1, v_1,\ldots, e_n, v_m) posloupnost, pro kterou platí, že \left|E\right| = n\mbox{ a } \forall i, j = 1,\ldots,n\;, i \ne j\;: e_i \ne e_j\; , nazveme tuto posloupnost eulerovským tahem. Je-li v_0 = v_m, nazveme tento tah uzavřeným.

Pro orientované grafy je nutné pojem tah nahradit pojmem cyklus.

Vlastnosti[editovat | editovat zdroj]

  • neorientovaný graf je eulerovský, je-li souvislý a každý jeho vrchol má sudý stupeň
  • neorientovaný graf je eulerovský, je-li souvislý a má-li právě 2 vrcholy lichého stupně. (eulerův tah bude pak otevřený)
  • neorientovaný graf je eulerovský, je-li souvislý a lze jej rozložit na hranově disjunktní cykly
  • orientovaný graf je eulerovský právě tehdy, je-li souvislý a každý jeho vrchol má vstupní stupeň rovný výstupnímu

Počet eulerovských tahů[editovat | editovat zdroj]

V orientovaných grafech lze použitím následujícího vzorce spočítat počet neekvivalentních eulerovských cyklů:

C \prod_{v \in V}(\deg^+(v)-1)!

popřípadě

C \prod_{v \in V}(\deg^-(v)-1)!

kde C je libovolný kofaktor Laplaceovy matice daného grafu.