Maximálně přizpůsobitelná hrana - Maximally-matchable edge

v teorie grafů, a maximálně přizpůsobitelná hrana v grafu je hrana, která je zahrnuta v alespoň jedné shoda maximální mohutnosti v grafu.^[1] Alternativní termín je povolený okraj.^[2]^[3]

Základní problém v teorie shody je: daný graf G, najděte sadu všech maximálně shodných hran v G. To je ekvivalentní nalezení spojení Všechno maximální počet shody v G (to se liší od jednoduššího problému hledání a singl maximální shoda v G). Je známo několik algoritmů pro tento problém.

Motivace

Zvažte a dohazování agentura se skupinou mužů a žen. Vzhledem k preferencím kandidátů sestavuje agentura a bipartitní graf kde je rozdíl mezi mužem a ženou, pokud jsou kompatibilní. Konečným cílem agentury je vytvořit co nejvíce kompatibilních párů, tj. Najít a shoda maximální mohutnosti v tomto grafu. Ke splnění tohoto cíle si agentura nejprve vybere hranu v grafu a navrhne, aby se muž a žena na obou koncích hrany setkali. Nyní musí agentura dbát na to, aby zvolila pouze maximálně srovnatelnou výhodu. Je to proto, že pokud zvolí hranu, která není maximálně shodná, může se zaseknout hranou, kterou nelze dokončit k dosažení shody s maximální mohutností.^[1]

Definice

Nechat G = (PROTI,E) být graf, kde PROTI jsou vrcholy a E jsou hrany. A vhodný v G je podmnožina M z E, takže každý vrchol v PROTI sousedí maximálně s jednou hranou v M. A maximální shoda je shoda maximální mohutnosti.

Okraj E v E je nazýván maximálně přizpůsobitelný (nebo povoleno) pokud existuje maximální shoda M který obsahuje E.

Algoritmy pro obecné grafy

V současné době je nejznámější deterministický algoritmus pro obecné grafy spuštěn v čase ${ displaystyle O (VE)}$ .^[2]

K dispozici je randomizovaný algoritmus pro obecné grafy v čase ${ displaystyle { tilde {O}} (V ^ {2.376})}$ .^[4]

Algoritmy pro bipartitní grafy

V bipartitních grafech, pokud je jediný shoda maximální mohutnosti je známo, je možné najít všechny maximálně shodné hrany v lineárním čase - ${ displaystyle O (V + E)}$ .^[1]

Pokud maximální shoda není známa, lze ji vyhledat pomocí existujících algoritmů. V tomto případě je výsledná celková doba běhu ${ displaystyle O (V ^ {1/2} E)}$ pro obecné bipartitní grafy a ${ displaystyle O ((V / log V) ^ {1/2} E)}$ pro husté bipartitní grafy s ${ displaystyle E = Theta (V ^ {2})}$ .

Bipartitní grafy s dokonalým spojením

Algoritmus pro nalezení maximálně shodných hran je jednodušší, když graf připouští a perfektní shoda.^[1]^{:díl 2.1}

Nechť je bipartitní graf ${ displaystyle G = (X + Y, E)}$ , kde ${ displaystyle X = (x_ {1}, ldots, x_ {n})}$ a ${ displaystyle Y = (y_ {1}, ldots, y_ {n})}$ . Nechť je dokonalá shoda ${ displaystyle M = {(x_ {1}, y_ {1}), ldots, (x_ {n}, y_ {n}) }}$ .

Teorém: okraj E je maximálně shodný, pokud a pouze-li E je součástí některých M-střídavý cyklus - cyklus, který střídá hrany v M a hrany nejsou uvnitř M. Důkaz:

Li E je ve střídavém cyklu, pak buď E je v M, nebo - převrácením cyklu - získáme novou dokonalou shodu, která obsahuje E. Proto, E je maximálně srovnatelný.
Naopak, pokud E je maximálně přizpůsobitelný, pak je v nějakém dokonalém sladění N. Tím, že vezmeme symetrický rozdíl M a N, můžeme sestrojit střídavý cyklus, který obsahuje E.

Nyní zvažte zaměřený graf ${ displaystyle H = (Z, E)}$ , kde ${ displaystyle Z = (z_ {1}, ldots, z_ {n})}$ a je tu hrana z ${ displaystyle z_ {i}}$ na ${ displaystyle z_ {j}}$ v H iff ${ displaystyle i neq j}$ a mezi nimi je hrana ${ displaystyle x_ {i}}$ a ${ displaystyle y_ {j}}$ v G (všimněte si, že za předpokladu, že takové hrany nejsou v M). Každý M- alternativní cyklus v G odpovídá a řízený cyklus v H. Směrovaná hrana patří do směrovaného cyklu, pokud oba její koncové body patří ke stejnému silně připojená součást. Existují algoritmy pro hledání všech silně propojených komponent v lineárním čase. Proto lze sadu všech maximálně shodných hran najít takto:

