I grafteori er en godt dækket graf (nogle gange kaldet en godt skjult graf ) en urettet graf , hvor alle inklusions-minimale toppunktsdæksler har samme størrelse. Veldækkede grafer blev defineret og studeret af Plummer [1] .
Et toppunktsdæksel af en graf er et sæt grafspidser, således at hver kant har mindst én ende i omslaget. En dækning er minimal (irreducerbar), hvis fjernelse af ethvert toppunkt ødelægger dækslet. Et dæksel kaldes det mindste, hvis der ikke er et andet dæksel af grafen med et mindre antal hjørner. En godt dækket graf er en, hvor enhver minimal dækning også er den mindste. I sit originale papir skriver Plummer [1] , at definitionen af en godt dækket graf er "naturligvis ækvivalent" med den egenskab, at to minimale omslag har samme størrelse.
Et uafhængigt sæt af en graf er et sæt af hjørner, hvor der ikke er to hjørner ved siden af hinanden. Hvis C er et toppunktsdæksel af G , skal komplementet af C være et uafhængigt sæt og omvendt. C er det mindste toppunktsdæksel, hvis og kun hvis dets komplement I er det maksimale uafhængige sæt, og C er det mindste toppunktsdæksel, hvis og kun hvis dets komplement er det største uafhængige sæt. Således er en godt dækket graf tilsvarende en graf, hvor hvert maksimalt uafhængigt sæt er det største.
I den originale artikel om godt dækkede grafer gjaldt disse definitioner kun for forbundne grafer [1] , selvom de også giver mening for afbrudte grafer. Nogle senere forfattere har erstattet tilknytningskravet med det svagere krav om, at der ikke er isolerede hjørner [2] . Både forbundne veldækkede grafer og veldækkede grafer uden isolerede toppunkter kan ikke have essentielle toppunkter , toppunkter der hører til hvert mindste toppunktsdæksel [1] . Desuden er enhver godt dækket graf en kritisk graf for toppunktsdæksler i den forstand, at fjernelse af ethvert toppunkt v fra grafen giver en graf med et mindre, mindste toppunktsdæksel [1] .
Uafhængighedskomplekset af en graf G er et simpelt kompleks , der har et simpleks for hver uafhængig mængde i G. Et simplicialt kompleks siges at være simpelt, hvis alle dets maksimale simplices har samme kardinalitet, således at en godt dækket graf svarer til en graf med et simpelt uafhængighedskompleks [3] .
En grafcyklus med længde fire eller fem er godt dækket - i begge tilfælde har det maksimale uafhængige sæt størrelse to. En cyklus på længde syv og en sti på længde tre er også godt dækket. Enhver komplet graf er godt dækket - ethvert maksimalt uafhængigt sæt består af et enkelt toppunkt. En komplet todelt graf er godt dækket, hvis begge dens dele har det samme antal hjørner - den har kun to maksimale uafhængige sæt. Tårngrafen er godt dækket - hvis du placerer et sæt tårne på skakbrættet , så der ikke er to tårne, der angriber hinanden, kan du altid tilføje endnu et ikke-angribende tårn, indtil der er et tårn på hver række og kolonne.
Hvis P er en polygon eller et sæt af punkter, er S sættet af åbne intervaller med toppunkter af P som endepunkter og ingen punkter af P indeni, og G er skæringsgrafen for S ( en graf, der har toppunkter for hvert interval i S og kanter for hvert par af krydsende intervaller), så er G godt dækket. I dette tilfælde svarer ethvert maksimalt uafhængigt sæt i G til et sæt kanter i en polygontriangulering P , og beregning af Euler-karakteristikken viser, at alle to triangulariseringer har det samme antal kanter [4] .
Hvis G er en hvilken som helst graf med n toppunkter, er rodproduktet af G med en enkeltkantsgraf (det vil sige grafen H dannet ved at tilføje n nye toppunkter til G , hver med grad et og alle forbundet med forskellige toppunkter i G ) er godt dækket. Den maksimale uafhængige mængde i H skal bestå af en vilkårlig uafhængig mængde i G , sammen med naboer af grad 1, fra et ekstra sæt. Dette sæt har således størrelse n [5] . Mere generelt er grafen G p dannet ved at tilføje et toppunkt for hver klike godt dækket , givet enhver graf G sammen med klikedækning (opdeling af p toppunkter af G i kliker) . Rodproduktet er et særligt tilfælde af denne konstruktion, når p består af n kliker, der hver indeholder et toppunkt [6] . Enhver graf er således en genereret undergraf af en godt dækket graf.
Favaron definerer en meget godt dækket graf som en veldækket graf (eventuelt afbrudt, men uden isolerede toppunkter), hvor ethvert maksimalt uafhængigt sæt (og derfor også ethvert minimum toppunktdækning) indeholder præcis halvdelen af toppunkterne [2] . Denne definition omfatter rodprodukterne af en graf G og en enkeltkantsgraf. Dette inkluderer for eksempel også todelte godt dækkede grafer, som blev studeret af Ravindra og Berge [7] [8] - i en todelt graf uden isolerede hjørner, danner begge sider af en hvilken som helst del maksimale uafhængige sæt (og minimale toppunktsdæksler) , så hvis grafen er godt dækket, skal begge sider have det samme antal hjørner. I en godt dækket graf med n toppunkter overstiger størrelsen af det maksimale uafhængige sæt ikke n /2 , så meget godt dækkede grafer er godt dækkede grafer, hvor det største uafhængige sæt har den maksimalt mulige størrelse for grafer [8 ] .
En todelt graf G er godt dækket, hvis og kun hvis den er en perfekt matchning af M med den egenskab, at for enhver kant uv fra M danner den genererede undergraf af naboerne u og v en komplet todelt graf [7] [9] . Karakteriseringen med hensyn til matchninger kan udvides fra todelte grafer til meget godt dækkede grafer - en graf G er meget godt dækket, hvis og kun hvis grafen har en perfekt matchende M med følgende to egenskaber:
Men hvis G er meget godt dækket, så opfylder enhver perfekt matchning i G disse egenskaber [10] .
Træer er et særligt tilfælde af todelte grafer, og at teste om et træ er godt dækket kan opfattes som et meget simpelt tilfælde af karakterisering af veldækkede todelte grafer - hvis G er et træ med mere end to toppunkter, er det vel- dækket, hvis og kun hvis hvert ikke-blade kanttræ støder op til præcis ét blad [7] [9] . Den samme karakterisering gælder for grafer, der er lokalt trælignende, i den forstand, at det tætte naboskab til ethvert toppunkt er acyklisk - hvis grafen har en omkreds på otte eller mere (så for ethvert toppunkt v , subgrafen af toppunkter i afstand tre fra v er acyklisk), så er det godt dækket, hvis og kun hvis et toppunkt med grad større end to har nøjagtig en nabo med grad et [11] . En nært beslægtet, men mere kompleks karakterisering gælder for godt dækkede grafer af omkreds fem eller mere [12] [13] .
Kubiske ( 3-regulære ) godt dækkede grafer er klassificeret - familien består af syv 3-forbundne repræsentanter og omfatter desuden tre uendelige familier af mindre forbundne kubiske grafer.
Disse syv 3-forbundne godt dækkede kubiske grafer inkluderer den komplette graf K 4 , de trekantede og femkantede prismegrafer , Durer-grafen , brugsgrafen K 3,3 , otte-vertex Y-Δ-transformationen fra brugsgrafen og den generaliserede Petersen graf G (7,2) med 14 hjørner [14] . Af disse grafer er de første fire plane , og derfor er det kun fire kubiske polyedriske grafer (grafer af simple konvekse polyedre ), der er godt dækket. Fire af de syv grafer (begge prismer, Dürer-grafen og G (7,2) ) er generaliserede Petersen-grafer.
1- og 2-forbundne kubiske godt dækkede grafer dannes ved at erstatte hjørnerne af en graf eller cyklus med tre fragmenter, som Plummer kaldte A , B og C [9] . Fragmenter A eller B kan bruges til at erstatte hjørnerne af en cyklus eller interne hjørner af en sti, mens fragment C bruges til at erstatte de to sidste hjørner af en sti. Fragment A indeholder en bro , således at vi som et resultat af at erstatte nogle hjørner med fragment A (resten erstattes af B og C ), får en vertex 1-forbundet kubisk godt dækket graf. Alle vertex-1-forbundne kubiske godt dækkede grafer har denne form, og alle sådanne grafer er plane [15] .
Der er to typer vertex 2-forbundne kubiske godt dækkede grafer. Den ene af disse to familier dannes ved at erstatte cyklusspidserne med fragmenterne A og B , mens mindst to fragmenter skal være af type A. En graf af denne type er plan , hvis og kun hvis den ikke indeholder fragmenter af type B. En anden familie dannes ved at erstatte spidserne af stien med fragmenter af type B og C. Alle sådanne grafer er plane [15] .
I betragtning af god dækning af simple polyedre i 3D-rum, overvejer forskere veldækkede simplicial polyedre eller tilsvarende godt dækkede maksimale plane grafer. Enhver maksimal plan graf med fem eller flere toppunkter har en toppunktsforbindelse på 3, 4 eller 5 [16] . Der er ingen godt dækkede 5-forbundne maksimale plane grafer, og der er kun fire 4-forbundne godt dækkede maksimale plane grafer - grafer af et regulært oktaeder , en femkantet bipyramide , en snub biklinoid og en uregelmæssig polyhedron (ikke-konveks deltahedron ) med 12 hjørner, 30 kanter og 20 trekantede flader. Der er dog uendeligt mange 3-forbundne godt dækkede maksimale plane grafer [17] [18] [19] . For eksempel kan en godt dækket 3-forbundet maksimal plan graf opnås ved at konstruere et klikdæksel [6] ud fra en hvilken som helst maksimal plan graf med 3 t hjørner, der har t uforbundne trekantede flader, ved at tilføje t nye hjørner, en i hver af disse kanter.
At kontrollere, om en graf indeholder to maksimalt uafhængige sæt af forskellige størrelser, er NP-komplet . Det vil sige, at kontrollere om en graf er godt dækket er et coNP-komplet problem [20] . Selvom det er let at finde de største uafhængige sæt i en graf, der vides at være godt dækket, for alle grafer er problemet med at finde det største uafhængige sæt, såvel som at kontrollere, at en graf ikke er godt dækket, NP-svært [21] .
I modsætning hertil er det muligt at kontrollere, at en given graf G er meget godt dækket i polynomisk tid . For at gøre dette finder vi en undergraf H af G , der består af kanter, der opfylder to matchende egenskaber i en meget godt dækket graf , og bruger derefter den perfekte dækningsalgoritme til at kontrollere, om H har en perfekt overensstemmelse [10] . Nogle problemer, der er NP-komplette for vilkårlige grafer, såsom Hamilton-stiproblemet , kan løses i polynomisk tid for enhver veloverdækket graf [22] .
En graf siges at være ensartet matchende , hvis nogen maksimal matchning er størst. Det vil sige, at den matcher ensartet, hvis dens linjegraf er godt dækket. Man kan teste om en linjegraf, eller mere generelt en graf uden kløer , er godt dækket i polynomisk tid [23] .
Karakteriseringen af godt dækkede grafer med en omkreds på fem eller mere og godt dækkede grafer, der er 3-regulære, fører også til effektive polynomiegenkendelsesalgoritmer for sådanne grafer [24] .