Trivielt perfekt graf

En trivielt perfekt graf er en graf med den egenskab, at størrelsen af den maksimale (i størrelse) uafhængige mængde i hver af dens genererede undergrafer er lig med antallet af maksimale kliker [1] [2] . Trivielt perfekte grafer blev først studeret af Volk [3] [4] , men navnet blev givet af Golumbik [2] . Golumbik skrev, at "dette navn blev valgt i lyset af trivialiteten i at bevise, at sådanne grafer er perfekte ." Trivielt perfekte grafer er også kendt som træ-sammenlignelighedsgrafer [3] [4] , træ-sammenlignelighedsgrafer [5] og kvasithreshold-grafer [6] .

Tilsvarende beskrivelser

Trivielt perfekte grafer har flere andre tilsvarende beskrivelser:

De er sammenlignelighedsgrafer af træer fra ordensteori . Det vil sige, lad T være en partiel orden , således at for enhver t ∈ T er mængden { s ∈ T : s < t } velordnet med relation < og T har det mindste element r . Så er sammenlignelighedsgrafen af orden T trivielt perfekt og enhver trivielt perfekt graf kan dannes på denne måde [7] [8] .
De er grafer, der ikke indeholder en P 4 - sti eller en C 4 -cyklus som genererede undergrafer [7] [9] [10]
De er grafer, hvor hver tilsluttet genereret subgraf indeholder et universelt toppunkt [11] .
De er grafer, der kan opfattes som intervalgrafer for et sæt indlejrede spænd . Et sæt mellemrum har indlejringsegenskaben, hvis de for to mellemrum fra sættet enten ikke skærer hinanden, eller en af dem er indeholdt i den anden [12] .
Det er grafer, der både er akkordgrafer og kografer [13] [14] . Dette følger af beskrivelsen af akkordgrafer som grafer uden genererede cyklusser af længde fire eller flere og kografer som grafer uden genererede stier med fire toppunkter ( P 4 ).
Det er grafer, der både er kografer og intervalgrafer [13] [14] .
De er grafer, der kan dannes ud fra grafer med et toppunkt ved at bruge to operationer - en usammenhængende forening af to mindre trivielt perfekte grafer og tilføjelse af et nyt toppunkt ved siden af alle hjørner af den mindre trivielt perfekte graf [6] [15] . Disse operationer svarer til dannelsen af en ny skov ved usammenhængende at forbinde to mindre skove, og dannelsen af et træ ved at forbinde en ny rod til rødderne af alle træerne i skoven.
De er grafer, hvori for enhver kant uv , kvartererne af hjørnerne u og v (inklusive u og v selv ) er indlejret - det ene kvarter skal være et kvarter af det andet [14] .
De er permutationsgrafer defineret ud fra permutationer sorteret på stakken [16] .
De er grafer med den egenskab, at i hver af dens genererede undergrafer er antallet af klikdækning lig med antallet af maksimale kliker [17] .
De er grafer med den egenskab, at i hver af dens genererede undergrafer er kliktallet lig med Grandi-pseudo- tallet [17] .
De er grafer med den egenskab, at det kromatiske tal for hver af dens genererede undergrafer er lig med pseudo Grandi-tallet [17] .

Relaterede grafklasser

Det følger af tilsvarende beskrivelser af trivielt perfekte grafer, at enhver trivielt perfekt graf også er en kograf , akkord , ptolemæisk , interval og perfekt graf .

Tærskelgrafer er præcis de grafer, der både er trivielt perfekte og er komplementet til trivielt perfekte grafer (trivielt perfekte kografer) [18] [19] .

Møller er trivielt perfekte.

Anerkendelse

Chu [20] beskriver en simpel lineær tidsalgoritme til at genkende trivielt perfekte grafer baseret på leksikografisk bredde-først søgning . Når LexBFS-algoritmen fjerner v fra det første sæt i køen, kontrollerer algoritmen, at alle resterende naboer til v er i det samme sæt. Hvis ikke, kan en af de forbudte genererede undergrafer bygges fra v . Hvis kontrollen lykkes for alle v , så er grafen trivielt perfekt. Algoritmen kan modificeres til at teste i lineær tid, om en graf er komplementet til en trivielt perfekt graf.

At bestemme om en generel graf efter fjernelse af k kanter bliver en trivielt perfekt graf er et NP-komplet problem [21] , som kan løses med faste parametre [22] , og det kan løses i tiden O(2,45 k (m+n) ) [ 23] .

Noter

↑ Brandstädt, Le, Spinrad, 1999 , s. 34 definition 2.6.2.
↑ 1 2 Golumbic, 1978 .
↑ 12 Wolk , 1962 .
↑ 12 Wolk , 1965 .
↑ Donnelly, Isaak, 1999 .
↑ 12 Yan , Chen, Chang, 1996 .
↑ 1 2 Brandstädt, Le, Spinrad, 1999 , s. 99 Sætning 6.6.1.
↑ Golumbic, 1978 , s. følge 4.
↑ Golumbic, 1978 , s. sætning 2.
↑ Wolk 1962 beviste dette for rodfæstede skovsammenlignelighedsgrafer.
↑ Wolk (1962) .
↑ Brandstädt, Le, Spinrad, 1999 , s. 51.
↑ 1 2 Brandstädt, Le, Spinrad, 1999 , s. 248.
↑ 1 2 3 Yan, Chen, Chang, 1996 , s. sætning 3.
↑ Gurski, 2006 .
↑ Rotem, 1981 .
↑ 1 2 3 Rubio-Montiel (2015) .
↑ Brandstädt, Le, Spinrad, 1999 , s. 100 Sætning 6.6.3.
↑ Golumbic, 1978 , s. følge 5.
↑ Chu, 2008 .
↑ Sharan (2002) .
↑ Cai (1996) .
↑ Nastos, Gao, 2010 .

Litteratur