Potrivire

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 27 martie 2022; verificările necesită 2 modificări .

În teoria grafurilor, o potrivire sau un set independent de muchii dintr-un graf este un set de muchii neadiacente în perechi.

Definiție

Fie dat un grafic G = ( V , E ), o potrivire M în G este o mulțime de muchii neadiacente în perechi, adică muchii care nu au vârfuri comune, i.e. . $\forall e,f\in M:e\cap f=\emptyset$

Definiții înrudite

O potrivire maximă este o potrivire M într-un grafic G care nu este conținut în nicio altă potrivire a acestui grafic, adică este imposibil să-i adăugați o singură muchie care nu este adiacentă tuturor muchiilor potrivirii. Cu alte cuvinte, o potrivire M a unui grafic G este maximă dacă orice muchie din G are o intersecție nevidă cu cel puțin o muchie din M . Mai jos sunt exemple de potriviri maxime (margini roșii) în trei grafice [1] .

Cea mai mare potrivire (sau potrivirea dimensiunii maxime [2] ) este potrivirea care conține numărul maxim de muchii. Numărul de potrivire [3] al unui grafic este numărul de muchii din cea mai mare potrivire. Un grafic poate avea un set de potriviri cele mai mari. În plus, orice potrivire cea mai mare este maximă, dar nu orice maxim va fi cel mai mare. Următoarele trei figuri arată cele mai mari potriviri în aceleași trei coloane [1] . $\nu (G)$ $G$

Unii autori folosesc termenul „potrivire maximă” pentru cea mai mare potrivire [4] [5] [6] [7] .

O potrivire perfectă (sau 1-factor ) este o potrivire la care participă toate vârfurile graficului. Adică, orice vârf al graficului este incident cu exact o muchie inclusă în potrivire. Figura (b) din figura de mai sus este un exemplu de astfel de potrivire. Orice potrivire perfectă este cea mai mare și maximă. O potrivire perfectă este și o acoperire de margine de dimensiune minimă. În cazul general , unde este numărul capacului de margine al graficului , cu alte cuvinte, dimensiunea celei mai mari potriviri nu depășește dimensiunea celui mai mic capac de margine. $\nu (G)\leq \rho (G)$ $\rho (G)$ $G$

O potrivire aproape perfectă este o potrivire la care nu participă exact un vârf. Acest lucru se poate întâmpla dacă graficul are un număr impar de vârfuri. În figura de mai sus, potrivirea din coloana (c) este aproape perfectă. Dacă pentru orice vârf din grafic există o potrivire aproape perfectă care nu conține exact acest vârf, graficul se numește factor critic .

Fie dat un M potrivit .

o cale alternativă este o cale în care marginile aparțin alternativ potrivirii și nu îi aparțin.
o cale de creștere (sau cale de creștere) este o cale alternativă care începe și se termină cu vârfuri libere (adică, nu participă la potrivire).

Lema lui Berge afirmă că o potrivire este maximă dacă și numai dacă nu există o cale complementară.

Proprietăți

Numărul de potriviri perfecte într-un graf bipartit este egal cu permanenta matricei de adiacență .
În orice grafic fără vârfuri izolate, numărul de potriviri și numărul de acoperire a muchiei se adună la numărul de vârfuri [8] .
- În special, dacă există o potrivire perfectă, atunci ambele numere sunt | v | / 2.

Dacă A și B sunt două potriviri maxime, atunci | A | ≤ 2| b | și | b | ≤ 2| A |. Pentru a vedea acest lucru, rețineți că fiecare muchie din B \ A poate fi asociată cu cel mult două muchii din A \ B , deoarece A este o potrivire. Cu toate acestea, fiecare muchie A \ B este conjugată cu muchia B \ A deoarece B este maximă. Prin urmare, $|A\setminus B|\leq 2|B\setminus A|$

Mai departe avem

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

