Vhodný

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 27. března 2022; kontroly vyžadují 2 úpravy .

V teorii grafů je shoda nebo nezávislá množina hran v grafu množina párově nesousedících hran.

Definice

Nechť je dán graf G = ( V , E ), vyhovující M v G je množina párově nesousedících hran, tedy hran, které nemají společné vrcholy, tzn. . $\forall e,f\in M:e\cap f=\emptyset$

Související definice

Maximální shoda je shoda M v grafu G , která není obsažena v žádné jiné shodě tohoto grafu, to znamená, že k němu nelze přidat jedinou hranu, která nesousedí se všemi hranami shody. Jinými slovy, shoda M grafu G je maximální, jestliže jakákoli hrana v G má neprázdný průsečík s alespoň jednou hranou z M . Níže jsou uvedeny příklady maximálních shod (červené okraje) ve třech grafech [1] .

Největší shoda (nebo shoda maximální velikosti [2] ) je shoda, která obsahuje maximální počet hran. Shodné číslo [3] v grafu je počet hran v největší shodě. Graf může mít sadu největších shod. Navíc každá největší shoda je maximální, ale žádné maximum nebude největší. Následující tři obrázky ukazují největší shody ve stejných třech sloupcích [1] . $\nu (G)$ $G$

Někteří autoři používají termín „maximální shoda“ pro největší shodu [4] [5] [6] [7] .

Dokonalá shoda (nebo 1-faktor ) je shoda, na které se podílejí všechny vrcholy grafu. To znamená, že jakýkoli vrchol grafu je dopadem přesně na jednu hranu zahrnutou do párování. Obrázek (b) na obrázku výše je příkladem takového párování. Jakékoli dokonalé sladění je největší a maximální. Dokonalým sladěním je také zakrytí okrajů minimální velikosti. V obecném případě , kde je číslo pokrytí okrajů grafu , jinými slovy, velikost největší shody nepřesahuje velikost nejmenšího pokrytí okraje. $\nu (G)\leq \rho (G)$ $\rho (G)$ $G$

Téměř dokonalé párování je párování, kterého se neúčastní právě jeden vrchol. To se může stát, pokud má graf lichý počet vrcholů. Na obrázku výše je shoda ve sloupci (c) téměř dokonalá. Pokud pro jakýkoli vrchol v grafu existuje téměř dokonalá shoda, která neobsahuje přesně tento vrchol, graf se nazývá faktor kritický .

Nechť je dáno odpovídající M.

střídavá cesta je cesta, ve které okraje střídavě patří do shody a nepatří do ní.
rozšiřující cesta (nebo rozšiřující cesta) je střídající se cesta začínající a končící volnými vrcholy (tj. neúčastnící se porovnávání).

Bergeovo lemma říká, že shoda je maximální tehdy a jen tehdy, když neexistuje žádná komplementární cesta.

Vlastnosti

Počet dokonalých shod v bipartitním grafu se rovná permanentě jeho matice sousednosti .
V libovolném grafu bez izolovaných vrcholů se počet shod a počet pokrytí hran rovná počtu vrcholů [8] .
- Konkrétně, pokud existuje dokonalá shoda, pak jsou obě čísla | v | / 2.

Jsou-li A a B dvě maximální shody, pak | A | ≤ 2| b | a | b | ≤ 2| A |. Abyste to viděli, poznamenejte si, že každá hrana z B \ A může být spárována s nejvýše dvěma hranami z A \ B , protože A je shoda. Každá hrana A \ B je však konjugována s hranou B \ A , protože B je maximální. Tudíž, $|A\setminus B|\leq 2|B\setminus A|$

Dále máme

|A|=|A\cap B|+|A\setminus B|\leq 2|B\cap A|+2|B\setminus A|=2|B|

Konkrétně to znamená, že jakákoli maximální shoda je 2-aproximace největší shody, stejně jako 2-aproximace minimální maximální shody. Tato nerovnost je přesná. Pokud je například G cesta se 3 hranami a 4 vrcholy, minimální velikost maximální shody je 1 a velikost největší shody je 2.

