Tærskelgraf

I grafteori er en tærskelgraf en graf, der kan bygges ud fra en enkelt-vertex-graf ved sekventielt at udføre følgende to operationer:

Tilføjelse af et isoleret toppunkt til grafen
Tilføjelse af ét dominerende toppunkt til grafen, dvs. et enkelt toppunkt forbundet med alle andre toppunkter.

For eksempel er grafen i figuren en tærskelgraf. Den kan bygges ud fra et toppunkt (top 1) og tilføje sorte toppunkter som isolerede toppunkter og røde toppunkter som dominerende toppunkter i numerisk rækkefølge.

Tærskelgrafer blev introduceret af Chvatal og Hammer [1] . Kapitlet om grafer dukkede op i Golumbiks bog [2] , mens Mahadev og Peleds bog [3] udelukkende er viet til tærskelgrafer.

Alternative definitioner

En ækvivalent definition er som følger: en graf er tærskel, hvis der eksisterer et reelt tal, og for hvert toppunkt er en vægt givet sådan, at for alle to hjørner , er en kant, hvis og kun hvis . $S$ $v$ $w(v)$ $v,u$ $UV$ $w(u)+w(v)>S$

En anden ækvivalent definition: en graf er tærskel, hvis der eksisterer et reelt tal, og for hvert knudepunkt er en vægt givet således, at for ethvert sæt hjørner er uafhængig, hvis og kun hvis $T$ $v$ $a(v)$ $X\subseteq V$ $x$ $\sum _{v\in X}a(v)\leq T.$

Navnet "tærskelgraf" kommer fra definitionen: S er en "tærskel" for, at egenskaben har en kant, eller tilsvarende er T en tærskel for, at et sæt er uafhængigt.

Dekomponering

Fra definitionen ved hjælp af sekventiel tilføjelse af hjørner kan man få en alternativ måde at beskrive tærskelgrafen entydigt i betydningen af en tegnstreng. fungerer altid som det første tegn i strengen og repræsenterer grafens første toppunkt. Hvert efterfølgende tegn vil enten være , hvilket betyder et isoleret toppunkt, eller , hvilket betyder tilføjelse af et dominant toppunkt. For eksempel repræsenterer en streng en stjerne med tre blade, men repræsenterer en sti med tre hjørner. Grafen i figuren kan repræsenteres af linjen $\epsilon$ $u$ $j$ $\epsilon uuj$ $\epsilon uj$ $\epsilon uuujuuj$

Forbundne klasser af grafer og genkendelse

Tærskelgrafer er et særligt tilfælde af kografer , opdelte grafer og trivielt perfekte grafer [4] . Enhver graf, der både er en kograf og en opdelt graf, er en tærskelgraf. Enhver graf, der både er en trivielt perfekt graf og komplementet til en trivielt perfekt graf, er en tærskelgraf. Tærskelgrafer er også et særligt tilfælde af intervalgrafer . Alle disse forbindelser kan forklares i form af deres karakterisering af forbudte genererede undergrafer. En kograf er en graf uden genererede stier med fire spidser, P 4 , og tærskelgrafer er grafer af baser af genererede undergrafer P 4 , C 4 eller 2K 2 [5] . C 4 er en cyklus af fire hjørner, og 2K 2 er dens komplement, det vil sige to separate kanter. Dette forklarer også, hvorfor tærskelgrafer er komplement-lukkede. P 4 er selvkomplementær, og derfor, hvis grafen ikke indeholder genererede undergrafer P 4 , C 4 og 2K 2 , vil dens komplement heller ikke have dem [6] .

Heggernes et al. har vist, at tærskelgrafer kan genkendes i lineær tid. Hvis grafen ikke er tærskel, vil en forhindring i form af P 4 , C 4 eller 2K 2 blive vist.

Se også

Noter

↑ Chvatal, Hammer, 1977 .
↑ Golumbic, 1980 .
↑ Mahadev, Peled, 1995 .
↑ Emelichev, Melnikov, Sarvanov, Tyshkevich, 1990 , s. 227, Følge 50.11.
↑ Emelichev, Melnikov, Sarvanov, Tyshkevich, 1990 , s. 224, Følge 50,3.
↑ Emelichev, Melnikov, Sarvanov, Tyshkevich, 1990 , s. 227, Følge 50.12.

Litteratur

V.A. Emelichev, O.I. Melnikov, V.I. Sarvanov, R.I. Tysjkevitj. Forelæsninger om grafteori. - Moskva: "Nauka", 1990. - ISBN 5-02-013992-0 . §halvtreds. Tærskelgrafer
Václav Chvátal, Peter Ladislaw Hammer. Studies in Integer Programming (Proc. Worksh. Bonn 1975) / PL Hammer, EL Johnson, BH Korte, GL Nemhauser. - Amsterdam: Nord-Holland, 1977. - V. 1. - S. 145-162. — (Annals of Discrete Mathematics). .
Martin Charles Golumbic. Algoritmisk grafteori og perfekte grafer. - New York: Academic Press, 1980. . 2. udgave, Annals of Discrete Mathematics, 57 , Elsevier, 2004.
NVR Mahadev, Uri N. Peled. Tærskelgrafer og relaterede emner. — Elsevier, 1995. .