Tröskeldiagram

Ett exempel på en tröskelgraf.

I grafteori är en tröskelgraf en graf som kan konstrueras från en graf med en vertex genom upprepade tillämpningar av följande två operationer:

1. Tillägg av en enda isolerad vertex till grafen.
2. Addering av en enda dominerande vertex till grafen, dvs en enda vertex som är kopplad till alla andra hörn.

Till exempel är grafen för figuren en tröskelgraf. Den kan konstrueras genom att börja med en graf med en enda hörn (topp 1) och sedan lägga till svarta hörn som isolerade hörn och röda hörn som dominerande hörn, i den ordning som de är numrerade.

Tröskelgrafer introducerades först av Chvátal & Hammer (1977) . Ett kapitel om tröskeldiagram visas i Golumbic (1980) , och boken Mahadev & Peled (1995) ägnas åt dem.

Alternativa definitioner

En ekvivalent definition är följande: en graf är en tröskelgraf om det finns ett reellt tal $S$ och för varje vertex $v$ en reell vertexvikt $w(v)$ så att för alla två hörn $v,u$ , $uv$ är en kant om och endast om $w(u) +w(v)>S$ .

En annan ekvivalent definition är denna: en graf är en tröskelgraf om det finns ett reellt tal $T$ och för varje vertex $v$ en reell vertexvikt $a(v)$ så att för varje vertexmängd $X\subseteq V$ , $X$ är oberoende om och endast om $\sum _{v\in X}a(v)\leq T.$

Namnet "tröskeldiagram" kommer från dessa definitioner: S är "tröskeln" för egenskapen att vara en kant, eller motsvarande T är tröskeln för att vara oberoende.

Tröskelgrafer har också en förbjuden grafkarakterisering : En graf är en tröskelgraf om och endast om den inte har fyra av dess hörn bildar en inducerad subgraf som är en trekantsvägsgraf , en fyrkantscykelgraf eller en tvåkantsgraf matchning .

Sönderfall

Från definitionen som använder upprepad addition av hörn kan man härleda ett alternativt sätt att unikt beskriva en tröskelgraf, med hjälp av en sträng av symboler. $\epsilon$ är alltid det första tecknet i strängen och representerar grafens första hörn. Varje efterföljande tecken är antingen $u$ , vilket anger tillägget av en isolerad vertex (eller unionspunkt ), eller $j$ , som anger tillägget av en dominerande vertex (eller sammanfogad vertex). Till exempel representerar strängen $\epsilon uuj$ en stjärngraf med tre blad, medan $\epsilon uj$ representerar en bana på tre hörn. Grafen för figuren kan representeras som $\epsilon uuujuuj$

Relaterade klasser av grafer och igenkänning

Tröskelgrafer är ett specialfall av kografer , delade grafer och trivialt perfekta grafer . En graf är en tröskelgraf om och bara om den är både en kograf och en delad graf. Varje graf som är både en trivialt perfekt graf och den komplementära grafen för en trivialt perfekt graf är en tröskelgraf. Tröskeldiagram är också ett specialfall av intervallgrafer . Alla dessa samband kan förklaras i termer av deras karaktärisering av förbjudna inducerade subgrafer. En kograf är en graf utan inducerad väg på fyra hörn, P ₄ , och en tröskelgraf är en graf utan inducerad P ₄ , C ₄ eller 2K ₂ . C ₄ är en cykel av fyra hörn och 2K ₂ är dess komplement, det vill säga två disjunkta kanter. Detta förklarar också varför tröskeldiagram är stängda under tagande av komplement; P ₄ är självkomplementär, så om en graf är P ₄ -, C ₄ - och 2K ₂ -fri, så är dess komplement det också.

Heggernes & Kratsch (2007) visade att tröskelgrafer kan kännas igen i linjär tid; om en graf inte _{är tröskelvärde,} kommer ett hinder (en av P4, _C4 eller 2K2) _{att matas ut.}

Se även

• Likgiltighetsgraf
• Serie-parallell graf
• Tröskelhypergrafer

• Chvátal, Václav ; Hammer, Peter L. (1977), "Aggregation av olikheter i heltalsprogrammering", i Hammer, PL; Johnson, EL; Korte, BH; et al. (red.), Studies in Integer Programming (Proc. Worksh. Bonn 1975) , Annals of Discrete Mathematics, vol. 1, Amsterdam: North-Holland, s. 145–162 .
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs , New York: Academic Press . 2:a upplagan, Annals of Discrete Mathematics, 57 , Elsevier, 2004.
•   Heggernes, Pinar ; Kratsch, Dieter (2007), "Linear-time certifiating recognition algorithms and forbidden induced subgraphs" (PDF) , Nordic Journal of Computing , 14 (1–2): 87–108 (2008), MR 2460558 .
• Mahadev, NVR; Peled, Uri N. (1995), Tröskeldiagram och relaterade ämnen , Elsevier .

externa länkar

• Tröskeldiagram , informationssystem om grafklasser och deras inkludering.