Eulerovský graf

Technology

12 hours ago

Author

Eulerovský graf (zkráceně E-graf) je takový souvislý neorientovaný graf, který má všechny uzly sudého stupně / existuje uzavřený tah obsahující všechny jeho hrany.

Orientovaný graf je Eulerovský, existuje-li uzavřený tah obsahující všechny jeho hrany.

Nakreslení Eulerovského grafu

Libovolný Eulerovský graf lze nakreslit pomocí Fleuryho algoritmu, (volně řečeno "jedním tahem"): * Vstupem tohoto algoritmu je graf G = (V, H) * u, v jsou počáteční a koncový uzel tahu * Všechny uzly tohoto grafu jsou: ** Sudého stupně, pak (u = v, tj. tah končí ve stejném místě jako začal) ** Právě dva uzly jsou lichého stupně. +more (u v). Tah poté vede z uzlu u (deg(u) = lichý) do uzlu v (deg(v) = lichý) * Začínáme v uzlu u * Odebereme(tj. nakreslíme) vždy hranu e = (u, w) tak, aby po jejím odebrání nebyl zbývající graf rozdělen na několik komponent. Tj. aby zůstal souvislý a přesuneme se na druhou stranu této hrany w. Opakujeme tento krok dokud je co odebírat.