Likgiltighetsdiagram - Indifference graph

En likgiltighetsdiagram, bildad av en uppsättning punkter på den verkliga linjen genom att koppla ihop punkter med högst ett avstånd

I grafteorin , en gren av matematiken, är en likgiltighetsgraf en oriktad graf konstruerad genom att tilldela ett verkligt tal till varje toppunkt och ansluta två vertikaler med en kant när deras tal ligger inom en enhet av varandra. Likgiltighetsdiagram är också korsningsdiagrammen för uppsättningar av enhetsintervaller eller av korrekt kapslade intervall (intervall som ingen innehåller någon annan). Baserat på dessa två typer av intervallrepresentationer kallas dessa diagram också enhetsintervalldiagram eller korrekta intervalldiagram ; de bildar en underklass av intervalldiagrammen .

Motsvarande karakteriseringar

Förbjudna inducerade underbilder för likgiltighetsdiagrammen: klo, sol och nät (överst, vänster – höger) och cykler med längd fyra eller fler (längst ner)

De ändliga likgiltighetsdiagrammen kan likvärdigt karakteriseras som

• De skärningsdiagram av enhetsintervaller ,
• Korsningsdiagrammen för intervalluppsättningar, varav inte två är kapslade (den ena innehåller den andra),
• De klofria intervalldiagrammen ,
• Diagrammen som inte har en inducerad subgraf isomorf till en klo K _1,3 , netto (en triangel med en grad-ett-toppunkt intill var och en av triangelns hörn), sol (en triangel omgiven av tre andra trianglar som var och en delar en kant med den centrala triangeln), eller hål (cykel längd fyra eller mer),
• De ojämförbarhet grafer av semiorders ,
• De oriktade graferna som har en linjär ordning så att för varje tre ordnade hörn - - , om det är en kant så är det och${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle w}$${\ displaystyle uw}$${\ displaystyle uv}$${\ displaystyle vw}$
• Diagrammen utan astral trippel , tre hörn kopplade parvis med banor som undviker det tredje toppunktet och innehåller inte två på varandra följande grannar till det tredje toppunktet,
• Diagrammen där varje ansluten komponent innehåller en väg där varje maximal klick av komponenten bildar en angränsande delväg,
• Diagrammen vars hörn kan numreras så att varje kortaste väg bildar en monoton sekvens ,
• Diagrammen vars angränsande matriser kan ordnas så att, i varje rad och varje kolumn, matrisens nollor bildar ett angränsande intervall intill matrisens huvuddiagonal.
• De inducerade underbilderna av krafter på ackordlösa vägar.
• De blad krafter som har en bladroten, som är en larv.

För oändliga diagram kan vissa av dessa definitioner skilja sig åt.

Egenskaper

Eftersom de är speciella fall av intervalldiagram har likgiltighetsdiagram alla egenskaper för intervalldiagram; i synnerhet är de ett speciellt fall för ackorddiagrammen och de perfekta graferna . De är också ett speciellt fall för cirkeldiagram , något som inte är sant för intervalldiagram mer generellt.

I Erdős – Rényi-modellen av slumpmässiga grafer , kommer en -vertexgraf vars antal kanter är signifikant mindre än en likgiltighetsgraf med hög sannolikhet, medan en graf vars antal kanter är betydligt mer än inte kommer att vara en likgiltighetsgraf med hög sannolikhet. ${\ displaystyle n}$${\ displaystyle n ^ {2/3}}$${\ displaystyle n ^ {2/3}}$

Den bandbredd för en godtycklig graf är ett mindre än storleken på den maximala klick i en likgiltighet graf som innehåller som en subgraf och väljes för att minimera storleken av den maximala klick. Den här egenskapen är parallell med liknande förhållanden mellan kurvor för vägbredd och intervall , och mellan kurvor för träbredd och ackord . En svagare uppfattning om bredd, klickbredden , kan vara godtyckligt stor på likgiltighetsdiagram. Emellertid har varje ordentlig underklass av likgiltighetsdiagrammen som stängs under inducerade underbilder begränsat klickbredden. ${\ displaystyle G}$${\ displaystyle G}$

Varje ansluten likgiltighetsdiagram har en Hamiltonisk väg . En likgiltighetsdiagram har en Hamilton-cykel om och bara om den är kopplad .

Likgiltighetsdiagram följer rekonstruktionens antaganden : de bestäms unikt av deras topp-raderade underbilder.

Algoritmer

Som med högdimensionella enhetsdiagram är det möjligt att omvandla en uppsättning punkter till deras likgiltighetsdiagram, eller en uppsättning enhetsintervaller till deras enhetsintervalldiagram, i linjär tid uppmätt i storleken på utgångsdiagrammet. Algoritmen avrundar punkterna (eller intervallcentra) ner till närmaste mindre heltal, använder en hash-tabell för att hitta alla par av punkter vars avrundade heltal ligger inom varandra ( problemet med fast radie nära grannar ) och filtrerar det resulterande lista över par för de vars oavgränsade värden också ligger i varandra.

Det är möjligt att testa om en given graf är en likgiltighetsgraf på linjär tid genom att använda PQ-träd för att konstruera en intervallrepresentation av diagrammet och sedan testa om en vertexordning som härrör från denna representation uppfyller egenskaperna hos en likgiltighetsgraf. Det är också möjligt att basera en igenkänningsalgoritm för likgiltiga grafer på algoritmer för ackordgenkänning . Flera alternativa linjära tidsigenkänningsalgoritmer är baserade på bredd-först-sökning eller lexikografisk bredd-första-sökning snarare än på sambandet mellan likgiltighetsdiagram och intervalldiagram.

När hörnen har sorterats efter de numeriska värdena som beskriver ett likgiltighetsdiagram (eller efter sekvensen av enhetsintervallen i en intervallrepresentation) kan samma ordning användas för att hitta en optimal graffärgning för dessa grafer, för att lösa det kortaste banproblemet , och att konstruera Hamiltoniska banor och maximala matchningar , allt i linjär tid. En Hamilton-cykel kan hittas från en korrekt intervallrepresentation av diagrammet i tid , men när själva diagrammet ges som inmatning, medger samma problem linjär tidslösning som kan generaliseras till intervalldiagram. ${\ displaystyle O (n \ log n)}$

Listfärgning förblir NP-komplett även när den är begränsad till likgiltighetsdiagram. Det är emellertid fast parametrar som går att använda när det parametreras av det totala antalet färger i ingången.

Applikationer

I matematisk psykologi uppstår likgiltighetsdiagram från verktygsfunktioner genom att skala funktionen så att en enhet representerar en skillnad i verktyg som är tillräckligt små för att individer kan antas vara likgiltiga för den. I den här applikationen kan par av artiklar vars verktyg har stor skillnad delvis ordnas efter den relativa ordningen på deras verktyg, vilket ger en halvledare .

I bioinformatik kan problemet med att förstärka ett färgat diagram till ett korrekt färgat enhetsintervalldiagram användas för att modellera detekteringen av falska negativ i DNA- sekvensmontering från fullständiga sammandrag .

Se även

• Tröskeldiagram , ett diagram vars kanter bestäms av summan av vertex-etiketter snarare än skillnader mellan etiketter
• Trivialt perfekt diagram , intervalldiagram för vilka varje par intervall är kapslade eller ojämna snarare än att korsas ordentligt

Referenser

externa länkar

• Informationssystem om diagramklassinkluderingar : enhetsintervalldiagram