Prahový graf

V teorii grafů je prahový graf graf, který lze sestavit z grafu s jedním vrcholem postupným prováděním následujících dvou operací:

Přidání jednoho izolovaného vrcholu do grafu
Přidání jednoho dominantního vrcholu do grafu, tzn. jeden vrchol spojený se všemi ostatními vrcholy.

Například graf na obrázku je prahový graf. Lze jej postavit z jednoho vrcholu (vrchol 1) a přidat černé vrcholy jako izolované vrcholy a červené vrcholy jako dominantní vrcholy v číselném pořadí.

Prahové grafy zavedli Chvátal a Hammer [1] . Kapitola o grafech se objevila v Golumbikově knize [2] , zatímco kniha Mahadeva a Peleda [3] je celá věnována prahovým grafům.

Alternativní definice

Ekvivalentní definice je následující: graf je prahová hodnota, pokud existuje reálné číslo a pro každý vrchol je dána váha taková, že pro libovolné dva vrcholy je hrana tehdy a pouze tehdy, když . $S$ $proti$ $w(v)$ $v,u$ $UV$ $w(u)+w(v)>S$

Další ekvivalentní definice: graf je prahová hodnota, pokud existuje reálné číslo a pro každý vrchol je dána váha taková, že pro jakoukoli sadu vrcholů je nezávislý právě tehdy a jen tehdy $T$ $proti$ $a(v)$ $X\subseteq V$ $X$ $\sum _{v\in X}a(v)\leq T.$

Název "prahový graf" pochází z definice: S je "prah" pro vlastnost, aby měla hranu, nebo ekvivalentně T je práh pro nezávislost množiny.

Rozklad

Z definice pomocí sekvenčního sčítání vrcholů lze získat alternativní způsob, jak jednoznačně popsat prahový graf ve smyslu řetězce znaků. vždy slouží jako první znak řetězce a představuje první vrchol grafu. Každý následující znak bude buď , což znamená izolovaný vrchol, nebo , což znamená přidání dominantního vrcholu. Například řetězec představuje hvězdu se třemi listy, ale představuje cestu tří vrcholů. Graf na obrázku může být znázorněn čárou $\epsilon$ $u$ $j$ $\epsilon uuj$ $\epsilon uj$ $\epsilon uuujuuj$

Propojené třídy grafů a rozpoznávání

Prahové grafy jsou speciálním případem kografů , dělených grafů a triviálně dokonalých grafů [4] . Jakýkoli graf, který je současně kografem i rozděleným grafem, je prahovým grafem. Každý graf, který je zároveň triviálně dokonalým grafem i doplňkem triviálně dokonalého grafu, je prahovým grafem. Speciálním případem intervalových grafů jsou také prahové grafy . Všechny tyto souvislosti lze vysvětlit z hlediska jejich charakterizace zakázanými generovanými podgrafy. Cograph je graf bez vygenerovaných cest se čtyřmi vrcholy P 4 a prahové grafy jsou grafy bází generovaných podgrafů P 4 , C 4 nebo 2K 2 [5] . C 4 je cyklus čtyř vrcholů a 2K 2 je jeho doplněk, tedy dvě samostatné hrany. To také vysvětluje, proč jsou prahové grafy uzavřeny jako doplněk. P 4 je samokomplementární, a proto, pokud graf neobsahuje vygenerované podgrafy P 4 , C 4 a 2K 2 , nebude je mít ani jeho doplněk [6] .

Heggernes a kol., ukázali, že prahové grafy lze rozpoznat v lineárním čase. Pokud graf není prahový, bude indikována překážka ve tvaru P 4 , C 4 nebo 2K 2 .

Viz také

Poznámky

↑ Chvátal, Kladivo, 1977 .
↑ Golumbic, 1980 .
↑ Mahadev, Peled, 1995 .
↑ Emelichev, Melnikov, Sarvanov, Tyshkevich, 1990 , str. 227, důsledek 50.11.
↑ Emelichev, Melnikov, Sarvanov, Tyshkevich, 1990 , str. 224, důsledek 50.3.
↑ Emelichev, Melnikov, Sarvanov, Tyshkevich, 1990 , str. 227, důsledek 50.12.

Literatura

V.A. Emelichev, O.I. Melnikov, V.I. Sarvanov, R.I. Tyškevič. Přednášky z teorie grafů. - Moskva: "Nauka", 1990. - ISBN 5-02-013992-0 . §padesáti. Prahové grafy
Václav Chvátal, Peter Ladislaw Hammer. Studium celočíselného programování (Proc. Worksh. Bonn 1975) / PL Hammer, EL Johnson, BH Korte, GL Nemhauser. - Amsterdam: North-Holland, 1977. - V. 1. - S. 145-162. — (Anály diskrétní matematiky). .
Martin Charles Golumbic. Algoritmická teorie grafů a dokonalé grafy. - New York: Academic Press, 1980. . 2. vydání, Annals of Discrete Mathematics, 57 , Elsevier, 2004.
NVR Mahadev, Uri N. Peled. Prahové grafy a související témata. — Elsevier, 1995 .

Odkazy

Prahové grafy Archivovány 28. března 2016 na Wayback Machine , Informační systém o třídách grafů a jejich zahrnutí.