În special, aceasta implică faptul că orice potrivire maximă este o aproximare de 2 a celei mai mari potriviri, precum și o aproximare de 2 a potrivirii maxime minime. Această inegalitate este exactă. De exemplu, dacă G este o cale cu 3 muchii și 4 vârfuri, dimensiunea minimă a potrivirii maxime este 1, iar dimensiunea celei mai mari potriviri este 2.

Polinom de potriviri

Funcția generatoare a numărului de potriviri k -muchii dintr-un grafic se numește polinom de potrivire . Fie G un grafic și m k numărul de potriviri k -muchii. Polinomul de potrivire al graficului G este

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

Există o altă definiție a polinomului de potrivire

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

unde n este numărul de vârfuri din grafic. Ambele definiții au propriile lor domenii de aplicare.

Algoritmi și complexitate computațională

Cea mai mare potrivire într-un grafic bipartit

Probleme de potrivire apar adesea atunci când lucrați cu grafice bipartite . Găsirea celei mai mari potriviri într-un graf bipartit [9] este poate cea mai simplă problemă. Algoritmul căii de umplutură îl obține găsind calea de umplutură de la fiecare vârf și adăugând-o la potrivire dacă este găsită o cale. O soluție alternativă este ca potrivirea să fie completată atâta timp cât există căi complementare în extindere: $G=(V=(X,Y),E)$ $x\în X$ $Y$

Instalați . $M=\emptyset$
În timp ce există căi de reaprovizionare în extindere : $P$
1. $M=M\oplus E(P)$

O cale de creștere este o cale de forma pentru care este adevărată pentru . O cale de creștere se numește cale de extindere dacă . $v_{0},\{v_{0},v_{1}\},v_{1},\{v_{1},v_{2}\},v_{2},\dots ,v_ {l-1},\{v_{l-1},v_{l}\},v_{l}$ $\{v_{i-1},v_{i}\}\în M\Leftrightarrow \{v_{i},v_{i+1}\}\notin M$ $0\leqslant i\leqslant l$ $v_{0},v_{l}\notin M$

Lema: Pentru orice grafic , potrivire și completare calea potrivirea și este validă . Demonstrație: Fie , și să fie vârful inițial al lui , deci și , și să fie ultimul vârf al , astfel încât și , și să fie un vârf intermediar al , deci . De aici rezultă că în grafic va fi adăugată încă o muchie decât îndepărtată din acesta. $G=(V,E)$ $M$ $P$ $M\oplus E(P)$ $|M\oplus E(P)|=|M|+1$ $G'=(V,M)$ $G''=(V,M\oplus E(P))$ $v$ $P$ $\delta _{G'}(v)=0$ $\delta _{G''}(v)=1$ $w$ $P$ $\delta _{G'}(w)=0$ $\delta _{G''}(w)=1$ $u$ $P$ $\delta _{G'}(u)=\delta _{G''}(u)=1$

Lema: Pentru orice grafic și potriviri astfel încât următoarele sunt adevărate: graficul conține un minim de căi de completare care nu se intersectează la vârfuri în raport cu . Dovada: Fie și , în timp ce cu adevărat și și astfel urmează . Fie pentru componentele conectate ale graficului . Din urmează $G=(V,E)$ $M$ $N$ $|M|<|N|$ $H=(V,M\oplus N)$ $|N|-|M|$ $M$ $G$ $G_{M}=(V,M)$ $G_{N}=(V,N)$ $\delta (G_{M})\subset \{0,1\}$ $\delta (G_{N})\subset \{0,1\)$ $\delta (H)\subset \{0,1,2\)$ $G_{i}=(V,E_{i})$ $1\leqslant i\leqslant g$ $H$ $\delta (H)\subset \{0,1,2\)$

$G_{i)$ este un vârf izolat sau
$G_{i)$ este un ciclu de lungime uniformă sau
$G_{i)$ este o cale de lungime uniformă, sau
$G_{i)$ este o cale de lungime impară

Vârfurile în provin alternativ de la și . Lăsa $G_{i)$ $M$ $N$ $d(G_{i})=|E_{i}\cap N|-|E_{i}\cap M|\subset \{-1,0,1\)$

