V pátek 26. dubna 2024 úderem 22 hodiny začíná naše nová
a opravdu velká série soutěží o nejlepší webovou stránku !!
Proto neváhejte a začněte hned zítra soutěžit o lákavé ceny !!

Párování grafu

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)
m (1 revizi)
(+ Nový článek)
Řá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]]

Verze z 8. 10. 2015, 13:33

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 <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ím grafu lze převést na úlohu toků v sítích.

Externí odkazy

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