Párování grafu

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

Příklad perfektního párování, které je zároveň maximální.

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.

Charakteristika

Königův teorém říká, že v bipartitním grafu se maximální párování velikostí rovná minimálnímu vrcholovému pokrytí. Přes tento výsledek může být problém minimálního vrcholového pokrytí a maximální nezávislé množiny vyřešeny v polynomiálním čase u bipartitních grafů.

Perfektní párování je pokrývající 1-regulární podgraf neboli 1-faktor. Obecně pokrývající k-regulární podgraf je k-faktor.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Matching (graph theory) na anglické Wikipedii.

Externí odkazy

Obrázky, zvuky či videa k tématu párování grafu na Wikimedia Commons

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.