, dar numai dacă este o cale de creștere. și asta înseamnă că trebuie să existe un minim de componente cu și, în consecință, trasee complementare. Conform definiției componentelor conectate, astfel de căi complementare nu se vor intersecta la vârfuri. $d(G_{i})=1$ $G_{i)$ $\sum _{i=1}^{g}d(G_{i})=|N\setminus M|-|M\setminus N|=|N|-|M|$ $|N|-|M|$ $G_{i)$ $d(G_{i})=1$

Puteți găsi calea complementară astfel:

Având în vedere un grafic bipartit și o potrivire . $G=(V,W,E)$ $M$
Creați unde $G'=(V\cup W,E'\cup E'')$
1. $E'=\{(v,w)\mid \{v,w\}\in E\setminus M\land v\in V\land w\in W\)$
2. $E''=\{(w,v)\mid \{v,w\}\in M\land v\in V\land w\in W\)$
Căutarea unei căi complementare se reduce la căutarea de la un vârf liber la un vârf liber . $G'$ $v\in V$ $w\in W$

Deoarece calea de creștere poate fi găsită în timpul DFS, timpul de rulare al algoritmului este . Această soluție este echivalentă cu adăugarea unei supersurse cu muchii la toate nodurile și a unui superstock cu muchii de la toate nodurile (transformarea graficului va dura și găsirea fluxului maxim de la până la . Toate muchiile care curg de la pentru a forma o potrivire maximă și dimensiunea din cea mai mare potrivire va fi egală cu Algoritmul timpHopcroft-Karp rapid. O altă abordare se bazează pe algoritmul de multiplicare rapidă a matricei și oferă complexitate [10] , care este mai bună în teorie pentru grafice suficient de dense , dar în practică algoritmul este mai lent. [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}})$

Într-un grafic bipartit ponderat

Într -un grafic bipartit ponderat , fiecărei muchii i se atribuie o pondere. O potrivire maximă a greutății într-un grafic bipartit [9] este definită ca o potrivire pentru care suma greutăților muchiilor potrivirii are o valoare maximă. Dacă graficul nu este un bipartit complet , muchiile lipsă sunt adăugate cu greutate zero. Problema găsirii unei astfel de potriviri este cunoscută sub numele de problema de atribuire . Remarcabilul algoritm maghiar rezolvă problema de atribuire și a fost unul dintre primii algoritmi de optimizare combinatorie . Problema poate fi rezolvată folosind o căutare modificată pe calea cea mai scurtă în algoritmul de creștere a căii. Dacă se folosește algoritmul Bellman-Ford , timpul de rulare va fi , sau prețul marginii poate fi deplasat pentru a ajunge la momentul când se aplică algoritmul lui Dijkstra cu un heap Fibonacci [12] . [13] $O(V^{2}E)$ $O(V^{2}\log {V}+VE)$

Cele mai bune potriviri

Există un algoritm de timp polinomial pentru găsirea celei mai mari potriviri sau a ponderii maxime într-un grafic non-bipartit. După Jack Edmonds se numește metoda cale, arbore și culoare sau pur și simplu algoritmul de potrivire Edmonds . Algoritmul folosește arce bidirecționale . O generalizare a aceleiași tehnici poate fi folosită pentru a găsi setul independent maxim în grafice fără gheare . Algoritmul lui Edmods a fost ulterior îmbunătățit la timpul de rulare , care corespunde algoritmilor pentru graficele bipartite [14] . Un alt algoritm (randomizat) dezvoltat de Mucha și Sankovsim (Mucha, Sankowski) [10] , bazat pe produsul rapid al matricelor , dă complexitate . $O(\sqrt{V}E)$ $O(V^{{2,376}})$

Potriviri maxime

Potrivirea maximă poate fi găsită cu un algoritm simplu lacom . Cea mai mare potrivire maximă este cea mai mare potrivire care poate fi găsită în timp polinomial. Implementare folosind pseudocod:

