Ribbbeläggning

Ett kanttäcke på en graf är en uppsättning kanter C så att varje vertex på grafen faller in mot åtminstone en kant från C .

Följande figur visar kanttäckningen av två grafer.

Det minsta kantskyddet är det minsta kantskyddet. Antalet kanter i det minsta kantomslaget på en graf kallas kantomslagsnummer och betecknas med (i Swami bok, Thulaliramana - ). Följande bild visar exempel på de minsta kantskydden.

Observera att omslaget till den högra grafen inte bara är ett kantskydd, utan också ett matchande . Dessutom är denna matchning en perfekt matchning - varje vertex i den faller samman med exakt en kant av matchningen. En perfekt matchning (om den finns) är alltid det minsta kantskyddet.

Uppgiften att hitta den minsta kanttäckningen är ett optimeringsproblem , tillhör klassen av täckningsproblem och kan lösas i polynomtid .

Exempel

• Om det inte finns några isolerade hörn i grafen (d.v.s. hörn med grad 0), är uppsättningen av alla kanter ett kantskydd (men inte nödvändigtvis den minsta!). Om det finns isolerade hörn finns det ingen kanttäckning i denna graf.
• Den fullständiga tvådelade grafen K m , n har kanttäckningsnumret max( m , n ).

Egenskaper

• Enligt den andra Gallai-identiteten , i en graf utan isolerade hörn, är det totala antalet kanter i det minsta kantskyddet och den största matchningen lika med antalet hörn i grafen.

Algoritmer

Den minsta kanttäckningen kan hittas i polynomtid genom att hitta den största matchningen och sedan lägga till kanter med hjälp av en girig algoritm för att täcka de återstående hörnen [1] [2] . I följande figur visas den största matchningen i rött. Ytterligare kanter som läggs till för att täcka avslöjade hörn visas i blått (i grafen till höger är den största matchningen en perfekt matchning där alla hörn redan är täckta, så det finns inget behov av ytterligare kanter.)

Se även

• Vertex Cover Problem
• Uppsättningstäckningsproblemet - kanttäckningsproblemet är ett specialfall av uppsättningstäckningsproblemet - befolkningens element är hörn, och varje delmängd täcker exakt två element.

Anteckningar

1. ↑ Garey och Johnson ( Garey, Johnson 1979 ), s. 79, använder kanttäcke och vertextäcke som exempel på ett par liknande problem, varav ett kan lösas i polynomtid och det andra är NP-hårt. Se även sidan 190.
2. ↑ Lawler, 2001 , sid. 222–223.

Litteratur

• Weisstein, Eric W. Edge Cover  (engelska) på Wolfram MathWorld- webbplatsen .
• Michael R. Garey, David S. Johnson. Datorer och svårhanterlighet: En guide till teorin om NP-fullständighet . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 .
• Eugene L. Lawler. Kombinatorisk optimering: nätverk och matroider. - Dover Publications, 2001. - ISBN 978-0-486-41453-9 .
• M. Swami, K. Thulasiraman. 9.2 Kantbeläggningar // Grafer, nätverk och algoritmer. - M . : "Mir", 1984. - S. 179-180.