Cuplare (teoria graficelor)

În disciplina matematică a teoriei graficelor , o cuplare sau potrivire (în engleză matching) sau asamblarea muchiilor independente într-un grafic este un set de margini bipartite fără vârfuri comune. Poate fi, de asemenea, un grafic întreg format din margini fără vârfuri comune.

Definiție

Având în vedere un grafic G = ( V , E ), o cuplare M în G este un set de arcuri în perechi neadiacente; adică nu există două margini care să aibă un vârf comun.

Un vârf este împerecheat (sau saturat ) dacă este o extremă a uneia dintre margini în partener . În caz contrar, vârful nu este împerecheat .

Un mate maxim este un mate M al unui grafic G cu proprietatea că dacă orice margine care nu este în M este adăugată la M , nu mai este un mate, adică M este maxim dacă nu este un subset adecvat al oricărui alt cuplaj în graficul G. Cu alte cuvinte, o cuplare M a unui grafic G este maximă dacă fiecare margine din G are o intersecție ne-goală cu cel puțin o margine în M. Figura următoare prezintă exemple de cuplaje maxime (roșii) în trei grafice.

O potrivire maximă (cunoscută și sub denumirea de potrivire cardinală maximă ^[1] ) este o potrivire care conține numărul maxim posibil de margini. Pot exista mai multe perechi maxime. Numărul de colegi $\nu (G)$ ${\ displaystyle \ nu (G)}$ ${\ displaystyle \ nu (G)}$ a unui grafic $G.$ ${\ displaystyle G}$ $G.$ este dimensiunea unui partener maxim. Rețineți că fiecare pereche maximă este maximă, dar nu fiecare pereche maximă este o pereche maximă. Următoarea figură prezintă exemple de colegi maximi în aceleași trei grafice.

O potrivire perfectă (cunoscută și sub numele de factor 1) este o potrivire care se potrivește cu toate vârfurile graficului. Adică, fiecare vârf al graficului este incident exact la o margine a cuplajului. Figura (b) de mai sus este un exemplu de potrivire perfectă. Fiecare potrivire perfectă este maximă și, prin urmare, maximă. În unele dintre literatură, se folosește termenul de cuplare completă . În figura de mai sus, doar partea (b) prezintă o potrivire perfectă. O potrivire perfectă este, de asemenea, o acoperire minimă a muchiei . Prin urmare, $\nu (G)\leq \rho (G)$ ${\ displaystyle \ nu (G) \ leq \ rho (G)}$ ${\ displaystyle \ nu (G) \ leq \ rho (G)}$ , adică, dimensiunea unui mate maxim nu este mai mare decât dimensiunea unei acoperiri minime a vârfului.

Un partener aproape perfect este acela în care exact un vârf nu este împerecheat. Acest lucru se poate întâmpla numai atunci când graficul are un număr impar de vârfuri, iar această cuplare trebuie să fie maximă. În figura de mai sus, partea (c) arată o potrivire aproape perfectă. Dacă, pentru fiecare vârf dintr-un grafic, există o potrivire aproape perfectă care omite doar acel vârf, graficul este numit și critic în ceea ce privește factorii .

Având un cuplaj M ,

o cale alternativă este o cale în care marginile aparțin alternativ cuplajului și nu cuplajului.
o cale de mărire este o cale alternativă care începe de la și se termină pe vârfuri libere (nepereche).

O cuplare poate fi demonstrată a fi maximă dacă și numai dacă nu are o cale de mărire. (Acest rezultat este uneori numit lema lui Berge .)

Proprietate

În orice grafic fără vârfuri izolate, suma numărului de mates și a numărului de acoperiri de margine este egal cu numărul de vârfuri. ^[2] Dacă există o potrivire perfectă, atunci atât numărul de perechi, cât și numărul de învelitoare de margine sunt | V | / 2.

