V teorii grafů je dobře pokrytý graf (někdy nazývaný dobře skrytý graf ) neorientovaný graf , ve kterém mají všechny kryty vrcholů s minimálním začleněním stejnou velikost. Dobře pokryté grafy definoval a studoval Plummer [1] .
Vrcholový kryt grafu je soubor vrcholů grafu tak, že každá hrana má alespoň jeden konec v krytu. Kryt je minimální (neredukovatelný), pokud odstranění jakéhokoli vrcholu zničí kryt. Pokrytí se nazývá nejmenší, pokud neexistuje jiné pokrytí grafu s menším počtem vrcholů. Dobře pokrytý graf je takový, ve kterém je jakékoli minimální pokrytí také nejmenší. Plummer ve svém původním článku píše [1] , že definice dobře pokrytého grafu je „zjevně ekvivalentní“ vlastnosti, že jakékoli dva minimální kryty mají stejnou velikost.
Nezávislá množina grafu je množina vrcholů, ve kterých žádné dva vrcholy nesousedí. Je-li C vrcholovým krytem G , doplněk C musí být nezávislou množinou a naopak. C je minimální pokrytí vrcholů právě tehdy, když jeho doplněk I je maximální nezávislá množina, a C je nejmenší pokrytí vrcholů právě tehdy, když je jeho doplněk největší nezávislou množinou. Dobře pokrytý graf je tedy ekvivalentně grafem, ve kterém je každá maximální nezávislá množina největší.
V původním článku o dobře pokrytých grafech se tyto definice vztahovaly pouze na spojené grafy [1] , i když mají smysl i pro grafy nespojené. Někteří pozdější autoři nahradili požadavek na spojitost slabším požadavkem, že neexistují žádné izolované vrcholy [2] . Jak spojené dobře pokryté grafy, tak dobře pokryté grafy bez izolovaných vrcholů nemohou mít podstatné vrcholy , vrcholy, které patří ke každému nejmenšímu pokrytí vrcholů [1] . Každý dobře pokrytý graf je navíc kritickým grafem pro pokrytí vrcholů v tom smyslu, že odstraněním jakéhokoli vrcholu v z grafu vznikne graf s menším nejmenším pokrytím vrcholu [1] .
Komplex nezávislosti grafu G je simpliciální komplex , který má simplex pro každou nezávislou množinu v G . O simpliciálním komplexu se říká, že je jednoduchý, pokud všechny jeho maximální simplice mají stejnou mohutnost, takže dobře pokrytý graf je ekvivalentní grafu s jednoduchým komplexem nezávislosti [3] .
Cyklus grafů délky čtyři nebo pět je dobře pokryt – v obou případech má maximální nezávislá množina velikost dvě. Dobře pokrytý je také cyklus délky sedm a cesta délky tři. Jakýkoli úplný graf je dobře pokrytý – každá maximální nezávislá množina se skládá z jediného vrcholu. Kompletní bipartitní graf je dobře pokrytý, pokud mají obě jeho části stejný počet vrcholů – má pouze dvě maximální nezávislé množiny. Graf věže je dobře pokrytý - pokud umístíte na šachovnici libovolnou sadu věží tak, aby na sebe neútočily dvě věže, můžete vždy přidat další neútočící věž, dokud nebude věž na každém řádku a sloupci.
Jestliže P je mnohoúhelník nebo množina bodů, S je množina otevřených intervalů, které mají vrcholy P jako koncové body a uvnitř žádné body P , a G je průsečíkový graf S ( graf, který má vrcholy pro každý interval v S a hrany pro každou dvojici protínajících se intervalů), pak je G dobře pokryto. Pro tento případ jakákoliv maximální nezávislá množina v G odpovídá množině hran v polygonální triangulaci P a výpočet Eulerovy charakteristiky ukazuje, že jakékoli dvě triangularizace mají stejný počet hran [4] .
Jestliže G je libovolný graf s n vrcholy, kořenový součin G s jednohranným grafem (tj. graf H vytvořený přidáním n nových vrcholů ke G , každý se stupněm jedna a všechny spojené s různými vrcholy v G ) je dobře krytý. Maximální nezávislá množina v H se musí skládat z libovolné nezávislé množiny v G spolu se sousedy prvního stupně z další množiny. Tato množina má tedy velikost n [5] . Obecněji řečeno, daný graf G spolu s pokrytím klik (rozdělením vrcholů p G na kliky), je graf Gp vytvořený přidáním vrcholu pro každou kliku dobře pokryt. Kořenový součin je speciálním případem této konstrukce, kdy p se skládá z n klik obsahujících každý jeden vrchol [6] . Každý graf je tedy vygenerovaným podgrafem dobře pokrytého grafu.
Favaron definuje velmi dobře pokrytý graf jako dobře pokrytý graf (případně rozpojený, ale bez izolovaných vrcholů), ve kterém jakákoli maximální nezávislá množina (a tedy i jakékoli minimální pokrytí vrcholů) obsahuje přesně polovinu vrcholů [2] . Tato definice zahrnuje kořenové produkty grafu G a jednohranného grafu. Patří sem také například bipartitní dobře pokryté grafy, které studovali Ravindra a Berge [7] [8] — v bipartitním grafu bez izolovaných vrcholů tvoří obě strany libovolné části maximální nezávislé množiny (a minimální pokrytí vrcholů) , takže pokud je graf dobře pokrytý, musí mít obě strany stejný počet vrcholů. V dobře pokrytém grafu s n vrcholy velikost maximální nezávislé množiny nepřesahuje n /2 , takže velmi dobře pokryté grafy jsou dobře pokryté grafy, ve kterých má největší nezávislá množina maximální možnou velikost pro grafy [8 ] .
Bipartitní graf G je dobře pokrytý právě tehdy, když je dokonalá shoda M s vlastností, že pro libovolnou hranu uv od M tvoří vygenerovaný podgraf sousedů u a v úplný bipartitní graf [7] [9] . Charakterizaci pomocí párování lze rozšířit z bipartitních grafů na velmi dobře pokryté grafy - graf G je velmi dobře pokrytý tehdy a pouze tehdy, když má graf perfektní shodu M s následujícími dvěma vlastnostmi:
Pokud je však G velmi dobře pokryto, pak jakákoli dokonalá shoda v G tyto vlastnosti splňuje [10] .
Stromy jsou speciálním případem bipartitních grafů a testování, zda je strom dobře pokrytý, lze považovat za velmi jednoduchý případ charakterizace dobře pokrytých bipartitních grafů – pokud G je strom s více než dvěma vrcholy, je dobře- pokryto tehdy a jen tehdy, když každý strom bez okrajů listu sousedí právě s jedním listem [7] [9] . Stejná charakterizace platí pro grafy, které jsou lokálně stromové, v tom smyslu, že blízké okolí jakéhokoli vrcholu je acyklické – pokud má graf obvod osm nebo více (takže pro jakýkoli vrchol v podgraf vrcholů ve vzdálenosti tři od v je acyklické). pak je dobře pokryto právě tehdy, když jakýkoli vrchol se stupněm větším než dva má právě jednoho souseda se stupněm jedna [11] . Úzce příbuzná, ale složitější charakterizace platí pro dobře pokryté grafy obvodu pět a více [12] [13] .
Kubické ( 3-regulární ) dobře pokryté grafy jsou klasifikovány - rodina se skládá ze sedmi 3-souvislých zástupců a navíc zahrnuje tři nekonečné rodiny méně spojených kubických grafů.
Těchto sedm 3-spojených dobře pokrytých kubických grafů zahrnuje úplný graf K 4 , grafy trojúhelníkového a pětiúhelníkového hranolu , Durerův graf , graf užitkovosti K 3,3 , transformaci Y-Δ s osmi vrcholy z grafu užitkovosti a zobecněný Petersenův graf G (7,2) se 14 vrcholy [14] . Z těchto grafů jsou první čtyři rovinné , a proto jsou pouze čtyři kubické polyedrické grafy (grafy jednoduchých konvexních mnohostěnů ), které jsou dobře pokryty. Čtyři ze sedmi grafů (oba hranoly, Dürerův graf a G (7,2) ) jsou zobecněné Petersenovy grafy.
1- a 2-spojené kubické dobře pokryté grafy vznikají nahrazením vrcholů grafu nebo cyklu třemi fragmenty, které Plummer nazval A , B a C [9] . Fragmenty A nebo B lze použít k nahrazení vrcholů cyklu nebo vnitřních vrcholů cesty, zatímco fragment C se používá k nahrazení dvou konečných vrcholů cesty. Fragment A obsahuje můstek , takže v důsledku nahrazení některých vrcholů fragmentem A (zbytek jsou nahrazeny B a C ), dostaneme vertex 1-connected cubic well-covered graf. Všechny kubické dobře pokryté grafy spojené vrcholem-1 mají tento tvar a všechny takové grafy jsou rovinné [15] .
Existují dva typy vrcholových 2-spojených kubických dobře pokrytých grafů. Jedna z těchto dvou rodin vzniká nahrazením vrcholů cyklu fragmenty A a B , přičemž alespoň dva fragmenty musí být typu A. Graf tohoto typu je rovinný právě tehdy, když neobsahuje fragmenty typu B. Další rodina vzniká nahrazením vrcholů cesty fragmenty typu B a C . Všechny takové grafy jsou rovinné [15] .
Vzhledem k dobrému pokrytí jednoduchých mnohostěnů ve 3D prostoru vědci zvažují dobře pokryté jednoduché mnohostěny nebo ekvivalentně dobře pokryté maximální rovinné grafy. Jakýkoli maximální rovinný graf s pěti nebo více vrcholy má vrcholovou konektivitu 3, 4 nebo 5 [16] . Neexistují žádné dobře pokryté 5-spojené maximální rovinné grafy a existují pouze čtyři 4-spojené dobře pokryté maximální rovinné grafy - grafy pravidelného osmistěnu , pětiúhelníkové bipyramidy , snub biklinoidu a nepravidelného mnohostěnu (nekonvexní deltahedron ) s 12 vrcholy, 30 hranami a 20 trojúhelníkovými plochami. Existuje však nekonečně mnoho 3-spojených dobře pokrytých maximálních rovinných grafů [17] [18] [19] . Například dobře pokrytý 3-souvislý maximální rovinný graf lze získat vytvořením klikového krytu [6] z libovolného maximálního rovinného grafu se 3 t vrcholy, který má t nespojených trojúhelníkových ploch, přidáním t nových vrcholů, jeden v každém z nich. tyto hrany.
Kontrola, zda graf obsahuje dvě maximální nezávislé množiny různých velikostí, je NP-úplná . To znamená, že kontrola, zda je graf dobře pokryt, je coNP-úplný problém [20] . Ačkoli je snadné najít největší nezávislé množiny v grafu, o kterém je známo, že je dobře pokryt, u všech grafů je problém najít největší nezávislou množinu, stejně jako zkontrolovat, zda graf není dobře pokryt, NP-těžký [21] .
Naproti tomu je možné zkontrolovat, že daný graf G je velmi dobře pokryt v polynomiálním čase . Abychom to udělali, najdeme podgraf H grafu G , sestávající z hran, které splňují dvě shodné vlastnosti ve velmi dobře pokrytém grafu , a pak pomocí algoritmu dokonalého pokrytí zkontrolujeme, zda H má perfektní shodu [10] . Některé problémy, které jsou NP-úplné pro libovolné grafy, jako je problém Hamiltonovské cesty , lze vyřešit v polynomiálním čase pro jakýkoli dobře pokrytý graf [22] .
O grafu se říká, že se rovnoměrně shoduje , pokud je maximální shoda největší. To znamená, že je jednotná, pokud je její spojnicový graf dobře pokryt. Lze otestovat, zda je spojnicový graf, nebo obecněji graf bez drápů , dobře pokryt v polynomiálním čase [23] .
Charakterizace dobře pokrytých grafů s obvodem pět a více a dobře pokrytých grafů, které jsou 3-pravidelné, také vede k účinným polynomiálním rozpoznávacím algoritmům pro takové grafy [24] .