În teoria grafurilor, un graf bine acoperit (uneori numit graf bine ascuns ) este un graf nedirecționat în care toate acoperirile de vârf de incluziune minime au aceeași dimensiune. Graficele bine acoperite au fost definite și studiate de Plummer [1] .
O acoperire de vârf a unui graf este un set de vârfuri de graf astfel încât fiecare muchie să aibă cel puțin un capăt în capac. O acoperire este minimă (ireductibilă) dacă îndepărtarea oricărui vârf distruge capacul. O acoperire se numește cea mai mică dacă nu există o altă acoperire a graficului cu un număr mai mic de vârfuri. Un grafic bine acoperit este unul în care orice acoperire minimă este și cea mai mică. În lucrarea sa originală, Plummer scrie [1] că definiția unui grafic bine acoperit este „evident echivalentă” cu proprietatea că orice două coperți minime au aceeași dimensiune.
O mulțime independentă a unui grafic este o mulțime de vârfuri în care nu există două vârfuri adiacente. Dacă C este o acoperire de vârf a lui G , complementul lui C trebuie să fie o mulțime independentă și invers. C este acoperirea minimă a vârfurilor dacă și numai dacă complementul său I este mulțimea independentă maximă, iar C este cea mai mică acoperire a vârfurilor dacă și numai dacă complementul său este cea mai mare mulțime independentă. Astfel, un grafic bine acoperit este, în mod echivalent, un grafic în care fiecare mulțime independentă maximă este cea mai mare.
În articolul original despre grafurile bine acoperite, aceste definiții se aplicau numai grafurilor conectate [1] , deși au sens și pentru grafurile deconectate. Unii autori de mai târziu au înlocuit cerința de conectare cu cerința mai slabă că nu există vârfuri izolate [2] . Atât grafurile bine acoperite conectate, cât și grafurile bine acoperite fără vârfuri izolate nu pot avea vârfuri esențiale , vârfuri care aparțin oricărei cele mai mici acoperiri de vârfuri [1] . Mai mult, orice graf bine acoperit este un graf critic pentru acoperirile de vârfuri, în sensul că prin eliminarea oricărui vârf v din graf rezultă un grafic cu o acoperire de vârf mai mică [1] .
Complexul de independență al unui graf G este un complex simplist care are un simplex pentru fiecare mulțime independentă din G. Un complex simplicial se spune că este simplu dacă toate simplexele sale maxime au aceeași cardinalitate, astfel încât un graf bine acoperit este echivalent cu un graf cu un complex simplu de independență [3] .
Un ciclu de grafic cu lungimea patru sau cinci este bine acoperit - în ambele cazuri, setul independent maxim are dimensiunea doi. Un ciclu de lungimea șapte și o potecă de lungimea trei sunt, de asemenea, bine acoperite. Orice grafic complet este bine acoperit - orice mulțime independentă maximă constă dintr-un singur vârf. Un graf bipartit complet este bine acoperit dacă ambele părți au același număr de vârfuri - are doar două mulțimi independente maxime. Graficul turnului este bine acoperit - dacă plasați orice set de turnuri pe tabla de șah, astfel încât să nu se atace două turnuri, puteți adăuga oricând un alt turn care nu atacă până când există câte un turn pe fiecare rând și coloană.
Dacă P este un poligon sau o mulțime de puncte, S este mulțimea de intervale deschise având vârfuri ale lui P ca puncte terminale și fără puncte ale lui P în interior, iar G este graficul de intersecție al lui S ( un grafic care are vârfuri pentru fiecare interval din S și muchii pentru fiecare pereche de intervale care se intersectează), atunci G este bine acoperit. Pentru acest caz, orice mulțime independentă maximă din G corespunde unui set de muchii într-o triangulație poligonală P , iar calculul caracteristicii lui Euler arată că oricare două triunghiulări au același număr de muchii [4] .
Dacă G este orice grafic cu n vârfuri, produsul rădăcină al lui G cu un grafic cu o singură muchie (adică graficul H format prin adăugarea a n vârfuri noi la G , fiecare cu gradul unu și toate conectate la vârfuri diferite, în G ) este bine acoperit. Mulțimea independentă maximă din H trebuie să constea dintr-o mulțime independentă arbitrară din G , împreună cu vecinii de gradul unu, dintr-o mulțime suplimentară. Astfel, această mulțime are dimensiunea n [5] . Mai general, având în vedere orice grafic G împreună cu acoperirea clicei (împărțirea p vârfuri ale lui G în clicuri), graficul G p format prin adăugarea unui vârf pentru fiecare clică este bine acoperit. Produsul rădăcină este un caz special al acestei construcții, când p este format din n clicuri care conțin câte un vârf [6] . Astfel, orice grafic este un subgraf generat al unui grafic bine acoperit.
Favaron definește un graf foarte bine acoperit ca un graf bine acoperit (eventual deconectat, dar fără vârfuri izolate) în care orice mulțime maxim independentă (și deci și orice acoperire minimă de vârf) conține exact jumătate din vârfuri [2] . Această definiție include produsele rădăcină a unui grafic G și a unui grafic cu o singură muchie. Aceasta include, de asemenea, de exemplu, grafuri bipartite bine acoperite, care au fost studiate de Ravindra și Berge [7] [8] - într-un graf bipartit fără vârfuri izolate, ambele părți ale oricărei părți formează mulțimi independente maxime (și acoperiri minime de vârfuri) , deci dacă graficul este bine acoperit, ambele părți trebuie să aibă același număr de vârfuri. Într-un grafic bine acoperit cu n vârfuri, dimensiunea mulțimii independente maxime nu depășește n /2 , deci graficele foarte bine acoperite sunt grafice bine acoperite în care cea mai mare mulțime independentă are dimensiunea maximă posibilă pentru grafice [8] ] .
Un graf bipartit G este bine acoperit dacă și numai dacă este o potrivire perfectă a lui M cu proprietatea că pentru orice muchie uv din M subgraful generat al vecinilor u și v formează un graf bipartit complet [7] [9] . Caracterizarea în termeni de potriviri poate fi extinsă de la grafice bipartite la grafice foarte bine acoperite - un grafic G este foarte bine acoperit dacă și numai dacă graficul are o potrivire perfectă M cu următoarele două proprietăți:
Totuși, dacă G este foarte bine acoperit, atunci orice potrivire perfectă în G satisface aceste proprietăți [10] .
Arborii sunt un caz special de grafuri bipartite, iar testarea dacă un arbore este bine acoperit poate fi considerată ca un caz foarte simplu de caracterizare a grafurilor bipartite bine acoperite - dacă G este un arbore cu mai mult de două vârfuri, este bine- acoperit dacă și numai dacă fiecare arbore fără marginea frunzei este adiacent cu exact o frunză [7] [9] . Aceeași caracterizare se aplică graficelor care sunt la nivel local asemănătoare unui arbore, în sensul că vecinătatea apropiată a oricărui vârf este aciclică - dacă graficul are o circumferință de opt sau mai mult (deci pentru orice vârf v , subgraful vârfurilor la distanța trei de la v este aciclic).atunci este bine acoperit dacă și numai dacă orice vârf cu grad mai mare de doi are exact un vecin cu gradul unu [11] . O caracterizare strâns legată, dar mai complexă, se aplică graficelor bine acoperite cu circumferința cinci sau mai mult [12] [13] .
Graficele cubice ( 3 regulate ) bine acoperite sunt clasificate - familia este formată din șapte reprezentanți cu trei conexiuni și, în plus, include trei familii infinite de grafice cubice mai puțin conectate.
Aceste șapte grafice cubice bine acoperite cu 3 conexiuni includ graficul complet K 4 , graficele prisme triunghiulare și pentagonale , graficul Durer , graficul utilitar K 3,3 , transformarea Y-Δ cu opt vârfuri din graficul utilitarului și graficul Petersen generalizat G (7,2) cu 14 vârfuri [14] . Dintre aceste grafice, primele patru sunt plane și, prin urmare, numai ele sunt și patru grafice poliedrice cubice (grafice ale poliedrelor simple convexe ) care sunt bine acoperite. Patru dintre cele șapte grafice (ambele prisme, graficul Dürer și G (7,2) ) sunt grafice Petersen generalizate.
Graficele cubice bine acoperite 1- și 2-conectate sunt formate prin înlocuirea vârfurilor unui graf sau ciclu cu trei fragmente, pe care Plummer le-a numit A , B și C [9] . Fragmentele A sau B pot fi folosite pentru a înlocui vârfurile unui ciclu sau vârfurile interne ale unei căi, în timp ce fragmentul C este folosit pentru a înlocui cele două vârfuri finale ale unei căi. Fragmentul A conține o punte , astfel încât, ca urmare a înlocuirii unor vârfuri cu fragment A (restul sunt înlocuite cu B și C ), obținem un graf cubic bine acoperit de vârf 1-conectat. Toate graficele cubice bine acoperite conectate la vârful 1 au această formă și toate aceste grafice sunt plane [15] .
Există două tipuri de grafice cubice bine acoperite conectate cu 2 vârfuri. Una dintre aceste două familii se formează prin înlocuirea vârfurilor ciclului cu fragmente A și B , în timp ce cel puțin două fragmente trebuie să fie de tip A . Un grafic de acest tip este plan dacă și numai dacă nu conține fragmente de tip B . O altă familie se formează prin înlocuirea vârfurilor căii cu fragmente de tip B și C . Toate astfel de grafice sunt plane [15] .
Având în vedere o bună acoperire a poliedrelor simple în spațiul 3D, cercetătorii consideră poliedre simple bine acoperite sau , echivalent, grafice plane maxime bine acoperite. Orice graf planar maxim cu cinci sau mai multe vârfuri are o conexiune a vârfurilor de 3, 4 sau 5 [16] . Nu există grafice plane maxime cu 5 conexiuni bine acoperite și există doar patru grafice plane maxime bine acoperite cu 4 conexiuni - grafice ale unui octaedru regulat , o bipiramidă pentagonală , un biclinoid snub și un poliedru neregulat (neconvex). deltaedru ) cu 12 vârfuri, 30 de muchii și 20 de fețe triunghiulare. Cu toate acestea, există infinit de multe grafuri planare maxime bine acoperite cu 3 conexiuni [17] [18] [19] . De exemplu, un graf planar maxim cu 3 conexiuni bine acoperit poate fi obținut prin construirea unui înveliș de clică [6] din orice graf planar maxim cu 3 t vârfuri care are t fețe triunghiulare neconectate, prin adăugarea a t noi vârfuri, câte unul în fiecare dintre aceste margini.
Verificarea dacă un grafic conține două seturi maxime independente de dimensiuni diferite este NP-complet . Adică, verificarea dacă un grafic este bine acoperit este o problemă conNP-completă [20] . Deși este ușor să găsiți cele mai mari mulțimi independente într-un grafic cunoscut a fi bine acoperit, pentru toate graficele problema găsirii celei mai mari mulțimi independente, precum și verificarea faptului că un grafic nu este bine acoperit, este NP-hard [21] .
În schimb, este posibil să se verifice că un anumit grafic G este foarte bine acoperit în timp polinomial . Pentru a face acest lucru, găsim un subgraf H al lui G , constând din muchii care satisfac două proprietăți de potrivire într-un graf foarte bine acoperit și apoi folosim algoritmul de acoperire perfectă pentru a verifica dacă H are o potrivire perfectă [10] . Unele probleme care sunt NP-complete pentru grafuri arbitrare, cum ar fi problema drumului hamiltonian , pot fi rezolvate în timp polinomial pentru orice graf bine acoperit [22] .
Se spune că un grafic se potrivește uniform dacă orice potrivire maximă este cea mai mare. Adică, se potrivește uniform dacă graficul său de linii este bine acoperit. Se poate testa dacă un grafic de linii, sau mai general un grafic fără gheare , este bine acoperit în timp polinomial [23] .
Caracterizarea graficelor bine acoperite cu circumferința cinci sau mai mult și a graficelor bine acoperite care sunt 3-regulate conduce, de asemenea, la algoritmi eficienți de recunoaștere a polinomiilor pentru astfel de grafice [24] .