Triviálně dokonalý graf - Trivially perfect graph
v teorie grafů, a triviálně dokonalý graf je graf s vlastností, že v každém z jeho indukované podgrafy velikost maximální nezávislá sada se rovná počtu maximální kliky.[1] Triviálně dokonalé grafy nejprve studoval (Wolk1962, 1965 ), ale byli pojmenováni Golumbic (1978); Golumbic píše, že „název byl zvolen, protože je triviální ukázat, že takový graf je perfektní "Triviálně dokonalé grafy jsou také známé jako srovnatelné grafy stromů,[2] arborescentní srovnatelné grafy,[3] a kvaziprahové grafy.[4]
Ekvivalentní charakterizace
Triviálně dokonalé grafy mají několik dalších ekvivalentních charakterizací:
- Jsou to srovnatelné grafy z řádově-teoretické stromy. To je, pojďme T být částečná objednávka takové, že pro každého t ∈ T, sada {s ∈ T : s < t} je dobře objednané vztahem T má minimální prvek r. Pak srovnávací graf z T je triviálně dokonalý a každý triviálně dokonalý graf lze vytvořit tímto způsobem.[5]
- Jsou to grafy, které nemají a P4 graf cesty nebo a C4 graf cyklu tak jako indukované podgrafy.[6]
- Jsou to grafy, ke kterým se každý připojil indukovaný podgraf obsahuje a univerzální vrchol.[7]
- Jsou to grafy, které lze reprezentovat jako intervalové grafy pro sadu vnořených intervaly. Sada intervalů je vnořena, pokud jsou pro každé dva intervaly v sadě dva disjunktní nebo jeden obsahuje druhý.[8]
- Jsou to grafy, které jsou oba akordický a cographs.[9] To vyplývá z charakterizace chordálních grafů jako grafů bez indukovaných cyklů délky větších než tři a grafů jako grafů bez indukované cesty na čtyřech vrcholech (P4).
- Jsou to grafy, které jsou jak grafy, tak intervalovými grafy.[9]
- Jsou to grafy, které lze vytvořit, počínaje grafy s jedním vrcholem, dvěma operacemi: disjunktní spojení dvou menších triviálně dokonalých grafů a přidání nového vrcholu sousedícího se všemi vrcholy menšího triviálně dokonalého grafu.[10] Tyto operace odpovídají v podkladovém lese vytvoření nového lesa disjunktním spojením dvou menších lesů a vytvoření stromu připojením nového kořenového uzlu ke kořenům všech stromů v lese.
- Jsou to grafy, ve kterých pro každou hranu uv, sousedství z u a proti (počítaje v to u a proti samy) jsou vnořeny: jedno sousedství musí být podmnožinou druhého.[11]
- Jsou to permutační grafy definováno od stohovatelné permutace.[12]
- Jsou to grafy s vlastností, že v každém z jeho indukovaných podgrafů číslo krytu se rovná počtu maximální kliky.[13]
- Jsou to grafy s vlastností, že v každém z jeho indukovaných podgrafů číslo kliky rovná se pseudogrundové číslo.[13]
- Jsou to grafy s vlastností, že v každém z jeho indukovaných podgrafů chromatické číslo rovná se pseudogrundové číslo.[13]
Související třídy grafů
Z ekvivalentních charakterizací triviálně dokonalých grafů vyplývá, že každý triviálně dokonalý graf je také a cograph, a chordální graf, a Ptolemaiovský graf, an intervalový graf a perfektní graf.
The prahové grafy jsou přesně grafy, které jsou samy o sobě triviálně dokonalé, a doplňky triviálně dokonalých grafů (cotriviálně dokonalé grafy).[14]
Větrný mlýn grafy jsou triviálně dokonalí.
Uznání
Chu (2008) popisuje jednoduchý lineární čas algoritmus pro rozpoznávání triviálně dokonalých grafů, založený na lexikografické vyhledávání na šířku. Kdykoli algoritmus LexBFS odstraní vrchol proti od první sady ve frontě algoritmus zkontroluje, že všichni zbývající sousedé proti patří do stejné sady; pokud ne, lze zkonstruovat jeden ze zakázaných indukovaných podgrafů proti. Pokud bude tato kontrola úspěšná pro všechny proti, potom je graf triviálně dokonalý. Algoritmus lze také upravit, aby se otestovalo, zda je graf doplňkový graf triviálně dokonalého grafu v lineárním čase.
Určení, zda obecný graf je k vymazání okrajů od triviálně dokonalého grafu je NP úplné,[15] fixovatelný parametr[16] a lze vyřešit v O (2.45k(m + n)) čas.[17]
Poznámky
- ^ Brandstädt, Le & Spinrad (1999), definice 2.6.2, str. 34; Golumbic (1978).
- ^ Wolk (1962); Wolk (1965).
- ^ Donnelly & Isaak (1999).
- ^ Yan, Chen & Chang (1996).
- ^ Brandstädt, Le & Spinrad (1999), věta 6.6.1, s. 99; Golumbic (1978), důsledek 4.
- ^ Brandstädt, Le & Spinrad (1999), věta 6.6.1, s. 99; Golumbic (1978) věta 2. Wolk (1962) a Wolk (1965) to prokázalo pro srovnatelné grafy zakořeněných lesů.
- ^ Wolk (1962).
- ^ Brandstädt, Le & Spinrad (1999), str. 51.
- ^ A b Brandstädt, Le & Spinrad (1999), str. 248; Yan, Chen & Chang (1996) věta 3.
- ^ Yan, Chen & Chang (1996); Gurski (2006).
- ^ Yan, Chen & Chang (1996) věta 3.
- ^ Rotem (1981).
- ^ A b C Rubio-Montiel (2015).
- ^ Brandstädt, Le & Spinrad (1999), věta 6.6.3, s. 100; Golumbic (1978), důsledek 5.
- ^ Sharan (2002).
- ^ Cai (1996).
- ^ Nastos & Gao (2010).
Reference
- Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Třídy grafů: PrůzkumMonografie SIAM o diskrétní matematice a aplikacích, ISBN 0-89871-432-X.
- Cai, L. (1996), „Opravitelnost parametrů s problémy s modifikací grafů pro dědičné vlastnosti“, Dopisy o zpracování informací, 58 (4): 171–176, doi:10.1016/0020-0190(96)00050-6.
- Chu, Frank Pok Man (2008), „Jednoduchý lineární čas ověřující algoritmus založený na LBFS pro rozpoznávání triviálně dokonalých grafů a jejich doplňků“, Dopisy o zpracování informací, 107 (1): 7–12, doi:10.1016 / j.ipl.2007.12.009.
- Donnelly, Sam; Isaak, Garth (1999), „Hamiltonovské síly v prahových a arborescentních grafech srovnatelnosti“, Diskrétní matematika, 202 (1–3): 33–44, doi:10.1016 / S0012-365X (98) 00346-X
- Golumbic, Martin Charles (1978), „Triviálně dokonalé grafy“, Diskrétní matematika, 24 (1): 105–107, doi:10.1016 / 0012-365X (78) 90178-4.
- Gurski, Frank (2006), „Charakterizace pro grafy definované omezenými operacemi šířky NLC nebo kliky“, Diskrétní matematika, 306 (2): 271–277, doi:10.1016 / j.disc.2005.11.014.
- Nastos, James; Gao, Yong (2010), „Nová strategie větvení problémů s parametrizovanými grafy“, Přednášky z informatiky, 6509: 332–346, arXiv:1006.3020.
- Rotem, D. (1981), "Stack rare permutations", Diskrétní matematika, 33 (2): 185–196, doi:10.1016 / 0012-365X (81) 90165-5, PAN 0599081.
- Rubio-Montiel, C. (2015), „Nová charakteristika triviálně dokonalých grafů“, Elektronický deník teorie grafů a aplikací, 3 (1): 22–26, doi:10.5614 / ejgta.2015.3.1.3.
- Sharan, Roded (2002), "Problémy s úpravami grafů a jejich aplikace na genomický výzkum", Disertační práce, Tel Aviv University.
- Wolk, E. S. (1962), „Graf srovnatelnosti stromu“, Proceedings of the American Mathematical Society (5 ed.), 13: 789–795, doi:10.1090 / S0002-9939-1962-0172273-0.
- Wolk, E. S. (1965), „Poznámka ke grafu srovnatelnosti stromu“, Proceedings of the American Mathematical Society (1. vyd.), 16: 17–20, doi:10.1090 / S0002-9939-1965-0172274-5.
- Yan, Jing-Ho; Chen, Jer-Jeong; Chang, Gerard J. (1996), „Quasi-threshold graphs“, Diskrétní aplikovaná matematika, 69 (3): 247–255, doi:10.1016 / 0166-218X (96) 00094-7.