Polynom shod

Generující funkce počtu k -hranných párování v grafu se nazývá párovací polynom . Nechť G je graf a m k je počet k -hranných shod. Shodný polynom grafu G je

\sum _{{k\geq 0}}m_{k}x^{k}

Existuje další definice shodného polynomu

\sum _{{k\geq 0}}(-1)^{k}m_{k}x^{{n-2k}}

kde n je počet vrcholů v grafu. Obě definice mají své vlastní oblasti použití.

Algoritmy a výpočetní složitost

Největší shoda v bipartitním grafu

Při práci s bipartitními grafy se často objevují problémy s párováním . Najít největší shodu v bipartitním grafu [9] je možná ten nejjednodušší problém. Algoritmus výplňové cesty ji získá tak, že najde cestu výplně z každého vrcholu a přidá ji k odpovídající, pokud je nalezena. Alternativním řešením je, že párování bude doplňováno, pokud existují rozšiřující se komplementární cesty: $G=(V=(X,Y),E)$ $x\in X$ $Y$

Nainstalujte . $M=\emptyset$
Zatímco se rozšiřují cesty doplňování : $P$
1. $M=M\oplus E(P)$

Rozšiřující cesta je cesta ve tvaru, pro který platí pro . Rozšiřující cesta se nazývá rozšiřující cesta if . $v_{0},\{v_{0},v_{1}\},v_{1},\{v_{1},v_{2}\},v_{2},\tečky ,v_ {l-1},\{v_{l-1},v_{l}\},v_{l}$ $\{v_{i-1},v_{i}\}\in M\Leftrightarrow \{v_{i},v_{i+1}\}\notin M$ $0\leqslant i\leqslant l$ $v_{0},v_{l}\notin M$

Lemma: Pro jakýkoli graf , shodu a dokončení cesty platí shoda a . Důkaz: Dovolit , a být počátečním vrcholem , tak a , A být posledním vrcholem , Tak, že a , A být středním vrcholem , tak . Z toho vyplývá, že o jednu hranu více do grafu přibude, než z něj odebere. $G=(V,E)$ $M$ $P$ $M\oplus E(P)$ $|M\oplus E(P)|=|M|+1$ $G'=(V,M)$ $G''=(V,M\oplus E(P))$ $proti$ $P$ $\delta _{G'}(v)=0$ $\delta _{G''}(v)=1$ $w$ $P$ $\delta _{G'}(w)=0$ $\delta _{G''}(š)=1$ $u$ $P$ $\delta _{G'}(u)=\delta _{G''}(u)=1$

Lemma: Pro jakýkoli graf a párování platí následující: graf obsahuje minimum cest dokončení , které se neprotínají ve vrcholech s ohledem na . Důkaz: Let a , zatímco skutečně a a tedy následuje . Nechť pro připojené složky grafu . Z vyplývá $G=(V,E)$ $M$ $N$ $|M|<|N|$ $H=(V,M\oplus N)$ $|N|-|M|$ $M$ $G$ $G_{M}=(V,M)$ $G_{N}=(V,N)$ ${\displaystyle \delta (G_{M})\subset \{0,1\))$ ${\displaystyle \delta (G_{N})\subset \{0,1\))$ ${\displaystyle \delta (H)\subset \{0,1,2\))$ $G_{i}=(V,E_{i})$ $1\leqslant i\leqslant g$ $H$ ${\displaystyle \delta (H)\subset \{0,1,2\))$

${\displaystyle G_{i))$ je izolovaný vrchol nebo
${\displaystyle G_{i))$ je cyklus sudé délky, popř
${\displaystyle G_{i))$ je dráha sudé délky, popř
${\displaystyle G_{i))$ je cesta liché délky

