Párování grafu - Historie editací

Sysop: Nahrazení textu „\and“ textem „\land“

2022-08-15T17:04:52Z

Nahrazení textu „\and“ textem „\land“

← Starší verze		Verze z 15. 8. 2022, 17:04
Řádka 19:		Řádka 19:
	V perfektním párování <big>$M$</big> jsou všechny vrcholy grafu M-saturované.		V perfektním párování <big>$M$</big> jsou všechny vrcholy grafu M-saturované.

-	Cesta <big>$ P = (v_0, v_1, ..., v_k)\,$</big> se nazývá '''M-střídající''', pokud <big>$(\forall v \in P)((v_{i-1},v_i) \in M) \~~and~~ (v_i,v_{i+1}) \notin M) $</big>, tj. pokud hrany na této cestě střídavě leží a neleží v M.	+	Cesta <big>$ P = (v_0, v_1, ..., v_k)\,$</big> se nazývá '''M-střídající''', pokud <big>$(\forall v \in P)((v_{i-1},v_i) \in M) \land (v_i,v_{i+1}) \notin M) $</big>, tj. pokud hrany na této cestě střídavě leží a neleží v M.

	M-střídající cestu nazveme '''M-zlepšující''', pokud nejsou její koncové vrcholy M-saturované.		M-střídající cestu nazveme '''M-zlepšující''', pokud nejsou její koncové vrcholy M-saturované.

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

2022-08-14T14:53:20Z

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

← Starší verze		Verze z 14. 8. 2022, 14:53
Řádka 4:		Řádka 4:

	== Definice ==		== Definice ==
