Acoperirea marginilor
În teoria graficelor , o acoperire a marginilor unui grafic este un set de margini astfel încât fiecare vârf al graficului este incident la cel puțin o margine a setului. În informatică , problema acoperirii marginale minime este problema găsirii unei acoperiri marginale de dimensiune minimă. Este o problemă de optimizare care aparține clasei de probleme de acoperire și poate fi rezolvată în timp polinomial .
Definiție
În mod formal, acoperirea marginilor unui grafic G este un set de margini C astfel încât fiecare vârf din G este incident cu cel puțin o margine în C. Se spune că mulțimea C acoperă vârfurile lui G. Figura următoare prezintă exemple de acoperiri de colț în două grafice.
O acoperire de margine minimă este o acoperire de colț de cea mai mică dimensiune posibilă. Numărul capacelor de margine este dimensiunea acoperirii minime a marginilor. Următoarea figură prezintă exemple de capace de colț minime.
Rețineți că figura din dreapta nu este doar o copertă pe margini, ci și o pereche . În special, este o potrivire perfectă : o potrivire M în care fiecare vârf este incident cu exact un vârf în M. O potrivire perfectă este întotdeauna o acoperire minimă a muchiei.
Exemple
- Setul tuturor muchiilor este o acoperire a marginilor, presupunând că nu există vârfuri de grad 0.
- Graficul bipartit complet K m , n are numărul maxim de capace de margine ( m , n ).
Algoritmi
O acoperire de margine foarte mică poate fi găsită în timp polinomial, găsind o cuplare maximă și extinzându-l „lacom” (adică printr-un „algoritm lacom” ), astfel încât toate vârfurile să fie acoperite. [1] [2] În figura următoare, o cuplare maximă este marcată cu roșu; marginile suplimentare care au fost adăugate pentru a acoperi nodurile nemărite sunt marcate cu albastru. (Figura din dreapta arată un grafic în care o potrivire maximă este o potrivire perfectă ; deci acoperă deja toate vârfurile și nu erau necesare margini suplimentare.)
Pe de altă parte, problema legată de a găsi o acoperire de top foarte mică este o problemă NP-hard . [1]
Notă
- ^ a b Garey & Johnson (1979) , p. 79 , folosește acoperirea marginilor și acoperirea vertexului ca exemplu al unei perechi de probleme similare, dintre care una poate fi rezolvată în timp polinomial, în timp ce cealaltă este NP-hard. A se vedea, de asemenea, p. 190.
- ^ Eugene L. Lawler, Combinatorial optimization: networks and matroids , Dover Publications, 2001, pp. 222–223, ISBN 978-0-486-41453-9 .
Bibliografie
- (EN) Eric W. Weisstein, Edge Cover , în MathWorld Wolfram Research.
- 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 .
Elemente conexe
- Acoperire la summit
- Acoperirea setului - problema acoperirii marginilor este un caz special al problemei acoperirii setului: elementele universului sunt vârfuri și fiecare subset acoperă exact două elemente.