Vzhledem k neorientovanému bipartitnímu grafu ${ displaystyle G = (X + Y, E)}$ a perfektní shoda M, označte každý okraj ${ displaystyle (x_ {i}, y_ {i})}$ v M jako maximálně přizpůsobitelné.
Sestavte směrovaný graf ${ displaystyle H = (Z, E)}$ jak je uvedeno výše.
Najděte všechny silně propojené komponenty v H.
Pro každého i, j takhle ${ displaystyle (z_ {i}, z_ {j})}$ jsou ve stejné součásti, označte hranu ${ displaystyle (x_ {i}, y_ {j})}$ jako maximálně přizpůsobitelné.
Označte všechny zbývající hrany jako nepřizpůsobitelné.

Bipartitní grafy bez dokonalé shody

Nechť je bipartitní graf ${ displaystyle G = (X + Y, E)}$ , kde ${ displaystyle X = (x_ {1}, ldots, x_ {n})}$ a ${ displaystyle Y = (y_ {1}, ldots, y_ {n '})}$ a ${ displaystyle n leq n '}$ . Nechť je daná maximální shoda ${ displaystyle M = {(x_ {1}, y_ {1}), ldots, (x_ {t}, y_ {t}) }}$ , kde ${ displaystyle t leq n leq n '}$ . Okraje dovnitř E lze rozdělit do dvou tříd:

Hrany s oběma koncovými body nasycené M. Říkáme takové hrany M-horní.
Hrany s přesně jedním koncovým bodem nasyceným M. Říkáme takové hrany M-nižší.
Všimněte si, že neexistují žádné hrany s oběma koncovými body nenasycenými M, protože by to bylo v rozporu s maximálností M.

Teorém: Všechno M-dolní hrany jsou maximálně srovnatelné.^[1]^:sub.2.2 Důkaz: předpokládejme E = (X_i,y_j) kde X_i je nasycený a y_j není. Poté odstranění (X_i,y_i) z M a přidání (X_i,y_j) přináší nové shody maximální mohutnosti.

Zůstává tedy najít maximálně srovnatelné hrany mezi M- horní.

Nechat H být podgrafem G vyvolané M-nasycené uzly. Všimněte si, že M je perfektní shoda H. Proto je možné pomocí algoritmu předchozí podsekce najít všechny hrany, které jsou maximálně shodné v H. Tassa^[1] vysvětluje, jak najít zbývající maximálně přizpůsobitelné hrany a jak dynamicky aktualizovat sadu maximálně přizpůsobitelných hran, když se změní graf.

Reference

^ ^A ^b ^C ^d ^E ^F Tassa, Tamir (2012-03-16). „Nalezení všech maximálně shodných hran v bipartitním grafu“. Teoretická informatika. 423: 50–58. doi:10.1016 / j.tcs.2011.12.071. ISSN 0304-3975.
^ ^A ^b De Carvalho, Marcelo H .; Cheriyan, Joseph (01.10.2005). „An ${ displaystyle O (VE)}$ algoritmus pro ušní rozklady shodných grafů ". Transakce ACM na algoritmech. 1 (2): 324–337. doi:10.1145/1103963.1103969. ISSN 1549-6325.
^ Lovász, László; Plummer, Michael (18. 8. 2009). Teorie shody. Providence, Rhode Island: American Mathematical Society. doi:10.1090 / chel / 367. ISBN 9780821847596.
^ Rabin, Michael O .; Vazirani, Vijay V. (1989). „Maximální shoda v obecných grafech prostřednictvím randomizace“ (PDF). Journal of Algorithms. 10 (4): 557–567. doi:10.1016/0196-6774(89)90005-9..

[:0-1] A ^b ^C ^d ^E ^F Tassa, Tamir (2012-03-16). „Nalezení všech maximálně shodných hran v bipartitním grafu“. Teoretická informatika. 423: 50–58. doi:10.1016 / j.tcs.2011.12.071. ISSN 0304-3975.

[DCC-2] A ^b De Carvalho, Marcelo H .; Cheriyan, Joseph (01.10.2005). „An ${ displaystyle O (VE)}$ algoritmus pro ušní rozklady shodných grafů ". Transakce ACM na algoritmech. 1 (2): 324–337. doi:10.1145/1103963.1103969. ISSN 1549-6325.

[3] Lovász, László; Plummer, Michael (18. 8. 2009). Teorie shody. Providence, Rhode Island: American Mathematical Society. doi:10.1090 / chel / 367. ISBN 9780821847596.

[:2-4] Rabin, Michael O .; Vazirani, Vijay V. (1989). „Maximální shoda v obecných grafech prostřednictvím randomizace“ (PDF). Journal of Algorithms. 10 (4): 557–567. doi:10.1016/0196-6774(89)90005-9..

[1]

[2]

[3]

[4]