Dacă A și B sunt două cuplaje maxime, atunci | A | ≤ 2 | B | și | B | ≤ 2 | A |. Pentru a vedea acest lucru, observați că fiecare margine din B \ A poate fi adiacentă la cel mult două muchii din A \ B deoarece A este un mate; în plus, fiecare muchie din A \ B este adiacentă unei muchii B \ A prin maximitatea lui B , prin urmare

|A\setminus B|\leq 2|B\setminus A|.

{\ displaystyle | A \ setminus B | \ leq 2 | B \ setminus A |.}

{\ displaystyle | A \ setminus B | \ leq 2 | B \ setminus A |.}

Obținem și asta

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

{\ displaystyle | A | = | A \ cap B | + | A \ setminus B | \ leq 2 | B \ cap A | +2 | B \ setminus A | = 2 | B |.}

{\ displaystyle | A | = | A \ cap B | + | A \ setminus B | \ leq 2 | B \ cap A | +2 | B \ setminus A | = 2 | B |.}

În special, acest lucru arată că orice potrivire maximă este o aproximare 2 a unei potriviri maxime și, de asemenea, o aproximare 2 a unei potriviri maxime. Această inegalitate este strictă: de exemplu, dacă G este o cale cu 3 margini și 4 noduri, dimensiunea unei potriviri minime maxime este 1 și dimensiunea unei potriviri maxime este 2.

Cuplarea polinoamelor

Același subiect în detaliu: Polinomul colegilor .

O funcție care generează numărul de mates de k muchii într-un grafic se numește polinomul mate. Fie G un grafic și m _k numărul de cuplaje ale k muchii. Un polinom de cuplare al lui G este

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

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

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

O altă definiție dă polinomul corespunzător ca

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

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

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

unde n este numărul de vârfuri din grafic. Fiecare tip are utilizările sale; pentru mai multe informații, consultați articolul despre împerechere polinoame.

Algoritmi și complexitate de calcul

În grafice bipartite neponderate

Problemele de cuplare implică adesea grafice bipartite . Găsirea unei cuplări bipartite maxime ^[3] (adesea numită cuplare bipartită cu cardinalitate maximă ) într-un grafic bipartit $G=(V=(X,Y),E)$ ${\ displaystyle G = (V = (X, Y), E)}$ ${\ displaystyle G = (V = (X, Y), E)}$ este poate cea mai simplă problemă.

Algoritmul de cale augmentantă găsește acest lucru obținând o cale de augmentare de la fiecare $x\in X$ ${\ displaystyle x \ în X}$ $x \ în X$ la $\ Y$ ${\ displaystyle \ Y}$ $\ Y$ și adăugându-l la partener dacă există. Deoarece fiecare cale poate fi găsită în timp $\ O(E)$ ${\ displaystyle \ O (E)}$ ${\ displaystyle \ O (E)}$ , timpul de funcționare este $\ O(VE)$ ${\ displaystyle \ O (VE)}$ ${\ displaystyle \ O (VE)}$ . Această soluție este echivalentă cu adăugarea unei surse super $s$ ${\ displaystyle s}$ $s$ cu marginile la toate vârfurile în $\ X$ ${\ displaystyle \ X}$ $\ X$ , și o super chiuvetă $\ t$ ${\ displaystyle \ t}$ $\ t$ cu marginile la toate vârfurile în $\ Y$ ${\ displaystyle \ Y}$ $\ Y$ , și pentru a găsi un flux maxim din $\ s$ ${\ displaystyle \ s}$ $\ s$ la $\ t$ ${\ displaystyle \ t}$ $\ t$ . Toate muchiile cu curgere din $\ X$ ${\ displaystyle \ X}$ $\ X$ la $\ Y$ ${\ displaystyle \ Y}$ $\ Y$ atunci constituie o cuplare maximă.

O îmbunătățire a acestui proces este algoritmul Hopcroft - Karp , care rulează în timp $O({\sqrt {V}}E)$ ${\ displaystyle O ({\ sqrt {V}} E)}$ ${\ displaystyle O ({\ sqrt {V}} E)}$ . O altă abordare se bazează pe algoritmul de multiplicare a matricei rapide și oferă complexitate $O(V^{2,376})$ ${\ displaystyle O (V ^ {2.376})}$ ${\ displaystyle O (V ^ {2,376})}$ , ^[4] ceea ce în teorie este mai bun pentru grafice suficient de dense , dar în practică algoritmul este mai lent. ^[5]

