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 Sablon:Harvtxt vezette be. A küszöbgráfokról a Sablon:Harvtxt egy fejezete szól, Sablon:Harvtxt 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 $S$ valós szám, továbbá a gráf minden $v$ csúcsához hozzárendelhető egy $w(v)$ valós értékű súly úgy, hogy bármely két $v,u$ csúcs között akkor húzódik $uv$ él, ha $w(u)+w(v)>S$.

Egy másik, ekvivalens definíció: egy gráf pontosan akkor küszöbgráf, ha létezik olyan $T$ valós szám és minden $v$ csúcshoz egy $a(v)$ valós értékű súly úgy, hogy bármely $X\subseteq V$ csúcshalmazra, $X$ pontosan akkor független csúcshalmaz, ha $\sum _{v\in X}a(v)\le T.$

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 $u$, jelölve a hozzáadott izolált csúcsot (vagy unió csúcsot) vagy $j$, ami a hozzáadott domináló csúcsot (vagy join, azaz összekapcsolási csúcs). Így például az $ϵuuj$ karakterlánc a három ágú csillaggráfot írja le, míg az $ϵuj$ a három csúcsú útgráfot. Az ábrán látható gráf így fejezhető ki: $ϵuuujuuj$.

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 P₄ négy csúcs közötti feszített utat, míg a küszöbgráf nem tartalmaz sem feszített P₄-et, C₄-et vagy 2K₂-t. C₄ a négy csúcs között húzódó kör, 2K₂ 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 P₄ önmaga komplementere, így ha egy gráf P₄-, C₄- és 2K₂-mentes, komplementere is az lesz.

Sablon:Harvtxt 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

• Sablon:Fordítás

Jegyzetek

• Sablon:Citation.
• Sablon:Citation. 2nd edition, Annals of Discrete Mathematics, 57, Elsevier, 2004.
• Sablon:Citation.
• Sablon:Citation.

További információk

• Threshold graphs, Information System on Graph Classes and their Inclusions.