Perfekt beställningsbar graf

I grafteorin är en perfekt beställningsbar graf en graf vars hörn kan ordnas på ett sådant sätt att en girig färgalgoritm med denna ordning optimalt färgar varje inducerad subgraf i den givna grafen. Perfekt beställningsbara grafer utgör ett specialfall av de perfekta graferna , och de inkluderar ackordsgrafer , jämförbarhetsgrafer och ärftliga avståndsgrafer . Men att testa om en graf är perfekt beställningsbar är NP-komplett .

Definition

Den giriga färgningsalgoritmen, när den tillämpas på en given ordning av hörnen i en graf G , beaktar grafens hörn i sekvens och tilldelar varje vertex sin första tillgängliga färg, det minsta uteslutna värdet för den färguppsättning som används av dess grannar. Olika vertexordningar kan leda till att denna algoritm använder olika antal färger. Det finns alltid en ordning som leder till en optimal färgsättning – det gäller till exempel den ordning som bestäms utifrån en optimal färgsättning genom att sortera hörnen efter deras färg – men det kan vara svårt att hitta. De perfekt beställningsbara graferna definieras som de grafer för vilka det finns en ordning som är optimal för den giriga algoritmen, inte bara för själva grafen utan för alla dess inducerade subgrafer .

Mer formellt sägs en graf G vara perfekt ordningsbar om det finns en ordning π av hörn av G , så att varje inducerad subgraf av G färgas optimalt av den giriga algoritmen med hjälp av undersekvensen av π inducerad av hörnen i subgrafen . En ordningsföljd π har denna egenskap exakt när det inte finns fyra hörn a , b , c , och d för vilka abcd är en inducerad väg, a förekommer före b i ordningen och c förekommer efter d i ordningen.

Beräkningskomplexitet

Perfekt beställningsbara grafer är NP-kompletta att känna igen. Det är dock lätt att testa om en viss ordning är en perfekt ordning av en graf. Följaktligen är det också NP-svårt att hitta en perfekt ordning på en graf, även om grafen redan är känd för att vara perfekt beställningsbar.

Relaterade grafklasser

Varje perfekt beställningsbar graf är en perfekt graf .

Chordal grafer är perfekt beställningsbara; en perfekt ordning av en ackordsgraf kan hittas genom att vända en perfekt elimineringsordning för grafen. Att tillämpa girig färgläggning till en perfekt ordning ger således en effektiv algoritm för optimal färgläggning av ackordsgrafer. Jämförbarhetsgrafer är också perfekt beställningsbara, med en perfekt ordning som ges av en topologisk ordning av en transitiv orientering av grafen. Komplementgraferna för toleransgraferna är perfekt beställningsbara .

En annan klass av perfekt beställningsbara grafer ges av graferna G så att i varje delmängd av fem hörn från G , minst en av de fem har en sluten grannskap som är en delmängd av (eller lika med) den slutna grannskapet av en annan av de fem hörnen. På motsvarande sätt är dessa grafer där den partiella ordningen för slutna kvarter, ordnade efter inkludering av set, har bredd som högst fyra. Cykeldiagrammet med 5 vertex har en partiell ordningsföljd i grannskapet på bredd fem, så fyra är den maximala bredden som säkerställer perfekt beställningsbarhet. Liksom med ackordsgraferna (och till skillnad från de perfekt beställningsbara graferna mer generellt) är graferna med bredd fyra igenkännbara i polynomtid.

Ett begrepp som ligger mellan den perfekta elimineringsordningen för en ackordsgraf och en perfekt ordningsföljd är en semiperfekt elimineringsordning : i en elimineringsordning finns det ingen trepunktsinducerad bana där mittpunkten är den första av de tre som ska elimineras, och i en semiperfekt elimineringsordning, finns det ingen fyrpunktsinducerad bana där en av de två mittersta hörnen är den första som elimineras. Det omvända av denna ordning uppfyller därför kraven för en perfekt ordning, så grafer med semiperfekta elimineringsordningar är perfekt beställningsbara. I synnerhet kan samma lexikografiska bredd-först sökalgoritm som används för att hitta perfekta elimineringsordningar för ackordsgrafer användas för att hitta semiperfekta elimineringsordningar för avståndsärftliga grafer , som därför också är perfekt beställningsbara.

De grafer för vilka varje vertexordning är en perfekt ordning är kograferna . Eftersom kografer är graferna utan en inducerad väg med fyra vertex, kan de inte bryta mot kravet på banordning vid en perfekt ordning.

Flera ytterligare klasser av perfekt beställningsbara grafer är kända.

Anteckningar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Perfectly_orderable_graph&oldid=1136192565 "