În grafice bipartite ponderate

Într-un grafic bipartit ponderat , fiecare margine are o valoare asociată. O potrivire maximă a graficelor bipartite ^[3] este definită ca o potrivire în care suma valorilor marginilor din potrivire are o valoare maximă. Dacă graficul nu este complet bipartit , vor fi inserate muchiile lipsă cu o valoare zero. Găsirea unei astfel de potriviri este cunoscută ca o problemă de atribuire . Celebrul algoritm maghiar rezolvă problema atribuirii și a fost unul dintre începuturile algoritmilor de optimizare combinatorie. Folosește o căutare de cale mai scurtă modificată în algoritmul de cale augmentantă. Dacă se folosește algoritmul Bellman-Ford pentru această etapă, timpul de execuție al algoritmului maghiar devine $O(V^{2}E)$ ${\ displaystyle O (V ^ {2} E)}$ ${\ displaystyle O (V ^ {2} E)}$ , adică, costul marginilor poate fi variat cu un potențial de realizare a timpului de rulare $O(V^{2}\log {V}+VE)$ ${\ displaystyle O (V ^ {2} \ log {V} + VE)}$ ${\ displaystyle O (V ^ {2} \ log {V} + VE)}$ cu algoritmul Dijkstra și clusterul Fibonacci . ^[6]

În graficele generale

Același subiect în detaliu: algoritmul de cuplare Edmonds .

Există un algoritm de timp polinomial pentru găsirea unei potriviri maxime sau a unei greutăți maxime într-un grafic care nu este bipartit; se datorează lui Jack Edmonds , se numește metoda cale, copac și floare sau pur și simplu algoritmul Edmonds și folosește grafice bidirecte . O generalizare a aceleiași tehnici poate fi utilizată și pentru a găsi seturi maxime independente în grafice fără stele . Algoritmul lui Edmonds a fost ulterior îmbunătățit pentru a funcționa în timp $O({\sqrt {V}}E)$ ${\ displaystyle O ({\ sqrt {V}} E)}$ ${\ displaystyle O ({\ sqrt {V}} E)}$ , echivalând timpul pentru împerecherea maximă bipartită. ^[7]

Un alt algoritm (randomizat) de Mucha și Sankowski, ^[4] bazat pe algoritmul rapid pentru multiplicarea matricilor , oferă o complexitate $O(V^{2,376})$ ${\ displaystyle O (V ^ {2,376})}$ ${\ displaystyle O (V ^ {2,376})}$ .

Cuplaje maxime

O cuplare maximă poate fi găsită cu un algoritm simplu lacom . O potrivire maximă este, de asemenea, o potrivire maximă și, prin urmare, este posibil să găsiți o potrivire maximă mai mare în timp polinomial. Cu toate acestea, nu se cunoaște niciun algoritm de timp polinomial pentru găsirea unei potriviri minime maxime , adică o potrivire maximă care conține cel mai mic număr posibil de muchii.

Rețineți că un mate maxim cu k margini este un set dominant de margini cu k margini. Dimpotrivă, dacă avem un set dominant de margini cu k muchii, putem construi un mate maxim cu k margini în timp polinomial. Astfel, problema găsirii unei potriviri minime maxime este în esență aceeași cu problema găsirii unui set minim dominant de margini. ^[8] Se știe că ambele probleme de optimizare sunt dificile pentru NP ; versiunile decizionale ale acestor probleme sunt exemple clasice de probleme NP-complete . ^[9] Ambele probleme pot fi aproximate într-un factor 2 în timp polinomial: găsește doar o cuplare maximă arbitrară M. ^[10]

Probleme de numărare

Același subiect în detaliu: Indicele Hosoya .

