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í:
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.
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ž .
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
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.
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
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 .