-	Nechť ''G'' = (''V'',''E'') je neorientovaný graf. Množina <big>\(M \subseteq E</~~math~~> se nazývá '''párováním grafu''' ''G'', pokud žádné dvě hrany v ''M'' nemají společný vrchol.	+	Nechť ''G'' = (''V'',''E'') je neorientovaný graf. Množina <big>$M \subseteq E$</big> se nazývá '''párováním grafu''' ''G'', pokud žádné dvě hrany v ''M'' nemají společný vrchol.

	Prázdná množina je párováním na každém grafu (nemá žádné páry - hrany). Graf bez hran má pouze prázdné párování.		Prázdná množina je párováním na každém grafu (nemá žádné páry - hrany). Graf bez hran má pouze prázdné párování.
Řádka 16:		Řádka 16:
	== Hledání párování ==		== Hledání párování ==

-	Vrchol <big>\(v \in V</~~math~~> se nazývá '''M-saturovaný''' (M-nasycený), pokud je obsažen v nějaké hraně párování '''M'''.	+	Vrchol <big>$v \in V$</big> se nazývá '''M-saturovaný''' (M-nasycený), pokud je obsažen v nějaké hraně párování '''M'''.
-	V perfektním párování <big>\(M</~~math~~> jsou všechny vrcholy grafu M-saturované.	+	V perfektním párování <big>$M$</big> jsou všechny vrcholy grafu M-saturované.

-	Cesta <big>\( P = (v_0, v_1, ..., v_k)\,</~~math~~> se nazývá '''M-střídající''', pokud <big>\((\forall v \in P)((v_{i-1},v_i) \in M) \and (v_i,v_{i+1}) \notin M) </~~math~~>, tj. pokud hrany na této cestě střídavě leží a neleží v M.	+	Cesta <big>$ P = (v_0, v_1, ..., v_k)\,$</big> se nazývá '''M-střídající''', pokud <big>$(\forall v \in P)((v_{i-1},v_i) \in M) \and (v_i,v_{i+1}) \notin M) $</big>, tj. pokud hrany na této cestě střídavě leží a neleží v M.

	M-střídající cestu nazveme '''M-zlepšující''', pokud nejsou její koncové vrcholy M-saturované.		M-střídající cestu nazveme '''M-zlepšující''', pokud nejsou její koncové vrcholy M-saturované.

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

2022-08-14T14:49:57Z

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

← Starší verze		Verze z 14. 8. 2022, 14:49
Řádka 4:		Řádka 4:

	== Definice ==		== Definice ==
-	Nechť ''G'' = (''V'',''E'') je neorientovaný graf. Množina <~~math~~>M \subseteq E</math> se nazývá '''párováním grafu''' ''G'', pokud žádné dvě hrany v ''M'' nemají společný vrchol.	+	Nechť ''G'' = (''V'',''E'') je neorientovaný graf. Množina <big>\(M \subseteq E</math> se nazývá '''párováním grafu''' ''G'', pokud žádné dvě hrany v ''M'' nemají společný vrchol.

	Prázdná množina je párováním na každém grafu (nemá žádné páry - hrany). Graf bez hran má pouze prázdné párování.		Prázdná množina je párováním na každém grafu (nemá žádné páry - hrany). Graf bez hran má pouze prázdné párování.
Řádka 16:		Řádka 16:
	== Hledání párování ==		== Hledání párování ==

-	Vrchol <~~math~~>v \in V</math> se nazývá '''M-saturovaný''' (M-nasycený), pokud je obsažen v nějaké hraně párování '''M'''.	+	Vrchol <big>\(v \in V</math> se nazývá '''M-saturovaný''' (M-nasycený), pokud je obsažen v nějaké hraně párování '''M'''.
-	V perfektním párování <~~math~~>M</math> jsou všechny vrcholy grafu M-saturované.	+	V perfektním párování <big>\(M</math> jsou všechny vrcholy grafu M-saturované.

-	Cesta <~~math~~> P = (v_0, v_1, ..., v_k)\,</math> se nazývá '''M-střídající''', pokud <~~math~~>(\forall v \in P)((v_{i-1},v_i) \in M) \and (v_i,v_{i+1}) \notin M) </math>, tj. pokud hrany na této cestě střídavě leží a neleží v M.	+	Cesta <big>\( P = (v_0, v_1, ..., v_k)\,</math> se nazývá '''M-střídající''', pokud <big>\((\forall v \in P)((v_{i-1},v_i) \in M) \and (v_i,v_{i+1}) \notin M) </math>, tj. pokud hrany na této cestě střídavě leží a neleží v M.

	M-střídající cestu nazveme '''M-zlepšující''', pokud nejsou její koncové vrcholy M-saturované.		M-střídající cestu nazveme '''M-zlepšující''', pokud nejsou její koncové vrcholy M-saturované.

Sysop: + Nový článek

2015-10-08T13:33:17Z

+ Nový článek

← Starší verze		Verze z 8. 10. 2015, 13:33
Řádka 1:		Řádka 1:
-	~~{{Wikipedia-cs\|~~Párování grafu\|~~700}}~~	+	'''Párování grafu''' je v [[teorie grafů\|teorii grafů]] taková podmnožina hran [[graf (teorie grafů)\|grafu]], že žádné dvě hrany z této množiny nemají společný vrchol.

		+	Idea je taková, že vrcholy grafů dáváme do '''párů'''. Pár může vzniknout jen tam, kde byla hrana. Přitom každý vrchol může být jen v jednom páru. Řadu praktických problémů lze převést na algoritmizované hledání jistého typu párování v grafu.
		+
		+	== Definice ==
		+	Nechť ''G'' = (''V'',''E'') je neorientovaný graf. Množina <math>M \subseteq E</math> se nazývá '''párováním grafu''' ''G'', pokud žádné dvě hrany v ''M'' nemají společný vrchol.
		+
		+	Prázdná množina je párováním na každém grafu (nemá žádné páry - hrany). Graf bez hran má pouze prázdné párování.
		+
		+	'''Maximální párování''' grafu je to párování, které má nejvíce hran.
		+	Graf může mít několik různých maximálních párování. Kružnice sudé délky má právě 2 maximální párování.
		+
		+	'''Perfektní párování''' grafu je párování, které pokrývá všechny vrcholy grafu.
		+	Grafy s lichým počtem vrcholů nemohou mít perfektní párování. Každé perfektní párování je zároveň maximálním párováním.
		+
		+	== Hledání párování ==
		+
		+	Vrchol <math>v \in V</math> se nazývá '''M-saturovaný''' (M-nasycený), pokud je obsažen v nějaké hraně párování '''M'''.
		+	V perfektním párování <math>M</math> jsou všechny vrcholy grafu M-saturované.
		+
		+	Cesta <math> P = (v_0, v_1, ..., v_k)\,</math> se nazývá '''M-střídající''', pokud <math>(\forall v \in P)((v_{i-1},v_i) \in M) \and (v_i,v_{i+1}) \notin M) </math>, tj. pokud hrany na této cestě střídavě leží a neleží v M.
		+
		+	M-střídající cestu nazveme '''M-zlepšující''', pokud nejsou její koncové vrcholy M-saturované.
		+	Takováto '''M-zlepšující''' cesta má sudý počet vrcholů. "Zlepšíme" ji tak, že "prohodíme" pořadí hran. Příklad: z M-zlepšující cesty (1, 2-3, 4-5, 6) dostaneme (1-2, 3-4, 5-6). Tím přidáme do M novou hranu, přitom zachováme vlastnosti párování.
		+
		+	'''Věta (Berge, 1957)''': Párování v grafu G je maximální právě tehdy, když v G neexistuje M-zlepšující cesta.
		+
		+	Nalezení párování v obecném grafu lze provést v polynomiálně omezeném čase. Hledání párování v [[bipartitní graf\|bipartitním grafu]] lze převést na úlohu toků v sítích.
		+
		+	== Externí odkazy ==
		+
		+	{{Článek z Wikipedie}}
	[[Kategorie:Grafové pojmy]]		[[Kategorie:Grafové pojmy]]

Sysop: 1 revizi

2013-09-03T11:47:01Z

1 revizi

← Starší verze

Verze z 3. 9. 2013, 11:47

Sysop: + Nový článek

2012-10-22T01:22:23Z

+ Nový článek

Nová stránka

{{Wikipedia-cs|Párování grafu|700}}

[[Kategorie:Grafové pojmy]]

Párování grafu - Historie editací

Sysop: Nahrazení textu „\and“ textem „\land“

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

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

Sysop: + Nový článek

Sysop: 1 revizi

Sysop: + Nový článek

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