Numărul de cuplări dintr-un grafic este cunoscut sub numele de indicele Hosoya al graficului. Calculul acestei cantități este # P-complet . Rămâne # P-complet în cazul special al numărării numărului de potriviri perfecte într-un grafic bipartit dat, deoarece calculul permanentului unei matrici arbitrare 0-1 (o altă problemă # P-completă) este același cu calcularea numărului de potriviri perfecte în graficul bipartit având matricea dată ca matrice biadiacentă . Cu toate acestea, există o schemă de aproximare randomizată complet polinomială în timp pentru numărarea numărului de colegi bipartiti. ^[11] O remarcabilă teoremă Kasteleyn afirmă că numărul de potriviri perfecte într-un grafic plan poate fi calculat exact în timp polinomial prin intermediul algoritmului FKT .

Numărul de potriviri perfecte într-un grafic complet K _n (cu n par) este dat de factorialul dublu ( n - 1) !!. ^[12] Numerele de meciuri din grafice complete, fără a forța meciurile să fie perfecte, sunt date prin numere de telefon . ^[13]

Găsiți toate marginile care pot fi cuplate maxim

Una dintre problemele de bază ale teoriei cuplării este de a găsi într-un grafic dat toate muchiile care pot fi extinse la o cuplare maximă a graficului. (Astfel de muchii se numesc muchii maxim matcabile sau margini permise .) Cel mai bun algoritm determinist pentru rezolvarea acestei probleme în grafice generale se desfășoară în timp. $O(VE)$ ${\ displaystyle O (VE)}$ ${\ displaystyle O (VE)}$ . ^[14] Există un algoritm randomizat care rezolvă această problemă în timp ${\tilde {O}}(V^{2.376})$ ${\ displaystyle {\ tilde {O}} (V ^ {2.376})}$ ${\ displaystyle {\ tilde {O}} (V ^ {2.376})}$ . ^[15] În cazul graficelor bipartite, este posibil să se găsească o singură cuplare maximă și apoi să o utilizați pentru a găsi toate muchiile cuplabile maxim în timp liniar; ^[16] timpul total de funcționare rezultat este de $O(V^{1/2}E)$ ${\ displaystyle O (V ^ {1/2} E)}$ ${\ displaystyle O (V ^ {1/2} E)}$ pentru grafice bipartite generale e $O((V/\log V)^{1/2}E)$ ${\ displaystyle O ((V / \ log V) ^ {1/2} E)}$ ${\ displaystyle O ((V / \ log V) ^ {1/2} E)}$ pentru grafice dense bipartite cu $E=\Theta (V^{2})$ ${\ displaystyle E = \ Theta (V ^ {2})}$ ${\ displaystyle E = \ Theta (V ^ {2})}$ . În cazurile în care una dintre cuplajele maxime este cunoscută din timp, ^[17] timpul total de execuție al algoritmului este $O(V+E)$ ${\ displaystyle O (V + E)}$ ${\ displaystyle O (V + E)}$ .

Caracterizări și note

Teorema lui König afirmă că, în grafice bipartite, cuplarea maximă este egală ca mărime cu acoperirea minimă a vârfurilor . Prin acest rezultat, problemele acoperirii minime a vârfurilor, a setului maxim independent și a maximului biciclic al vârfurilor pentru grafice bipartite pot fi rezolvate în timp polinomial.

Teorema căsătoriei (sau teorema lui Hall) oferă o caracterizare pentru grafice bipartite care au cuplare perfectă, iar teorema Tutti oferă o caracterizare pentru grafice arbitrare.

O potrivire perfectă este un subgraf care se întinde pe 1 , cunoscut și sub numele de 1 factor . În general, o acoperire sub-grafică k- ajustare este o k- luteinizare .

Aplicații

O structură Kekulé a unui compus aromatic constă dintr-o cuplare perfectă a scheletului său de carbon , arătând localizările dublei legături ale structurii moleculare . aceste structuri poartă numele lui Friedrich August Kekulé von Stradonitz , care a arătat că benzenului (în ceea ce privește teoria graficelor, un ciclu cu 6 vârfuri) i se poate atribui această structură. ^[18]

