Tröskeldiagram

I grafteorin är en tröskelgraf en graf som kan byggas från en graf med en enda vertex genom att sekventiellt utföra följande två operationer:

Lägga till en isolerad vertex till grafen
Att lägga till en dominant vertex till grafen, dvs. en enda vertex kopplad till alla andra hörn.

Till exempel är grafen i figuren en tröskelgraf. Det kan byggas från ett hörn (topp 1) och lägga till svarta hörn som isolerade hörn och röda hörn som dominanta hörn i numerisk ordning.

Tröskelgrafer introducerades av Chvatal och Hammer [1] . Kapitlet om grafer dök upp i Golumbiks bok [2] , medan Mahadev och Peleds bok [3] helt och hållet ägnas åt tröskeldiagram.

Alternativa definitioner

En ekvivalent definition är följande: en graf är tröskel om det finns ett reellt tal och för varje hörn ges en vikt så att för två hörn , är en kant om och endast om . $S$ $v$ $w(v)$ $v,u$ $UV$ $w(u)+w(v)>S$

En annan ekvivalent definition: en graf är tröskel om det finns ett reellt tal och för varje vertex ges en vikt så att för varje uppsättning av hörn är oberoende om och endast om $T$ $v$ $a(v)$ $X\subseteq V$ $X$ $\sum _{v\in X}a(v)\leq T.$

Namnet "tröskeldiagram" kommer från definitionen: S är ett "tröskelvärde" för att egenskapen ska ha en kant, eller motsvarande, T är en tröskel för att en mängd ska vara oberoende.

Nedbrytning

Från definitionen som använder sekventiell addition av hörn, kan man få ett alternativt sätt att unikt beskriva tröskeldiagrammet i betydelsen av en teckensträng. fungerar alltid som det första tecknet i strängen och representerar grafens första hörn. Varje efterföljande tecken kommer antingen att vara , vilket betyder en isolerad vertex, eller , vilket betyder att man lägger till en dominant vertex. Till exempel representerar en sträng en stjärna med tre blad, men representerar en bana med tre hörn. Grafen i figuren kan representeras av linjen $\epsilon$ $u$ $j$ $\epsilon uuj$ $\epsilon uj$ $\epsilon uuujuuj$

Anslutna klasser av grafer och igenkänning

Tröskelgrafer är ett specialfall av kografer , delade grafer och trivialt perfekta grafer [4] . Varje graf som är både en kograf och en delad graf är en tröskelgraf. Varje graf som är både en trivialt perfekt graf och komplementet till 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 genererade subgrafer. En kograf är en graf utan genererade banor med fyra hörn, P 4 , och tröskeldiagram är grafer av baser av genererade subgrafer P 4 , C 4 eller 2K 2 [5] . C 4 är en cykel av fyra hörn, och 2K 2 är dess komplement, det vill säga två separata kanter. Detta förklarar också varför tröskeldiagram är komplementstängda. P 4 är självkomplementär, och därför, om grafen inte innehåller genererade subgrafer P 4 , C 4 och 2K 2 , kommer dess komplement inte heller att ha dem [6] .

Heggernes et al har visat att tröskelgrafer kan kännas igen i linjär tid. Om grafen inte är tröskelvärde indikeras ett hinder i form av P 4 , C 4 , eller 2K 2 .

Se även

Anteckningar

↑ Chvatal, Hammer, 1977 .
↑ Golumbic, 1980 .
↑ Mahadev, Peled, 1995 .
↑ Emelichev, Melnikov, Sarvanov, Tyshkevich, 1990 , sid. 227, följd 50.11.
↑ Emelichev, Melnikov, Sarvanov, Tyshkevich, 1990 , sid. 224, följd 50,3.
↑ Emelichev, Melnikov, Sarvanov, Tyshkevich, 1990 , sid. 227, följd 50.12.

Litteratur

V.A. Emelichev, O.I. Melnikov, V.I. Sarvanov, R.I. Tysjkevitj. Föreläsningar om grafteori. - Moskva: "Nauka", 1990. - ISBN 5-02-013992-0 . §femtio. Tröskeldiagram
Václav Chvátal, Peter Ladislaw Hammer. Studier i heltalsprogrammering (Proc. Worksh. Bonn 1975) / PL Hammer, EL Johnson, BH Korte, GL Nemhauser. - Amsterdam: Nord-Holland, 1977. - V. 1. - S. 145-162. — (Annals of Discret Mathematics). .
Martin Charles Golumbic. Algoritmisk grafteori och perfekta grafer. - New York: Academic Press, 1980. . 2:a upplagan, Annals of Discrete Mathematics, 57 , Elsevier, 2004.
NVR Mahadev, Uri N. Peled. Tröskeldiagram och relaterade ämnen. — Elsevier, 1995. .

Länkar

Tröskeldiagram Arkiverade 28 mars 2016 på Wayback Machine , informationssystem om grafklasser och deras inkludering.