The English encyclopedia Allmultimedia.org will be launched in two phases.
The final launch of the Allmultimedia.org will take place on February 27, 2026
(shortly after the 2026 Winter Olympics).

Párování grafu

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)
(+ Nový článek)
m (Nahrazení textu „\and“ textem „\land“)
 
(Nejsou zobrazeny 4 mezilehlé verze.)
Řá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 <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í.
 +
 +
'''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 <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\)</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) \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é.
 +
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]]

Aktuální verze z 15. 8. 2022, 17:04

Párování grafu je v teorii grafů taková podmnožina hran 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 \(M \subseteq E\) 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 \(v \in V\) 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í \(M\) jsou všechny vrcholy grafu M-saturované.

Cesta \( P = (v_0, v_1, ..., v_k)\,\) se nazývá M-střídající, pokud \((\forall v \in P)((v_{i-1},v_i) \in M) \land (v_i,v_{i+1}) \notin M) \), 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ím grafu lze převést na úlohu toků v sítích.

Externí odkazy

Citováno z „http://www1fdc.multimediaexpo.cz/mmecz/index.php/P%C3%A1rov%C3%A1n%C3%AD_grafu“