Vrcholy přicházejí střídavě z a . Nechat ${\displaystyle G_{i))$ $M$ $N$ ${\displaystyle d(G_{i})=|E_{i}\cap N|-|E_{i}\cap M|\subset \{-1,0,1\))$

, ale pouze v případě , že jde o rozšiřující cestu. a to znamená, že musí existovat minimum komponent s a v důsledku toho komplementárními cestami. Podle definice spojených komponent se takové komplementární cesty nebudou protínat ve vrcholech. $d(G_{i})=1$ ${\displaystyle G_{i))$ $\sum _{i=1}^{g}d(G_{i})=|N\setminus M|-|M\setminus N|=|N|-|M|$ $|N|-|M|$ ${\displaystyle G_{i))$ $d(G_{i})=1$

Doplňkovou cestu najdete takto:

Daný bipartitní graf a odpovídající . $G=(V,W,E)$ $M$
Vytvořte kde $G'=(V\cup W,E'\cup E'')$
1. ${\displaystyle E'=\{(v,w)\mid \{v,w\}\in E\setminus M\land v\in V\land w\in W\))$
2. ${\displaystyle E''=\{(w,v)\mid \{v,w\}\in M\land v\in V\land w\in W\))$
Hledání komplementární cesty je redukováno na hledání z volného vrcholu do volného vrcholu . $G'$ $v\in V$ $w\in W$

Protože rozšiřující cestu lze nalézt v čase DFS, doba běhu algoritmu je . Toto řešení je ekvivalentní přidání superzdroje s hranami ke všem vrcholům a superstocku s hranami ze všech vrcholů (transformace grafu bude trvat a nalezení maximálního toku z do . Všechny hrany, které tečou z do tvoří maximální shodu a velikost největší shoda se bude rovnat časovémuHopcroft-Karpově rychlejší. Jiný přístup je založen na algoritmu rychlého násobení matic a poskytuje složitost [10] , což je teoreticky lepší pro dostatečně husté grafy , ale v praxi algoritmus je pomalejší [11] $O(|E|)$ $O(|V||E|)$ $s$ $X$ $t$ $Y$ $O(n+m)$ $s$ $t$ $X$ $Y$ $O({\sqrt {V}}E)$ $O(V^{{2,376}})$

Ve váženém bipartitním grafu

Ve váženém bipartitním grafu je každé hraně přiřazena váha. Maximální váha párování v bipartitním grafu [9] je definována jako párování, pro které má součet vah hran párování maximální hodnotu. Pokud graf není úplný bipartitní , jsou chybějící hrany přidány s nulovou váhou. Problém nalezení takové shody je známý jako problém přiřazení . Pozoruhodný maďarský algoritmus řeší problém zadání a byl jedním z prvních kombinatorických optimalizačních algoritmů . Problém lze vyřešit pomocí modifikovaného hledání nejkratší cesty v algoritmu rozšiřující cesty. Pokud je použit Bellman-Fordův algoritmus , bude doba běhu , nebo může být cena hrany posunuta tak, aby dosáhla času při aplikaci Dijkstrova algoritmu s Fibonacciho haldou [12] . [13] $O(V^{2}E)$ $O(V^{2}\log {V}+VE)$

Největší shody

Existuje polynomiální časový algoritmus pro nalezení největší shody nebo shody maximální váhy v nebipartitním grafu. Podle Jacka Edmondse se tomu říká cesta, strom a barva nebo jednoduše Edmondsův algoritmus porovnávání . Algoritmus používá obousměrné oblouky . Zobecnění stejné techniky lze použít k nalezení maximální nezávislé množiny v grafech bez drápů . Edmodsův algoritmus byl následně vylepšen na dobu běhu , což odpovídá algoritmům pro bipartitní grafy [14] . Další (randomizovaný) algoritmus vyvinutý Muchou a Sankovsim (Mucha, Sankowski) [10] , založený na rychlém součinu matic , dává složitost . $O(\sqrt{V}E)$ $O(V^{{2,376}})$

Maximální shody

Maximální shodu lze nalézt pomocí jednoduchého chamtivého algoritmu . Největší maximální shoda je největší shoda, kterou lze nalézt v polynomiálním čase. Implementace pomocí pseudokódu:

Daný hrabě . $G=(V,E)$
Nainstalujte . $M=\emptyset$
Dokud sada není prázdná: $E$
1. Vyberte . $e\in E$
2. Nainstalujte . ${\displaystyle M=M\cup \{e\))$
3. Nainstalujte . ${\displaystyle E=\{e'\in E\mid e'\cap e=\emptyset \))$
Vynést . $M$

Není však znám žádný polynomiální časový algoritmus, který by našel nejmenší maximální shodu , tj. maximální shodu obsahující nejmenší možný počet hran.

Všimněte si, že největší shoda k hran je množina dominující hraně s k hranami. Naopak, za předpokladu minimální množiny s dominující hranou s k hranami, můžeme vytvořit největší shodu s k hranami v polynomiálním čase. Problém nalezení minimální velikosti maximální shody je tedy ekvivalentní problému nalezení minimální množiny dominující hraně [15] . Oba tyto optimalizační problémy jsou známé jako NP-hard a jejich rozpoznávací verze jsou klasickými příklady NP-úplných problémů [16] . Oba problémy lze aproximovat faktorem 2 s polynomiálním časem - stačí najít libovolné maximum odpovídající M [17] .

Výčtové úlohy

Počet shod v grafu je známý jako Hosoyyův index . Výpočet tohoto čísla je #P-complete . Problém zůstává #P-kompletní ve speciálním případě výpisu dokonalých shod v bipartitním grafu , protože výpočet permanentu náhodné matice 0-1 (další #P-úplný problém) je stejný jako výpočet počtu dokonalých shod v bipartitní graf s danou maticí jako maticí sousednosti . Existuje však náhodné aproximační schéma polynomiálního času pro výpočet počtu shod v bipartitním grafu [18] . Nádherný Casteleynův teorém , který říká, že počet dokonalých shod v rovinném grafu lze vypočítat přesně v polynomiálním čase pomocí algoritmu FKT .

Počet dokonalých shod v úplném grafu K n (se sudým n ) je dán dvojitým faktoriálem ( n − 1)!! [19] . Počet shod v kompletním grafu bez omezení, aby byla shoda dokonalá, je dán telefonními čísly [20] .

Nalezení všech hran, odpovídající hrany

Jedním z hlavních problémů v teorii párování je najít všechny hrany, které lze rozšířit na největší párování. Nejlepší deterministický algoritmus pro řešení tohoto problému běží v čase [21] . Existuje randomizovaný algoritmus, který řeší problém v čase [22] . V případě bipartitního grafu můžete najít největší shodu a použít ji k nalezení všech maximálně shodných hran v lineárním čase [23] ; což bude mít za následek pro obecné bipartitní grafy a pro husté bipartitní grafy s . Pokud je předem známa jedna z největších shod [24] , bude celková doba běhu algoritmu . $O(VE)$ ${\tilde {O}}(V^{{2.376}})$ $O(V^{{1/2}}E)$ $O((V/\log V)^{{1/2}}E)$ $E=\Theta (V^{2})$ $O(V+E)$

Charakteristika a poznámky

Königova věta říká, že v bipartitních grafech je velikost největší shody rovna velikosti nejmenšího pokrytí vrcholů . Z toho vyplývá, že pro bipartitní grafy lze problémy s nalezením nejmenšího vertexového pokrytí , největší nezávislé množiny a maximálního vertex biclique řešit v polynomiálním čase .

Hallův teorém (nebo svatební teorém) poskytuje charakterizaci bipartitních grafů, které mají dokonalé shody, zatímco Tuttův teorém poskytuje charakterizaci libovolných grafů.

Dokonalá shoda generuje 1-běžný podgraf , tedy 1-faktor . Obecně platí, že k - regulární podgraf je k -faktor .

Aplikace

Kekule strukturní vzorec aromatických sloučenin sestává z dokonalých shod jejich uhlíkového skeletu , ukazující umístění dvojných vazeb v chemické struktuře . Tyto struktury jsou pojmenovány po Friedrichu Augustovi Kekuleovi , který ukázal, že benzen (z hlediska teorie grafů jde o cyklus 6 vrcholů) lze jako takovou strukturu znázornit [25] .

Index Hosoyya je počet neprázdných shod plus jedna. Používá se ve výpočetní a matematické chemii ke studiu organických sloučenin.

Viz také

Poznámky

↑ 1 2 Stanislav Okulov. Diskrétní matematika. Teorie a praxe řešení problémů v informatice. Studijní příručka . — Litry, 2014-02-07. - S. 186. - 428 s. — ISBN 9785457534674 .
↑ Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, kapitola 5.
↑ Evstigneev V.A., Kasyanov V.N. Sériově paralelní poset // Slovník grafů v informatice / Edited by prof. Viktor Nikolajevič Kasjanov. - Novosibirsk: LLC "Siberian Scientific Publishing House", 2009. - V. 17. - (Návrh a optimalizace programů). - ISBN 978-591124-036-3 .
↑ Fuad Aleskerov, Ella Khabina, Dmitrij Schwartz. Binární vztahy, grafy a kolektivní rozhodnutí . — Litry, 2016-01-28. - S. 22. - 343 s. — ISBN 9785457966925 .
↑ Rubchinsky A. A. Diskrétní matematické modely. Počáteční koncepty a standardní problémy . — Directmedia, 2014-08-06. - S. 136. - 269 s. — ISBN 9785445838029 .
↑ Leonid Gladkov, Vladimir Kureichik, Viktor Kureichik. Genetické algoritmy . — Litry, 2016-01-28. - S. 276. - 367 s. — ISBN 9785457965997 .
↑ Leonid Gladkov, Vladimir Kureichik, Viktor Kureichik, Pavel Sorokoletov. Bioinspirované metody v optimalizaci . — Litry, 2016-01-28. - S. 330. - 381 s. — ISBN 9785457967472 .
↑ Tibor Gallai. Über extreme Punkt- und Kantenmengen // Ann. Univ. sci. Budapešť. Sekta Eötvös. Matematika.. - 1959. - svazek 2 . — s. 133–138 .
↑ 1 2 Douglas Brent West. Úvod do teorie grafů. — 2. - Prentice Hall, 1999. - ISBN 0-13-014400-2 .
↑ 1 2 M. Mucha, P. Sankowski. Maximální shody prostřednictvím Gaussovy eliminace // Proc. 45. IEEE Symp. Základy informatiky . - 2004. - S. 248-255 .
↑ Bala G. Chandran, Dorit S. Hochbaum. Praktická a teoretická vylepšení pro bipartitní párování pomocí algoritmu pseudoflow . - 2011. - arXiv : 1105.1569 . .
↑ M. Fredman, R. Tarjan. Fibonacciho haldy a jejich použití ve vylepšených algoritmech optimalizace sítě // Journal of the ACM . - 1987. - T. 34 , no. 3 . — S. 596–615 .
↑ Rainer Burkard, Mauro Dell'Amico, Silvano Martello. Problémy s přiřazením . - Philadelphia: SIAM, Society for Industrial and Applied Mathematics, 2009. - s . 77-79 , 98. kapitola 4.1.3 Historické poznámky, knihy a přehledy, kapitola 4.4.3 Efektivní implementace
↑ Silvio Micali, Vijay Vazirani. Algoritmus pro nalezení maximální shody v obecných grafech // Proc. 21. IEEE Symp. Základy informatiky . - 1980. - S. 17-27 . - doi : 10.1109/SFCS.1980.12 . $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$
↑ Yannakakis Mihalis, Gavril Fanica. Hranové dominantní množiny v grafech // SIAM Journal on Applied Mathematics. - 1980. - T. 38 , no. 3 . — S. 364–372 . - doi : 10.1137/0138030 .
↑ Michael R. Garey, David S. Johnson. Počítače a neovladatelnost: Průvodce teorií NP-úplnosti . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 . . Hranová dominující množina je diskutována v případě problémů s dominující množinou, Problém GT2 v příloze A1.1. Minimální velikost maximální shoda je problém GT10 v příloze A1.1.
↑ Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, Marco Protasi. Složitost a aproximace: Problémy kombinatorické optimalizace a jejich vlastnosti aproximace. — Springer, 2003. Minimální sada dominujících hran je problém GT3 v příloze B (strana 370). Minimální velikost maximální shoda je úloha GT10 v příloze B (strana 374). Viz také Minimum Edge Dominating Set archivováno 5. září 2013 na Wayback Machine a Minimum Maximal Matching archivováno 6. března 2014 na Wayback Machine na webu kompendium Archivováno 2. října 2013 na Wayback Machine .
↑ Ivona Bezáková, Daniel Štefankovič, Vijay V. Vazirani, Eric Vigoda. Urychlení simulovaného žíhání pro problémy s permanentním a kombinatorickým počítáním // SIAM Journal on Computing . - 2008. - T. 37 , no. 5 . - S. 1429-1454 . - doi : 10.1137/050644033 .
↑ David Callan. Kombinační průzkum identit pro dvojitý faktoriál . - 2009. - arXiv : 0906.1317 .
↑ Extrémní problémy pro topologické indexy v kombinatorické chemii // Journal of Computational Biology . - 2005. - T. 12 , no. 7 . — S. 1004–1013 . - doi : 10.1089/cmb.2005.12.1004 .
↑ Marcelo H. de Carvalho, Joseph Cheriyan. Algoritmus pro ušní dekompozice grafů pokrytých shodou // Proc. ACM/SIAM Symposium on Discrete Algorithms (SODA). - 2005. - S. 415-423 . $O(VE)$
↑ Michael O. Rabin, Vijay V. Vazirani. Maximální shody v obecných grafech pomocí randomizace // J. of Algorithms. - 1989. - T. 10 . — S. 557–567 .
↑ Tamir Tassa. Nalezení všech maximálně porovnatelných hran v bipartitním grafu // Teoretická informatika . - 2012. - T. 423 . — S. 50–58 . - doi : 10.1016/j.tcs.2011.12.071 .
↑ Aris Gionis, Arnon Mazza, Tamir Tassa. k -Anonymizace revisited // International Conference on Data Engineering (ICDE) . - 2008. - S. 744-753 .
↑ Viz např. Nenad Trinajstić, Douglas J. Klein, Milan Randić. O některých řešených a neřešených problémech chemické teorie grafů . - 1986. - T. 30 , no. S20 . — S. 699–742 . - doi : 10.1002/qua.560300762 .

Čtení pro další čtení

László Lovász, Michael D. Plummer. Teorie shody. - North-Holland, 1986. - ISBN 0-444-87916-1 .
Úvod do algoritmů. - druhý. - MIT Press a McGraw-Hill, 2001. - ISBN 0-262-53196-8 .

SJ Cyvin, Ivan Gutman. Kekule struktury v benzenoidních uhlovodících. — Springer-Verlag, 1988.
Marek Karpinski, Wojciech Rytter. Rychlé paralelní algoritmy pro problémy s párováním grafů . - Oxford University Press, 1998. - ISBN 978-0-19-850162-6 .

Odkazy

Příklad řešení problému na YouTube Archivováno 22. března 2016 na Wayback Machine
Algoritmus pro nalezení největší shody v bipartitním grafu Archivováno 7. ledna 2012 na Wayback Machine
Knihovna grafů s implementací přizpůsobení maximální mohutnosti na bázi Hopcroft-Karpa a Push-Relabel Archivováno 25. října 2005 na Wayback Machine