A matematika, azon belül a gráfelmélet területén egy küszöbgráf (threshold graph) olyan gráf, ami előállítható az egy csúcsból álló gráfból a következő két művelet bármelyikének ismételt alkalmazásával: A gráfhoz hozzáadunk egy izolált csúcsot. A gráfhoz hozzáadunk egy univerzális csúcsot (domináló csúcsot), tehát egy olyan csúcsot, ami minden más csúccsal össze van kötve.

A küszöbgráfokat vezette be. A küszöbgráfokról a egy fejezete szól, pedig egy teljes könyvet szentelt nekik.

Alternatív definíciók A fentivel ekvivalens definíció a következő: egy gráf pontosan akkor küszöbgráf, ha létezik olyan valós szám, továbbá a gráf minden csúcsához hozzárendelhető egy valós értékű súly úgy, hogy bármely két csúcs között akkor húzódik él, ha .

Egy másik, ekvivalens definíció: egy gráf pontosan akkor küszöbgráf, ha létezik olyan valós szám és minden csúcshoz egy valós értékű súly úgy, hogy bármely csúcshalmazra, pontosan akkor független csúcshalmaz, ha

A „küszöbgráf” elnevezés ezekből a definíciókból ered: S az él behúzásának, vagy ezzel egyenértékű módon T a független csúcshalmaznak levés küszöbértéke.

Felbontás A csúcsok ismételt hozzáadását alkalmazó definícióból megalkotható a küszöbgráfok leírásának egy alternatív, szimbólumok sorozatával való leírása. az első karaktere a karakterláncnak, a gráf első csúcsát jelképezve. Az összes többi karakter vagy , jelölve a hozzáadott izolált csúcsot (vagy unió csúcsot) vagy , ami a hozzáadott domináló csúcsot (vagy join, azaz összekapcsolási csúcs). Így például az karakterlánc a három ágú csillaggráfot írja le, míg az a három csúcsú útgráfot. Az ábrán látható gráf így fejezhető ki: .

Kapcsolódó gráfcsaládok, felismerésük A küszöbgráfok a kográfok, a split gráfok és a triviálisan perfekt gráfok speciális esetei. Bármely gráf, ami egyszerre kográf és split gráf, az küszöbgráf. Bármely gráf, ami triviálisan perfekt és a komplementere is az, szintén küszöbgráf. A küszöbgráfok továbbá az intervallumgráfok speciális esetei is. Ezek a kapcsolatok kifejezhetők a tiltott feszített részgráfok szerinti jellemzés alapján: a kográf nem tartalmaz P4 négy csúcs közötti feszített utat, míg a küszöbgráf nem tartalmaz sem feszített P4-et, C4-et vagy 2K2-t. C4 a négy csúcs között húzódó kör, 2K2 pedig a komplementere, azaz két diszjunkt él. Ez megmagyarázza, hogy a küszöbgráfok miért zártak a komplementerképzés műveletére nézve: a P4 önmaga komplementere, így ha egy gráf P4-, C4- és 2K2-mentes, komplementere is az lesz.

megmutatta, hogy a küszöbgráfok lineáris időben felismerhetők; ha egy gráf nem küszöb-, bizonyíték-algoritmusa valamely tiltott részgráfot adja eredményül.

Kapcsolódó szócikkek Egység-intervallumgráf Soros-párhuzamos gráf

Fordítás

Jegyzetek . . 2nd edition, Annals of Discrete Mathematics, 57, Elsevier, 2004. . .

További információk Threshold graphs, Information System on Graph Classes and their Inclusions.

Kategória:Gráfcsaládok Kategória:Perfekt gráfok