Eulerovský graf: Porovnání verzí
Smazaný obsah Přidaný obsah
přidání obrázku |
zvýraznění proměnných a výrazů matematickými zápisy + odstranění šablony {{Upravit}} (myslím, že nyní je článek čistý a přehledný) |
||
Řádek 1:
[[File:Labelled Eulergraph.svg|thumb|Eulerovský graf - každý uzel grafu má sudý stupeň]]
'''Eulerovský graf''' (zkráceně ''E-graf'') je takový [[graf (teorie grafů)|graf]], který má všechny [[vrchol (graf)|uzly]] sudého [[stupeň vrcholu|stupně]].
Řádek 5 ⟶ 4:
== Nakreslení Eulerovského grafu ==
Libovolný Eulerovský graf lze nakreslit pomocí '''Flueryho algoritmu''', (volně řečeno "jedním tahem"):
* Vstupem tohoto algoritmu je graf <math>G = (V, H)</math>
* <math>u</math>, <math>v</math> jsou počáteční a koncový uzel tahu
* Všechny uzly tohoto grafu jsou:
** Sudého stupně, pak (<math>u = v</math>, tj. tah končí ve stejném místě jako začal)
** Právě dva uzly jsou lichého stupně. (<math>u <> v</math>). Tah poté vede z uzlu <math>u</math> ([[Stupeň vrcholu|deg]](u) = lichý) do uzlu <math>v</math> (deg(v) = lichý)
* Začínáme v uzlu <math>u</math>
* Odebereme(tj. nakreslíme) vždy hranu <math>e = (u, w)</math> tak, aby po jejím odebrání nebyl zbývající graf rozdělen na několik komponent
== Související články ==
| |||