Indicele Hosoya este numărul de cuplaje ne-goale plus unul; este utilizat în investigații de chimie computațională și chimie matematică pe compuși organici.

Lecturi suplimentare

László Lovász și MD Plummer , Matching Theory , North-Holland, 1986, ISBN 0-444-87916-1 .
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest și Clifford Stein , Introducere în algoritmi , ediția a II-a, MIT Press și McGraw - Hill, 2001, capitolul 26, pp. 643-700, ISBN 0-262-53196-8 .
András Frank , Despre metoda maghiară a lui Kuhn - Un tribut din Ungaria ( PDF ) (raport tehnic), Egerváry Research Group, 2004.
Michael L. Fredman și Robert E. Tarjan , grămezi Fibonacci și utilizările lor în algoritmi de optimizare a rețelei îmbunătățite , în Journal of the ACM , vol. 34, nr. 3, 1987, pp. 595–615, DOI : 10.1145 / 28869.28874 .
SJ Cyvin și Ivan Gutman, Kekule Structures in Benzenoid Hydrocarbons , Springer-Verlag, 1988.
Marek Karpinski și Wojciech Rytter, Algoritmi paraleli rapide pentru probleme de potrivire a graficelor , Oxford University Press, 1998, ISBN 978-0-19-850162-6 .

Notă

^ Alan Gibbons, Teoria algoritmică a graficelor, Cambridge University Press, 1985, capitolul 5.
^ Tibor Gallai, Über extreme Punkt- und Kantenmengen , în Ann. Univ. Ski. Budapesta. Secta Eötvös. Matematica. , vol. 2, 1959, pp. 133–138. .
^ ^a ^b Douglas Brent West, Capitolul 3 , în Introducere în teoria graficelor , ediția a II-a, Prentice Hall, 1999, ISBN 0-13-014400-2 .
^ ^a ^b M. Mucha, Sankowski, P., Maximum Matchings via Gaussian Elimination ( PDF ), în Proc. 45 IEEE Symp. Fundamentele informaticii , 2004, pp. 248-255.
^ Bala G. Chandran și Dorit S. Hochbaum, Ameliorări practice și teoretice pentru potrivirea bipartită utilizând algoritmul pseudoflow , 2011, arXiv : 1105.1569 .
„Algoritmii teoretic eficienți enumerați mai sus în practică tind să funcționeze defectuos . ”
^ Michael L. Fredman, Tarjan, Robert Endre, grămezile Fibonacci și utilizările lor în algoritmi de optimizare a rețelei îmbunătățite , în Journal of the ACM , vol. 34, nr. 3, 1987, pp. 596–615, DOI : 10.1145 / 28869.28874 .
^ S. Micali , Vazirani, VV, An $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ ${\ displaystyle \ scriptstyle O ({\ sqrt {| V |}} \ cdot | E |)}$ ${\ displaystyle \ scriptstyle O ({\ sqrt {| V |}} \ cdot | E |)}$ algoritm pentru găsirea potrivirii maxime în grafice generale , în Proc. 21 IEEE Symp. Fundamentele informaticii , 1980, pp. 17-27, DOI : 10.1109 / SFCS.1980.12 .
^ Mihalis Yannakakis, Fanica, Gavril, Edge dominating sets in graphs , în SIAM Journal on Applied Mathematics , vol. 38, nr. 3, 1980, pp. 364–372, DOI : 10.1137 / 0138030 .
^ Michael R. Garey și David S. Johnson , Computers and Intractability: A Guide to Theory of NP-Completeness , WH Freeman, 1979, ISBN 0-7167-1045-5 . Setul dominant de margini (versiunea de decizie) este discutat sub problema setului dominant, care este problema GT2 în Anexa A1.1. Problema potrivirii maxime minime (versiunea de decizie) este problema GT10 din Anexa A1.1.
^ Giorgio Ausiello, Crescenzi Pierluigi, Gambosi Giorgio, Kann Viggo, Marchetti-Spaccamela Alberto, Protasi Marco, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties , Springer, 2003 .. Setul de margini cel mai puțin dominant (versiunea de optimizare) este problema GT3 din Anexa B (pagina 370). Potrivirea maximă minimă (versiunea de optimizare) este problema GT10 din Anexa B (pagina 374). A se vedea, de asemenea, setul minim care domină marginile și potrivirea minimă minimă în compendiul online.
^ Ivona Bezáková, Štefankovič Daniel, Vazirani Vijay V., Vigoda Eric, Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems , în SIAM Journal on Computing , vol. 37, n. 5, 2008, pp. 1429–1454, DOI : 10.1137 / 050644033 .
^ David Callan, Un studiu combinatorial al identităților pentru factorialul dublu , 2009 ..
^ Robert F. Tichy, Wagner Stephan, Probleme extreme pentru indici topologici în chimia combinatorie ( PDF ), în Journal of Computational Biology , vol. 12, nr. 7, 2005, pp. 1004-1013, DOI : 10.1089 / cmb . 2005.12.1004 . .
^ Marcelo H. de Carvalho și Joseph Cheriyan, An $O(VE)$ ${\ displaystyle O (VE)}$ ${\ displaystyle O (VE)}$ algoritm pentru descompunerea urechii de grafice acoperite de potrivire , în Proc. ACM / SIAM Symposium on Discrete Algorithms (SODA) , 2005, pp. 415–423.
^ Michael O. Rabin și Vijay V. Vazirani, Potriviri maxime în grafice generale prin randomizare , în J. of Algorithms , vol. 10, 1989, pp. 557–567.
^ Tamir Tassa, Găsirea tuturor muchiilor maximal-matchable într-un grafic bipartit , în Theoretical Computer Science , vol. 423, 2012, pp. 50–58, DOI : 10.1016 / j.tcs.2011.12.071 .
^ Aris Gionis, Arnon Mazza și Tamir Tassa, k - Anonimizarea revizuită , în Conferința internațională privind ingineria datelor (ICDE) , 2008, pp. 744-753.
^ Vezi, de exemplu, Nenad Trinajstić , Douglas J. Klein și Milan Randić , Despre unele probleme rezolvate și nerezolvate ale teoriei grafice chimice , în International Journal of Quantum Chemistry , vol. 30, S20, 1986, pp. 699–742, DOI : 10.1002 / qua . 560300762 . .

