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.ŠLAPAL Josef: SGA-A - Grafy a algoritmy
Orientovaný graf je Eulerovský, existuje-li uzavřený tah obsahující všechny jeho hrany.
Pokud jsou právě dva uzly lichého stupně, pak se jedná o otevřený Eulerovský tah.
Nakreslení Eulerovského grafu Libovolný Eulerovský graf lze nakreslit pomocí Fleuryho algoritmu, (volně řečeno „jedním tahem“): Vstupem tohoto algoritmu je graf , jsou počáteční a koncový uzel tahu Všechny uzly tohoto grafu jsou: Sudého stupně, pak (, tj. tah končí ve stejném místě jako začal) Začínáme v uzlu Odebereme(tj. nakreslíme) vždy hranu 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 . Opakujeme tento krok dokud je co odebírat. Tento algoritmus lze použít i pro hledání otevřeného Eulerovského taku, ale pak . Odkazy
Reference
Související články Eulerovský tah Sedm mostů města Královce
Kategorie:Typy grafů