Eulerovský graf
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.[1]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/72/Labelled_Eulergraph.svg/220px-Labelled_Eulergraph.svg.png)
Orientovaný graf je Eulerovský, existuje-li uzavřený tah obsahující všechny jeho hrany.
Nakreslení Eulerovského grafu
editovatLibovolný 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)
- Právě dva uzly jsou lichého stupně. (
). Tah poté vede z uzlu
(deg(u) = lichý) do uzlu
(deg(v) = lichý)
- Sudého stupně, pak (
- 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.
Související články
editovatReference
editovat🔥 Top keywords: Hlavní stranaSpeciální:HledáníSupercelaDonald SutherlandMistrovství Evropy ve fotbale 2024Lucie BíláIvan LuťanskýMistrovství Evropy ve fotbaleRadarJaroslav a Dana StodoloviPekař (zpěvák)Martin MikyskaSpeciální:Poslední změnyMistrovství Evropy ve fotbale 2020Heliodor PíkaKiefer SutherlandČeskoJimi HendrixMASH (film)Gerhard AignerMezinárodní dny a rokyMistrovství světa ve fotbaleSlunovratAntoine GriezmannSeverní KoreaJiří Arvéd SmíchovskýJosef Kemr21. červenMeteorologický radarLamine YamalStřelba na Filozofické fakultě Univerzity KarlovyGruzieRobert LewandowskiHawkeye PierceNizozemskoKylian MbappéLetní olympijské hry 2024Filip TurekMikuláš Bek