Küszöbgráf

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.

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 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 $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)\leq 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. $\epsilon$ 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 $\epsilon uuj$ karakterlánc a három ágú csillaggráfot írja le, míg az $\epsilon uj$ a három csúcsú útgráfot. Az ábrán látható gráf így fejezhető ki: $\epsilon 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.

(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

• Egység-intervallumgráf
• Soros-párhuzamos gráf

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

• Chvátal, Václav & Hammer, Peter L. (1977), "Aggregation of inequalities in integer programming", in Hammer, P. L.; Johnson, E. L. & Korte, B. H. et al., Studies in Integer Programming (Proc. Worksh. Bonn 1975), vol. 1, Annals of Discrete Mathematics, Amsterdam: North-Holland, pp. 145–162.
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, New York: Academic Press. 2nd edition, Annals of Discrete Mathematics, 57, Elsevier, 2004.
• Heggernes, Pinar & Kratsch, Dieter (2007), "Linear-time certifying recognition algorithms and forbidden induced subgraphs", Nordic Journal of Computing 14 (1-2): 87–108 (2008), <http://www.ii.uib.no/~pinar/certifying-NJC.pdf>.
• Mahadev, N. V. R. & Peled, Uri N. (1995), Threshold Graphs and Related Topics, Elsevier.

További információk

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