Alte proiecte

Wikționarul conține dicționarul lema « cuplare »
Wikimedia Commons conține imagini sau alte fișiere despre împerechere

linkuri externe

( EN ) O bibliotecă de grafice cu implementarea cuplajelor de cardinalitate maximă bazate pe Hopcroft - Karp și Push - Relabel , pe lemon.cs.elte.hu .
(IT) Note privind graficele [1]

Controlul autorității	LCCN (EN) sh85082044 · GND (DE) 4831446-8

Portal IT

Portalul de matematică

[1] Alan Gibbons, Teoria algoritmică a graficelor, Cambridge University Press, 1985, capitolul 5.

[2] Tibor Gallai, Über extreme Punkt- und Kantenmengen , în Ann. Univ. Ski. Budapesta. Secta Eötvös. Matematica. , vol. 2, 1959, pp. 133–138. .

[Wes01-3] Douglas Brent West, Capitolul 3 , în Introducere în teoria graficelor , ediția a II-a, Prentice Hall, 1999, ISBN 0-13-014400-2 .

[Mucha-4] M. Mucha, Sankowski, P., Maximum Matchings via Gaussian Elimination ( PDF ), în Proc. 45 IEEE Symp. Fundamentele informaticii , 2004, pp. 248-255.

[5] Bala G. Chandran și Dorit S. Hochbaum, Ameliorări practice și teoretice pentru potrivirea bipartită utilizând algoritmul pseudoflow , 2011, arXiv : 1105.1569 .
„Algoritmii teoretic eficienți enumerați mai sus în practică tind să funcționeze defectuos . ”