Numărul dat . $G=(V,E)$
Instalați . $M=\emptyset$
Atâta timp cât setul nu este gol: $E$
1. Alege . $e\in E$
2. Instalați . $M=M\cup \{e\}$
3. Instalați . ${\displaystyle E=\{e'\in E\mid e'\cap e=\emptyset \))$
Scoate afară . $M$

Cu toate acestea, nu se cunoaște niciun algoritm în timp polinomial care să găsească cea mai mică potrivire maximă , adică potrivirea maximă care conține cel mai mic număr posibil de muchii.

Rețineți că cea mai mare potrivire de k muchii este un set dominant de muchii cu k muchii. Dimpotrivă, având în vedere un set dominant de muchii minime cu k muchii, putem construi cea mai mare potrivire cu k muchii în timp polinomial. Astfel, problema găsirii dimensiunii minime a potrivirii maxime este echivalentă cu problema găsirii muchiei dominante a muchiei minime [15] . Ambele probleme de optimizare sunt cunoscute ca NP-hard , iar versiunile lor de recunoaștere sunt exemple clasice de probleme NP-complete [16] . Ambele probleme pot fi aproximate cu un factor de 2 cu timp polinomial - doar găsiți o potrivire maximă arbitrară M [17] .

Sarcini de enumerare

Numărul de potriviri dintr-un grafic este cunoscut sub numele de indicele Hosoyya . Calcularea acestui număr este #P-complet . Problema rămâne #P-completă în cazul special de enumerare a potrivirilor perfecte într-un grafic bipartit , deoarece calcularea permanentei unei matrice aleatoare 0-1 (o altă problemă #P-completă) este la fel cu calcularea numărului de potriviri perfecte în un graf bipartit cu o matrice dată ca matrice de adiacență . Există, totuși, o schemă de aproximare polinomială aleatorie în timp pentru a calcula numărul de potriviri într-un grafic bipartit [18] . O minunată teoremă a lui Casteleyn care afirmă că numărul de potriviri perfecte dintr-un graf plan poate fi calculat exact în timp polinomial folosind algoritmul FKT .

Numărul de potriviri perfecte dintr-un grafic complet K n (cu n par ) este dat de factorialul dublu ( n − 1)!! [19] . Numărul de potriviri dintr-un grafic complet fără limită, astfel încât potrivirea să fie perfectă, este dat de numerele de telefon [20] .

Găsirea tuturor muchiilor, potrivirea muchiilor

Una dintre principalele probleme în teoria potrivirilor este găsirea tuturor marginilor care pot fi extinse la cea mai mare potrivire. Cel mai bun algoritm determinist pentru rezolvarea acestei probleme rulează în timp [21] . Există un algoritm randomizat care rezolvă problema în timp [22] . În cazul unui graf bipartit, puteți găsi cea mai mare potrivire și o puteți utiliza pentru a găsi toate muchiile de potrivire maximă în timp liniar [23] ; ceea ce va rezulta pentru grafurile bipartite generale si pentru grafurile bipartite dense cu . Dacă una dintre cele mai mari potriviri este cunoscută dinainte [24] , timpul total de rulare al algoritmului va fi . $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)$

Caracteristici și observații

Teorema lui König afirmă că, în graficele bipartite, dimensiunea celei mai mari potriviri este egală cu dimensiunea celui mai mic înveliș de vârf . De aici rezultă că, pentru grafurile bipartite, problemele de găsire a celei mai mici acoperiri de vârfuri , a celei mai mari mulțimi independente și a biclicului maxim de vârfuri pot fi rezolvate în timp polinomial .

Teorema lui Hall (sau teorema nunții) oferă o caracterizare a graficelor bipartite care au potriviri perfecte, în timp ce teorema lui Tutt oferă o caracterizare a graficelor arbitrare.

O potrivire perfectă generează un subgraf cu 1 regulat , adică un factor 1 . În general, un subgraf k-regular care se întinde este un factor k .

Aplicații

Formula structurală Kekule a compușilor aromatici constă în potriviri perfecte ale scheletului lor de carbon , arătând locația dublelor legături în structura chimică . Aceste structuri sunt numite după Friedrich August Kekule , care a arătat că benzenul (din punct de vedere al teoriei grafurilor, este un ciclu de 6 vârfuri) poate fi reprezentat ca o astfel de structură [25] .

