Jämförbarhet graf - Comparability graph

I grafteori är en jämförbarhetsgraf en oriktad graf som förbinder elementpar som är jämförbara med varandra i en delordning . Jämförbarhetsgrafer har också kallats transitivt orienterbara grafer , delvis ordningsbara grafer , inneslutningsgrafer och delningsgrafer . En ojämförbarhetsgraf är en oriktad graf som förbinder elementpar som inte är jämförbara med varandra i en delordning .

Definitioner och karaktärisering

Hasse -diagram över en poset (vänster) och dess jämförbarhetsgraf (höger)

En av de förbjudna inducerade subgraferna av en jämförbarhetsgraf. Den generaliserade cykeln a - b - d - f - d - c - e - c - b - a i denna graf har udda längd (nio) men har inga triangulära ackord.

För alla strikt delvis ordnade uppsättningar ( S , <) är jämförbarhetsdiagrammet för ( S , <) grafen ( S , ⊥) vars hörn är elementen i S och kanterna är de paren { u , v } av element så att u < v . Det vill säga, för en delvis ordnad uppsättning, ta den riktade acykliska grafen , applicera transitiv stängning och ta bort orientering.

På motsvarande sätt är en jämförbarhetsgraf en graf som har en transitiv orientering , en tilldelning av riktningar till grafens kanter (dvs en orientering av grafen) så att adjacensförhållandet för den resulterande riktade grafen är transitivt : när det finns riktade kanter ( x , y ) och ( y , z ) måste det finnas en kant ( x , z ).

Man kan representera alla ändliga delordningar som en grupp av uppsättningar, så att x < y i delordningen närhelst uppsättningen som motsvarar x är en delmängd av uppsättningen som motsvarar y . På detta sätt kan jämförbarhetsgrafer visas vara ekvivalenta med inneslutningsgrafer för uppsatta familjer; det vill säga en graf med en toppunkt för varje uppsättning i familjen och en kant mellan två uppsättningar när den ena är en delmängd av den andra. Alternativt kan man representera delordningen av en helhetsfamilj , så att x < y när heltalet som motsvarar x är en divisor av heltalet som motsvarar y . På grund av denna konstruktion har jämförbarhetsgrafer också kallats delningsgrafer.

Jämförbarhetsgrafer kan karakteriseras som graferna så att för varje generaliserad cykel med udda längder kan man hitta en kant ( x , y ) som förbinder två hörn som är på avstånd två i cykeln. En sådan kant kallas ett triangulärt ackord . I detta sammanhang definieras en generaliserad cykel som en sluten gång som använder varje kant av grafen högst en gång i varje riktning. Jämförbarhetsdiagram kan också kännetecknas av en lista över förbjudna inducerade subgrafer .

Relation till andra graffamiljer

Varje komplett graf är en jämförbarhet graf, jämförbarhet graf för en total order . Alla acykliska orienteringar för ett komplett diagram är transitiva. Varje bipartitgraf är också ett jämförelsediagram. Orientering av kanterna på en bipartitgraf från ena sidan av bipartitionen till den andra resulterar i en transitiv orientering, motsvarande en partiell ordning av höjd två. Som Seymour (2006) konstaterar har varje jämförbarhetsgraf som varken är fullständig eller bipartit en sned partition .

Den komplementet av någon intervall grafen är en jämförelse grafen. Jämförbarhetsrelationen kallas en intervallordning . Intervallgrafer är exakt de grafer som är ackordala och som har jämförelsegrafkomplement.

Ett permutationsdiagram är ett inneslutningsdiagram med en uppsättning intervall. Därför är permutationsgrafer en annan underklass av jämförbarhetsgrafer.

De trivialt perfekta graferna är jämförbarhetsgrafer för rotade träd . Cographs kan karakteriseras som jämförbarhetsgrafer för serieparallella partiella ordningar ; sålunda är cographs också jämförbarhetsgrafer.

Tröskelgrafer är en annan speciell typ av jämförbarhetsdiagram.

Varje jämförbarhetsgraf är perfekt . Perfektion av jämförbarhetsgrafer är Mirskys sats , och perfektion av deras komplement är Dilworths sats ; dessa fakta, tillsammans med den perfekta grafsatsen kan användas för att bevisa Dilworths sats från Mirskys sats eller vice versa. Mer specifikt är jämförbarhetsgrafer perfekt ordningsbara grafer , en underklass med perfekta grafer: en girig färgningsalgoritm för en topologisk ordning av en transitiv orientering av grafen kommer att färga dem optimalt.

Den komplementet av varje jämförelse grafen är en sträng diagram .

Algoritmer

En transitiv orientering av en graf, om den finns, kan hittas i linjär tid. Men algoritmen för att göra det kommer att tilldela orienteringar till kanterna på en graf, så för att slutföra uppgiften att testa om en graf är en jämförbarhetsgraf måste man testa om den resulterande orienteringen är transitiv, ett problem som bevisligen är likvärdigt i komplexitet med matrisen multiplikation .

Eftersom jämförbarhetsgrafer är perfekta kan många problem som är svåra för mer allmänna klasser av grafer, inklusive graffärgning och det oberoende uppsatta problemet , lösas på polynomtid för jämförbarhetsgrafer.

Anteckningar

Referenser