[Fredman87-6] Michael L. Fredman, Tarjan, Robert Endre, grămezile Fibonacci și utilizările lor în algoritmi de optimizare a rețelei îmbunătățite , în Journal of the ACM , vol. 34, nr. 3, 1987, pp. 596–615, DOI : 10.1145 / 28869.28874 .

[7] S. Micali , Vazirani, VV, An $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ ${\ displaystyle \ scriptstyle O ({\ sqrt {| V |}} \ cdot | E |)}$ ${\ displaystyle \ scriptstyle O ({\ sqrt {| V |}} \ cdot | E |)}$ algoritm pentru găsirea potrivirii maxime în grafice generale , în Proc. 21 IEEE Symp. Fundamentele informaticii , 1980, pp. 17-27, DOI : 10.1109 / SFCS.1980.12 .

[8] Mihalis Yannakakis, Fanica, Gavril, Edge dominating sets in graphs , în SIAM Journal on Applied Mathematics , vol. 38, nr. 3, 1980, pp. 364–372, DOI : 10.1137 / 0138030 .

[9] Michael R. Garey și David S. Johnson , Computers and Intractability: A Guide to Theory of NP-Completeness , WH Freeman, 1979, ISBN 0-7167-1045-5 . Setul dominant de margini (versiunea de decizie) este discutat sub problema setului dominant, care este problema GT2 în Anexa A1.1. Problema potrivirii maxime minime (versiunea de decizie) este problema GT10 din Anexa A1.1.

[10] Giorgio Ausiello, Crescenzi Pierluigi, Gambosi Giorgio, Kann Viggo, Marchetti-Spaccamela Alberto, Protasi Marco, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties , Springer, 2003 .. Setul de margini cel mai puțin dominant (versiunea de optimizare) este problema GT3 din Anexa B (pagina 370). Potrivirea maximă minimă (versiunea de optimizare) este problema GT10 din Anexa B (pagina 374). A se vedea, de asemenea, setul minim care domină marginile și potrivirea minimă minimă în compendiul online.

[11] Ivona Bezáková, Štefankovič Daniel, Vazirani Vijay V., Vigoda Eric, Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems , în SIAM Journal on Computing , vol. 37, n. 5, 2008, pp. 1429–1454, DOI : 10.1137 / 050644033 .

[12] David Callan, Un studiu combinatorial al identităților pentru factorialul dublu , 2009 ..

[13] Robert F. Tichy, Wagner Stephan, Probleme extreme pentru indici topologici în chimia combinatorie ( PDF ), în Journal of Computational Biology , vol. 12, nr. 7, 2005, pp. 1004-1013, DOI : 10.1089 / cmb . 2005.12.1004 . .

[14] Marcelo H. de Carvalho și Joseph Cheriyan, An $O(VE)$ ${\ displaystyle O (VE)}$ ${\ displaystyle O (VE)}$ algoritm pentru descompunerea urechii de grafice acoperite de potrivire , în Proc. ACM / SIAM Symposium on Discrete Algorithms (SODA) , 2005, pp. 415–423.

[15] Michael O. Rabin și Vijay V. Vazirani, Potriviri maxime în grafice generale prin randomizare , în J. of Algorithms , vol. 10, 1989, pp. 557–567.

[16] Tamir Tassa, Găsirea tuturor muchiilor maximal-matchable într-un grafic bipartit , în Theoretical Computer Science , vol. 423, 2012, pp. 50–58, DOI : 10.1016 / j.tcs.2011.12.071 .

[17] Aris Gionis, Arnon Mazza și Tamir Tassa, k - Anonimizarea revizuită , în Conferința internațională privind ingineria datelor (ICDE) , 2008, pp. 744-753.

[18] Vezi, de exemplu, Nenad Trinajstić , Douglas J. Klein și Milan Randić , Despre unele probleme rezolvate și nerezolvate ale teoriei grafice chimice , în International Journal of Quantum Chemistry , vol. 30, S20, 1986, pp. 699–742, DOI : 10.1002 / qua . 560300762 . .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]