Indicele Hosoyya este numărul de potriviri nevide plus unu. Este folosit în chimia computațională și matematică pentru a studia compușii organici.

Vezi și

Note

↑ 1 2 Stanislav Okulov. Matematică discretă. Teoria și practica rezolvării problemelor în informatică. Ghid de studiu . — Litri, 07-02-2014. - S. 186. - 428 p. — ISBN 9785457534674 .
↑ Alan Gibbons, Teoria graficelor algoritmice, Cambridge University Press, 1985, capitolul 5.
↑ Evstigneev V.A., Kasyanov V.N. Poset serie-paralel // Dicționar de grafice în informatică / Editat de prof. Viktor Nikolaevici Kasyanov. - Novosibirsk: SRL „Editura Științifică Siberiană”, 2009. - V. 17. - (Proiectarea și optimizarea programelor). - ISBN 978-591124-036-3 .
↑ Fuad Aleskerov, Ella Khabina, Dmitry Schwartz. Relații binare, grafice și decizii colective . — Litri, 28-01-2016. - S. 22. - 343 p. — ISBN 9785457966925 .
↑ Rubchinsky A. A. Modele matematice discrete. Concepte inițiale și probleme standard . — Directmedia, 2014-08-06. - S. 136. - 269 p. — ISBN 9785445838029 .
↑ Leonid Gladkov, Vladimir Kureichik, Viktor Kureichik. Algoritmi genetici . — Litri, 28-01-2016. - S. 276. - 367 p. — ISBN 9785457965997 .
↑ Leonid Gladkov, Vladimir Kureichik, Viktor Kureichik, Pavel Sorokoletov. Metode bioinspirate în optimizare . — Litri, 28-01-2016. - S. 330. - 381 p. — ISBN 9785457967472 .
↑ Tibor Gallai. Über extreme Punkt- und Kantenmengen // Ann. Univ. sci. Budapesta. Eötvös Sect. Matematică.. - 1959. - Vol . 2 . — p. 133–138 .
↑ 1 2 Douglas Brent West. Introducere în teoria grafurilor. — al 2-lea. - Prentice Hall, 1999. - ISBN 0-13-014400-2 .
↑ 1 2 M. Mucha, P. Sankowski. Potriviri maxime prin eliminarea gaussiană // Proc. Al 45-lea IEEE Symp. Bazele Informaticii . - 2004. - S. 248-255 .
↑ Bala G. Chandran, Dorit S. Hochbaum. Îmbunătățiri practice și teoretice pentru potrivirea bipartită folosind algoritmul pseudoflow . - 2011. - arXiv : 1105.1569 . .
↑ M. Fredman, R. Tarjan. Mulțile Fibonacci și utilizările lor în algoritmi îmbunătățiți de optimizare a rețelei // Journal of the ACM . - 1987. - T. 34 , nr. 3 . — S. 596–615 .
↑ Rainer Burkard, Mauro Dell'Amico, Silvano Martello. Probleme de atribuire . - Philadelphia: SIAM, Society for Industrial and Applied Mathematics, 2009. - pp . 77-79 , 98. capitolul 4.1.3 Note istorice, cărți și anchete, capitolul 4.4.3 Implementări eficiente
↑ Silvio Micali, Vijay Vazirani. Un algoritm pentru găsirea potrivirii maxime în graficele generale // Proc. Al 21-lea IEEE Symp. Bazele Informaticii . - 1980. - S. 17-27 . - doi : 10.1109/SFCS.1980.12 . $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$
↑ Yannakakis Mihalis, Gavril Fanica. Seturi dominante în grafice // SIAM Journal on Applied Mathematics. - 1980. - T. 38 , nr. 3 . — S. 364–372 . - doi : 10.1137/0138030 .
↑ Michael R. Garey, David S. Johnson. Calculatoare și intractabilitate: un ghid pentru teoria NP-completeității . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 . . Mulțimea dominantă a muchiei este discutată în cazul problemelor cu mulțimea dominantă, Problema GT2 în Anexa A1.1. Potrivirea maximă a dimensiunii minime este problema GT10 din Anexa A1.1.
↑ Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, Marco Protasi. Complexitate și aproximare: probleme de optimizare combinatorie și proprietățile lor de aproximabilitate. — Springer, 2003. Setul minim de margini dominante este o problemă GT3 din Anexa B (pagina 370). Potrivirea maximă a dimensiunii minime este sarcina GT10 din Anexa B (pagina 374). A se vedea, de asemenea, Setul de dominare a marginilor minime Arhivat la 5 septembrie 2013 la Wayback Machine și Minimum Maximal Matching Arhivat la 6 martie 2014 la Wayback Machine pe compendiul web Arhivat la 2 octombrie 2013 la Wayback Machine .
↑ Ivona Bezáková, Daniel Štefankovič, Vijay V. Vazirani, Eric Vigoda. Accelerarea recoacerii simulate pentru problemele permanente și combinatorii de numărare // SIAM Journal on Computing . - 2008. - T. 37 , nr. 5 . - S. 1429-1454 . - doi : 10.1137/050644033 .
↑ David Callan. Un studiu combinatoriu al identităților pentru factorialul dublu . - 2009. - arXiv : 0906.1317 .
↑ Probleme extreme pentru indici topologici în chimia combinatorie // Journal of Computational Biology . - 2005. - T. 12 , nr. 7 . — S. 1004–1013 . - doi : 10.1089/cmb.2005.12.1004 .
↑ Marcelo H. de Carvalho, Joseph Cheriyan. Un algoritm pentru descompunerea urechii de grafice acoperite de potrivire // Proc. Simpozion ACM/SIAM despre algoritmi discreti (SODA). - 2005. - S. 415-423 . $O(VE)$
↑ Michael O. Rabin, Vijay V. Vazirani. Potriviri maxime în grafice generale prin randomizare // J. de algoritmi. - 1989. - T. 10 . — S. 557–567 .
↑ Tamir Tassa. Găsirea tuturor marginilor care se potrivesc maxim într-un grafic bipartit // Informatică teoretică . - 2012. - T. 423 . — S. 50–58 . - doi : 10.1016/j.tcs.2011.12.071 .
↑ Aris Gionis, Arnon Mazza, Tamir Tassa. k -Anonimizarea revizuită // International Conference on Data Engineering (ICDE) . - 2008. - S. 744-753 .
↑ Vezi, de exemplu, Nenad Trinajstić, Douglas J. Klein, Milan Randić. Despre unele probleme rezolvate și nerezolvate ale teoriei grafurilor chimice . - 1986. - T. 30 , nr. S20 . — S. 699–742 . - doi : 10.1002/qua.560300762 .

Lectură pentru lecturi suplimentare

László Lovász, Michael D. Plummer. Teoria potrivirii. - Olanda de Nord, 1986. - ISBN 0-444-87916-1 .
Introducere în algoritmi. - al doilea. - MIT Press și McGraw-Hill, 2001. - ISBN 0-262-53196-8 .

SJ Cyvin, Ivan Gutman. Structuri Kekule în hidrocarburi benzenoide. — Springer-Verlag, 1988.
Marek Karpinski, Wojciech Rytter. Algoritmi rapidi paraleli pentru problemele de potrivire a graficelor . - Oxford University Press, 1998. - ISBN 978-0-19-850162-6 .

Link -uri

Un exemplu de rezolvare a unei probleme pe YouTube Arhivat 22 martie 2016 pe Wayback Machine
Un algoritm pentru găsirea celei mai mari potriviri într-un grafic bipartit Arhivat la 7 ianuarie 2012 la Wayback Machine
O bibliotecă de grafice cu implementare de potrivire a cardinalității maxime bazată pe Hopcroft-Karp și Push-Relabel Arhivat la 25 octombrie 2005 la Wayback Machine