Eulerovský graf - Historie editací

Sysop: Nahrazení textu „“ textem „\)“

2022-08-14T14:51:42Z

Nahrazení textu „</math>“ textem „\)</big>“

← Starší verze		Verze z 14. 8. 2022, 14:51
Řádka 6:		Řádka 6:
	== Nakreslení Eulerovského grafu ==		== Nakreslení Eulerovského grafu ==
	Libovolný Eulerovský graf lze nakreslit pomocí '''Flueryho algoritmu''', (volně řečeno "jedním tahem"):		Libovolný Eulerovský graf lze nakreslit pomocí '''Flueryho algoritmu''', (volně řečeno "jedním tahem"):
-	* Vstupem tohoto algoritmu je graf <big>\(G = (V, H)</~~math~~>	+	* Vstupem tohoto algoritmu je graf <big>$G = (V, H)$</big>
-	* <big>\(u</~~math~~>, <big>\(v</~~math~~> jsou počáteční a koncový uzel tahu	+	* <big>$u$</big>, <big>$v$</big> jsou počáteční a koncový uzel tahu
	* Všechny uzly tohoto grafu jsou:		* Všechny uzly tohoto grafu jsou:
-	** Sudého stupně, pak (<big>\(u = v</~~math~~>, tj. tah končí ve stejném místě jako začal)	+	** Sudého stupně, pak (<big>$u = v$</big>, tj. tah končí ve stejném místě jako začal)
-	** Právě dva uzly jsou lichého stupně. (<big>\(u <> v</~~math~~>). Tah poté vede z uzlu <big>\(u</~~math~~> ([[Stupeň vrcholu\|deg]](u) = lichý) do uzlu <big>\(v</~~math~~> (deg(v) = lichý)	+	** Právě dva uzly jsou lichého stupně. (<big>$u <> v$</big>). Tah poté vede z uzlu <big>$u$</big> ([[Stupeň vrcholu\|deg]](u) = lichý) do uzlu <big>$v$</big> (deg(v) = lichý)
-	* Začínáme v uzlu <big>\(u</~~math~~>	+	* Začínáme v uzlu <big>$u$</big>
-	* Odebereme(tj. nakreslíme) vždy hranu <big>\(e = (u, w)</~~math~~> 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 <big>\(w</~~math~~>. Opakujeme tento krok dokud je co odebírat.	+	* Odebereme(tj. nakreslíme) vždy hranu <big>$e = (u, w)$</big> 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 <big>$w$</big>. Opakujeme tento krok dokud je co odebírat.

	== Související články ==		== Související články ==

Sysop: Nahrazení textu „ $“ textem „$ \(“

2022-08-14T14:48:29Z

Nahrazení textu „<math>“ textem „<big>\(“

← Starší verze		Verze z 14. 8. 2022, 14:48
Řádka 6:		Řádka 6:
	== Nakreslení Eulerovského grafu ==		== Nakreslení Eulerovského grafu ==
	Libovolný Eulerovský graf lze nakreslit pomocí '''Flueryho algoritmu''', (volně řečeno "jedním tahem"):		Libovolný Eulerovský graf lze nakreslit pomocí '''Flueryho algoritmu''', (volně řečeno "jedním tahem"):
-	* Vstupem tohoto algoritmu je graf <~~math~~>G = (V, H)</math>	+	* Vstupem tohoto algoritmu je graf <big>\(G = (V, H)</math>
-	* <~~math~~>u</math>, <~~math~~>v</math> jsou počáteční a koncový uzel tahu	+	* <big>\(u</math>, <big>\(v</math> jsou počáteční a koncový uzel tahu
	* Všechny uzly tohoto grafu jsou:		* 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)	+	** Sudého stupně, pak (<big>\(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ý)	+	** Právě dva uzly jsou lichého stupně. (<big>\(u <> v</math>). Tah poté vede z uzlu <big>\(u</math> ([[Stupeň vrcholu\|deg]](u) = lichý) do uzlu <big>\(v</math> (deg(v) = lichý)
-	* Začínáme v uzlu <~~math~~>u</math>	+	* Začínáme v uzlu <big>\(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. Tj. aby zůstal souvislý a přesuneme se na druhou stranu této hrany <~~math~~>w</math>. Opakujeme tento krok dokud je co odebírat.	+	* Odebereme(tj. nakreslíme) vždy hranu <big>\(e = (u, w)</math> 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 <big>\(w</math>. Opakujeme tento krok dokud je co odebírat.

	== Související články ==		== Související články ==

Sysop: + Nový článek

2015-10-08T09:57:47Z

+ Nový článek

Nová stránka

[[File:Labelled Eulergraph.png|thumb|230px|Eulerovský graf – každý uzel grafu má sudý stupeň]]
'''Eulerovský graf''' (zkráceně ''E-graf'') je takový souvislý neorientovaný [[graf (teorie grafů)|graf]], který má všechny [[vrchol (graf)|uzly]] sudého [[stupeň vrcholu|stupně]]. Proto existuje uzavřený tah obsahující všechny jeho hrany.<ref>[http://www.math.fme.vutbr.cz/download.aspx?id_file=3607 ŠLAPAL Josef: SGA-A - Grafy a algoritmy]</ref>

[[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í '''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. Tj. aby zůstal souvislý a přesuneme se na druhou stranu této hrany <math>w</math>. Opakujeme tento krok dokud je co odebírat.

== Související články ==
* [[Eulerovský tah]]
* [[Sedm mostů města Královce]]

== Reference ==
<references />

{{Článek z Wikipedie}}
[[Kategorie:Typy grafů]]

Eulerovský graf - Historie editací

Sysop: Nahrazení textu „“ textem „\)“

Sysop: Nahrazení textu „“ textem „\(“

Sysop: + Nový článek

Sysop: Nahrazení textu „ $“ textem „$ \(“