Rib belægning

Et kantdæksel på en graf er et sæt kanter C , således at hvert hjørne af grafen falder ind mod mindst én kant fra C .

Følgende figur viser kantdækningen af ​​to grafer.

Det mindste kantdæksel er det mindste kantdæksel. Antallet af kanter i det mindste kantomslag på en graf kaldes kantomslagsnummeret og er angivet med (i Swami-bogen, Thulaliramana - ). Følgende figur viser eksempler på de mindste kantafdækninger.

Bemærk, at omslaget til den højre graf ikke kun er et kantdæksel, men også et matchende . Desuden er denne matchning en perfekt matchning - hvert hjørne i den falder sammen med nøjagtig den ene kant af matchningen. Et perfekt match (hvis det findes) er altid det mindste kantdæksel.

Opgaven med at finde den mindste kantdækning er et optimeringsproblem , hører til klassen af ​​dækningsproblemer og kan løses i polynomisk tid .

Eksempler

• Hvis der ikke er isolerede spidser i grafen (dvs. spidser med grad 0), så er sættet af alle kanter et kantdæksel (men ikke nødvendigvis det mindste!). Hvis der er isolerede hjørner, er der ingen kantdækning i denne graf.
• Den komplette todelte graf K m , n har kantdækningsnummeret max( m , n ).

Egenskaber

• Ifølge den anden Gallai-identitet , i en graf uden isolerede hjørner, er det samlede antal kanter i det mindste kantdæksel og den største matchning lig med antallet af hjørner i grafen.

Algoritmer

Den mindste kantdækning kan findes i polynomisk tid ved at finde den største matchning og derefter tilføje kanter ved hjælp af en grådig algoritme til at dække de resterende hjørner [1] [2] . I den følgende figur er den største matchning vist med rødt. Yderligere kanter, der er tilføjet for at dække udækkede hjørner, er vist med blåt (i grafen til højre er den største matchning en perfekt matchning , hvor alle hjørner allerede er dækket, så der er ikke behov for yderligere kanter).

Se også

• Vertex Cover Problem
• Mængdedækningsproblemet - kantdækningsproblemet er et specialtilfælde af mængdedækningsproblemet - populationens elementer er toppunkter, og hver delmængde dækker præcis to elementer.

Noter

1. ↑ Garey og Johnson ( Garey, Johnson 1979 ), s. 79, bruger kantdæksel og toppunktdæksel som et eksempel på et par lignende problemer, hvoraf det ene kan løses i polynomisk tid, og det andet er NP-hårdt. Se også side 190.
2. ↑ Lawler, 2001 , s. 222-223.

Litteratur

• Weisstein, Eric W. Edge Cover  (engelsk) på Wolfram MathWorld- webstedet .
• Michael R. Garey, David S. Johnson. Computere og intraktabilitet: En guide til teorien om NP-fuldstændighed . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 .
• Eugene L. Lawler. Kombinatorisk optimering: netværk og matroider. - Dover Publications, 2001. - ISBN 978-0-486-41453-9 .
• M. Swami, K. Thulasiraman. 9.2 Kantbelægninger // Grafer, netværk og algoritmer. - M . : "Mir", 1984. - S. 179-180.