Graafiteoriassa hyvin peitetty graafi ( kutsutaan joskus hyvin piilotetuksi graafiksi ) on suuntaamaton graafi , jossa kaikki inkluusio-minimaaliset kärjen peitteet ovat samankokoisia. Hyvin peitetyt kuvaajat määritteli ja tutki Plummer [1] .
Graafin kärjen kansi on joukko graafin kärkipisteitä siten, että jokaisella reunalla on vähintään yksi pää kannessa. Kansi on minimaalinen (pelistämätön), jos minkä tahansa kärjen poistaminen tuhoaa kannen. Kanta kutsutaan pienimmäksi, jos graafilla ei ole muuta peitettä, jolla on pienempi määrä pisteitä. Hyvin peitetty graafi on sellainen, jossa pienin peitto on myös pienin. Alkuperäisessä artikkelissaan Plummer kirjoittaa [1] , että hyvin peitetyn graafin määritelmä on "ilmiselvästi vastaava" sen ominaisuuden kanssa, että millä tahansa kahdella minimikannessa on sama koko.
Graafin riippumaton joukko on joukko pisteitä, joissa ei ole kahta pistettä vierekkäin. Jos C on G : n kärkipeite, C :n komplementin on oltava riippumaton joukko ja päinvastoin. C on minimipisteen peitto silloin ja vain, jos sen komplementti I on suurin riippumaton joukko, ja C on pienin kärjen peite, jos ja vain jos sen komplementti on suurin itsenäinen joukko. Näin ollen hyvin peitetty graafi on vastaavasti graafi, jossa jokainen suurin riippumaton joukko on suurin.
Alkuperäisessä artikkelissa hyvin peitetystä graafista nämä määritelmät soveltuvat vain yhdistettyihin graafisiin [1] , vaikka ne ovat järkeviä myös irrotetuille kaavioille. Jotkut myöhemmät kirjoittajat ovat korvanneet liitettävyysvaatimuksen heikommalla vaatimuksella, jonka mukaan ei ole eristettyjä huippuja [2] . Sekä liitetyillä hyvin peitetyillä graafeilla että hyvin peitetyillä graafeilla, joissa ei ole eristettyjä pisteitä, ei voi olla olennaisia pisteitä , pisteitä, jotka kuuluvat jokaiseen pienimpään kärkipeitteeseen [1] . Lisäksi mikä tahansa hyvin peitetty graafi on kriittinen graafi huippupisteiden kattauksille siinä mielessä, että minkä tahansa pisteen v poistaminen graafista tuottaa graafin, jolla on pienempi pienin pistepeite [1] .
Graafin G riippumattomuuskompleksi on yksinkertainen kompleksi , jolla on simpleksi jokaiselle G :n riippumattomalle joukolle . Yksinkertaisen kompleksin sanotaan olevan yksinkertainen, jos kaikilla sen maksimaalisilla yksinkertaisilla on sama kardinaliteetti, joten hyvin peitetty graafi vastaa graafia, jolla on yksinkertainen riippumattomuuskompleksi [3] .
Kuvaajajakso , jonka pituus on neljä tai viisi, on hyvin katettu – molemmissa tapauksissa suurimman riippumattoman joukon koko on kaksi. Kierros, jonka pituus on seitsemän ja polku, jonka pituus on kolme, ovat myös hyvin katettuja. Mikä tahansa täydellinen graafi on hyvin peitetty - mikä tahansa suurin riippumaton joukko koostuu yhdestä kärjestä. Täydellinen kaksiosainen graafi on hyvin peitetty, jos sen molemmilla osilla on sama määrä pisteitä - sillä on vain kaksi maksimaalista riippumatonta joukkoa. Tornikaavio on hyvin peitetty - jos asetat shakkilaudalle minkä tahansa tornin joukon niin , että kaksi tornia ei hyökkää toisiaan vastaan, voit aina lisätä toisen ei-hyökkäävän tornin, kunnes jokaisella rivillä ja sarakkeella on torni.
Jos P on monikulmio tai pistejoukko, S on joukko avoimia välejä, joiden P :n kärjet ovat päätepisteitä ja joiden sisällä ei ole P :n pisteitä , ja G on S :n leikkauskäyrä ( kuvaaja, jolla on pisteet jokaiselle S :n intervallille ja reunat jokaiselle leikkausväliparille), silloin G on hyvin peitetty. Tässä tapauksessa mikä tahansa suurin riippumaton joukko G :ssä vastaa reunojen joukkoa monikulmiokolmiossa P , ja Eulerin ominaiskäyrän laskeminen osoittaa, että millä tahansa kahdella kolmiomittauksella on sama määrä reunoja [4] .
Jos G on mikä tahansa graafi, jossa on n kärkeä , G : n juuritulo yksireunaisen graafin kanssa (eli graafi H , joka muodostuu lisäämällä n uutta pistettä G :hen , joista jokaisella on aste yksi ja kaikki kytketty eri pisteisiin G :ssä ) on hyvin peitetty. H :n suurimman riippumattoman joukon tulee koostua mielivaltaisesta riippumattomasta joukosta G :ssä yhdessä ykkösasteen naapureiden kanssa lisäjoukosta. Tämän sarjan koko on siis n [5] . Yleisemmin ottaen mikä tahansa graafi G yhdessä klikkin peiton kanssa (jakaa G :n p pisteet klikkeiksi), graafi Gp, joka muodostetaan lisäämällä kullekin klikkille huippupiste, on hyvin peitetty . Juuritulo on tämän konstruktion erikoistapaus, kun p koostuu n : stä klikistä, joissa kussakin on yksi kärki [6] . Siten mikä tahansa graafi on hyvin peitetyn graafin generoitu osagraafi .
Favaron määrittelee erittäin hyvin peitetyn graafin hyvin peitetyksi graafiksi (mahdollisesti irrotettuna, mutta ilman eristettyjä pisteitä), jossa mikä tahansa suurin riippumaton joukko (ja siten myös mikä tahansa huippupisteiden minimipeite) sisältää tasan puolet pisteistä [2] . Tämä määritelmä sisältää graafin G ja yksireunaisen graafin juuritulot. Tämä sisältää myös esimerkiksi kaksiosaiset hyvin peitetyt graafit, joita Ravindra ja Berge tutkivat [7] [8] — kaksiosaisessa graafissa, jossa ei ole eristettyjä huippuja, minkä tahansa osan molemmat puolet muodostavat maksimaalisia riippumattomia joukkoja (ja minimaalisia huippupisteiden peitteitä) , joten jos graafi on hyvin peitetty , molemmilla puolilla on oltava sama määrä pisteitä. Hyvin peittetyssä graafissa, jossa on n kärkeä, suurimman riippumattoman joukon koko ei ylitä n /2 , joten erittäin hyvin peitetyt graafit ovat hyvin peitettyjä graafeja, joissa suurimmalla riippumattomalla joukolla on suurin mahdollinen graafien koko [8 ] .
Kaksiosainen graafi G on hyvin peitetty silloin ja vain, jos se sopii täydellisesti M :lle sen ominaisuuden kanssa, että mille tahansa M:n reunalle uv generoitu naapureiden u ja v aligraafi muodostaa täydellisen kaksiosaisen graafin [7] [9] . Yhteensopivuuden karakterisointi voidaan laajentaa kaksiosaisista graafisista erittäin hyvin peitettyihin graafisiin - graafi G on erittäin hyvin katettu, jos ja vain jos graafilla on täydellinen yhteensopivuus M seuraavilla kahdella ominaisuudella:
Jos G on kuitenkin hyvin peitetty, niin mikä tahansa täydellinen yhteensopivuus G :ssä täyttää nämä ominaisuudet [10] .
Puut ovat kaksiosaisten graafien erikoistapaus, ja sen testaamista, onko puu hyvin peitetty, voidaan ajatella hyvin yksinkertaisena tapauksena hyvin peitettyjen kaksiosaisten graafien karakterisoinnissa - jos G on puu, jolla on enemmän kuin kaksi kärkeä, se on hyvin katetaan silloin ja vain, jos jokainen ei-lehtireunapuu on täsmälleen yhden lehden vieressä [7] [9] . Sama luonnehdinta pätee graafisiin, jotka ovat paikallisesti puumaisia siinä mielessä, että minkä tahansa kärjen lähiympäristö on asyklinen – jos graafin ympärysmitta on vähintään kahdeksan (siis minkä tahansa kärjen v , kolmen etäisyyden päässä olevien kärkien alikaavio v on asyklinen). silloin se on hyvin peitetty silloin ja vain, jos jollakin kärjellä, jonka aste on suurempi kuin kaksi, on täsmälleen yksi naapuri, jolla on aste yksi [11] . Läheisesti liittyvä, mutta monimutkaisempi karakterisointi pätee hyvin peitettyihin kaavioihin, joiden ympärysmitta on viisi tai enemmän [12] [13] .
Kuutioiset ( 3 -säännölliset ) hyvin peitetyt graafit luokitellaan - perhe koostuu seitsemästä 3-liitetystä edustajasta ja lisäksi se sisältää kolme ääretöntä perhettä vähemmän kytkettyjä kuutiograafisia.
Nämä seitsemän 3-liitettä hyvin peitettyä kuutiograafia sisältävät täydellisen graafin K 4 , kolmion ja viisikulmaisen prismakuvaajan , Durerin graafin , hyödyllisyysgraafin K 3,3 , kahdeksan kärjen Y-Δ muunnoksen hyödyllisyysgraafista ja yleistetty Petersen-graafi G (7,2) , jossa on 14 kärkeä [14] . Näistä kaavioista ensimmäiset neljä ovat tasomaisia , ja siksi vain ne ovat myös neljä kuutiota monitahoista kuvaajaa ( yksinkertaisten kuperoiden monitahojen kuvaajia ), jotka on hyvin peitetty. Neljä seitsemästä graafista (molemmat prismat, Dürer-graafi ja G (7,2) ) ovat yleistettyjä Petersen-graafia.
1- ja 2-liitetyt kuutioiset hyvin peitetyt graafit muodostetaan korvaamalla graafin tai syklin kärjet kolmella fragmentilla, joita Plummer kutsui A , B ja C [9] . Fragmentteja A tai B voidaan käyttää korvaamaan syklin kärkipisteitä tai polun sisäisiä pisteitä, kun taas fragmentilla C korvataan polun kaksi viimeistä kärkeä. Fragmentti A sisältää sillan , joten kun osa kärkeistä korvataan fragmentilla A (loput korvataan B :llä ja C :llä ), saadaan kärki 1:een kytketty kuutio hyvin peitetty graafi. Kaikilla vertex-1-liitetyillä kuutiopohjaisilla hyvin peitetyillä graafeilla on tämä muoto, ja kaikki tällaiset graafit ovat tasomaisia [15] .
On olemassa kahta tyyppiä vertex 2 -liitettyjä kuutioisia hyvin peitettyjä kaavioita. Toinen näistä kahdesta perheestä muodostetaan korvaamalla syklipisteet fragmenteilla A ja B , kun taas vähintään kahden fragmentin on oltava tyyppiä A . Tämän tyyppinen graafi on tasomainen silloin ja vain, jos se ei sisällä B -tyypin fragmentteja . Toinen perhe muodostetaan korvaamalla polun kärjet tyypin B ja C fragmenteilla . Kaikki tällaiset kuvaajat ovat tasomaisia [15] .
Ottaen huomioon yksinkertaisten polyhedrien hyvän peiton 3D-avaruudessa, tutkijat harkitsevat hyvin peitettyjä yksinkertaisia polyhedraja tai vastaavasti hyvin peitettyjä maksimaalisia tasokaavioita. Minkä tahansa maksimaalisen tasograafin, jossa on viisi tai useampia kärkeä, kärkiliitettävyys on 3, 4 tai 5 [16] . Ei ole olemassa hyvin peitettyjä 5-liitettyjä maksimitasokaavioita, ja on vain neljä 4-liitettyä hyvin peitettyä maksimaalista tasograafia - säännöllisen oktaedrin , viisikulmaisen bipyramidin , snub -biclinoidin ja epäsäännöllisen monitahoisen (ei-kuperan ) kuvaajia. deltahedron ), jossa on 12 kärkeä, 30 reunaa ja 20 kolmiopintaa. On kuitenkin olemassa äärettömän monta 3-liitännäistä hyvin peitettyä maksimaalista tasograafia [17] [18] [19] . Esimerkiksi hyvin peitetty 3-liitännäinen maksimitasograafi voidaan saada rakentamalla klikkipeite [6] mistä tahansa maksimaalisesta tasograafista, jossa on 3 t kärkeä ja jossa on t yhdistämätöntä kolmion pintaa, lisäämällä t uutta pistettä, yksi jokaiseen nämä reunat.
Sen tarkistaminen, sisältääkö kaavio kaksi maksimaalista erikokoista riippumatonta joukkoa, on NP-täydellinen . Toisin sanoen sen tarkistaminen, onko graafi hyvin peitetty, on coNP-täydellinen tehtävä [20] . Vaikka graafista on helppo löytää suurimmat riippumattomat joukot, joiden tiedetään olevan hyvin katettu, kaikkien graafien ongelma suurimman riippumattoman joukon löytämisessä sekä sen tarkistamisessa, ettei graafia ole hyvin katettu, on NP-kova [21] . .
Sitä vastoin on mahdollista tarkistaa, että tietty graafi G on hyvin katettu polynomiajassa . Tätä varten löydämme G:n aligraafin H , joka koostuu reunoista, jotka täyttävät kaksi yhteensopivaa ominaisuutta erittäin hyvin peitetyssä graafissa , ja käytämme sitten täydellisen peittoalgoritmia tarkistaaksemme, onko H :lla täydellinen yhteensopivuus [10] . Jotkut ongelmat, jotka ovat NP-täydellisiä mielivaltaisille graafille, kuten Hamiltonin polun ongelma , voidaan ratkaista polynomiajassa mille tahansa hyvin peitetylle graafille [22] .
Kuvaajan sanotaan olevan tasaisesti täsmäävä , jos mikä tahansa maksimaalinen vastaavuus on suurin. Toisin sanoen se vastaa tasaisesti, jos sen viivakaavio on hyvin peitetty. Voidaan testata, peittyykö viivakaavio tai yleisemmin kynsitön graafi hyvin polynomiajassa [23] .
Hyvin peitettyjen graafien karakterisointi, jonka ympärysmitta on viisi tai enemmän, ja hyvin peitetyt graafit, jotka ovat 3-säännöllisiä, johtaa myös tehokkaisiin polynomien tunnistusalgoritmeihin tällaisille kaavioille [24] .