Multimediaexpo.cz je již 18 let na českém internetu !!
Párování grafu
Z Multimediaexpo.cz
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
| Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010 |
|---|
| Informace o článku.
Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. |