matematikai fogalom a gráfelméletben From Wikipedia, the free encyclopedia
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 küszöbgráfokat (Chvátal & Hammer 1977) vezette be. A küszöbgráfokról a (Golumbic 1980) egy fejezete szól, (Mahadev & Peled 1995) pedig egy teljes könyvet szentelt nekik.
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.
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: .
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.
(Heggernes & Kratsch 2007) 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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.