Küszöbgráf

Példa küszöbgráfra.
A létrehozás lépései: kiindulunk az egy csúcsból álló gráfból (1-es csúcs), majd hozzáadjuk a fekete izolált csúcsokat és a piros domináló csúcsokat, a számozás sorrendjében.

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:

  1. A gráfhoz hozzáadunk egy izolált csúcsot.
  2. 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 (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.

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.

(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.

Kapcsolódó szócikkek

Fordítás

  • Ez a szócikk részben vagy egészben a Threshold graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

További információk

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!