Split gráf

A Wikipédiából, a szabad enciklopédiából
(Hasított gráf szócikkből átirányítva)
Egy split gráf, klikkbe és független csúcshalmazba particionálva.

A matematika, azon belül a gráfelmélet területén egy split gráf, hasított gráf vagy kettéhasadó gráf (split graph) olyan gráf, melynek csúcsai egy klikkbe (teljes részgráfba) és egy független csúcshalmazba particionálhatók. Elsőként Földes and Hammer (1977a, 1977b) tanulmányozta őket, tőlük függetlenül Tyshkevich and Chernyak (1979) is bevezette a fogalmat.[1]

Egy split gráfnak lehet egynél több lehetséges klikkre és független halmazra való particionálása is; például az a–b–c útgráf egy split gráf, melynek csúcsai háromféleképpen particionálhatók:

  1. az {a,b} klikk és a {c}
  2. a {b,c} klikk és az {a} független halmaz
  3. a {b} klikk és az {a,c} független halmaz

A split gráfok tiltott részgráfjaik alapján jellemezhetők: egy gráf pontosan akkor split gráf, ha egyetlen feszített részgráfja sem 4 vagy 5 csúcsú kör, vagy diszjunkt élpár (ami a 4-kör komplementere).[2]

Más gráfcsaládokkal való kapcsolata[szerkesztés]

A definíció alapján a split gráfok nyilvánvalóan zártak a komplementerképzés műveletére nézve.[3] Egy másik karakterizáció szerint a split gráfok azok a merev körű gráfok, melyek komplementere is merev körű.[4] Ahogy a merev körű gráfok a fák al-fáinak metszetgráfjai, ugyanígy a split gráfok csillaggráfok al-csillagjainak metszetgráfjai.[5] Csaknem minden merev körű gráf splitgráf; ahogy n tart végtelenhez, az n-csúcsú merev körű gráfok között a split gráfok aránya egyhez tart.[6]

Mivel a merev körű gráfok perfektek, ezért a split gráfok is azok. A dupla split gráfok[7] családjának tagjait split gráfokból lehet előállítani minden csúcs megduplázásával (így a klikk antipárosítást feszít ki, a független csúcshalmaz pedig párosítást); a dupla split gráfok a perfekt gráfok öt alaposztályának egyike, melyekből az összes többi perfekt gráf előállítható, ahogy az megjelenik (Chudnovsky et al. 2006) erős perfektgráf-tétel-bizonyításában.

Ha egy gráf egyszerre split és intervallumgráf, akkor komplementere egyszerre split és összehasonlíthatósági gráf, ugyanez igaz megfordítva. A split összehasonlíthatósági gráfok és így a split intervallumgráfok ezért jellemezhetőek három tiltott feszített részgráfjukkal.[8] A split kográfok pontosan megegyeznek a küszöbgráfokkal, a split permutációgráfok pedig pontosan azok az intervallumgráfok, melyek komplementerei is intervallumgráfok.[9] A split gráfok komplementer kromatikus száma 2.

Algoritmikus problémák[szerkesztés]

Tekintsük a G split gráfot, melynek létezik egy C klikkbe és I független csúcshalmazba particionálása. Ekkor a split gráf minden maximális klikkje vagy C-vel egyezik meg, vagy egy I-beli csúcs szomszédságával. Ezért a split gráfokban könnyű feladat meghatározni a maximális klikket, illetve komplementer feladatként a maximális független halmazt. Tetszőleges split gráfban a következő három lehetőség valamelyikének igaznak kell lennie:[10]

  1. Létezik olyan x csúcs I-ben, hogy C ∪ {x} teljes. Ebben az esetben C ∪ {x} egy maximális klikk, I pedig maximális független halmaz.
  2. Létezik x csúcs C-ben, hogy I ∪ {x} független. Ebben az esetben I ∪ {x} maximális független halmaz és C maximális klikk.
  3. C maximális klikk és I maximális független halmaz. Ebben az esetben G-nek a (C,I) klikkre és független halmazra felbontása egyedi, C a maximális klikk és I a maximális független halmaz.

Néhány optimalizálási probléma, ami általánosabb gráfcsaládokon NP-teljes – köztük a gráfszínezés – hasonlóan egyszerűsödik split gráfokat tekintve. A Hamilton-kör keresése továbbra is NP-teljes, még olyan split gráfokra is, melyek erősen merev körűek.[11] Ismert továbbá, hogy a minimális domináló csúcshalmaz problémája split gráfokra is NP-teljes.[12]

Fokszámsorozatok[szerkesztés]

A split gráfok figyelemre méltó sajátossága, hogy pusztán a gráf fokszámsorozata alapján felismerhetők. Legyen a G gráf fokszámsorozata d1 ≥ d2 ≥ ... ≥ dn, és m a legnagyobb i érték, amire di ≥ i − 1. Ekkor G pontosan akkor split gráf, ha

Ha ez az eset áll fenn, akkor a legnagyobb fokszámú m csúcs maximális klikket alkot G-ben, a maradék csúcsok pedig független csúcshalmazt.[13]

Split gráfok leszámlálása[szerkesztés]

(Royle 2000) megmutatta, hogy az n-csúcsú split gráfok és bizonyos Sperner-rendszerek között bijekció létesíthető. Ezt a tényt kihasználva meghatározta az n csúcsú (nem izomorf) split gráfok számát. Kis n értékekre, n = 1-től kezdve, ezek:

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... (A048194 sorozat az OEIS-ben).

Ezt a gráfleszámlálási eredményt korábban (Tyshkevich & Chernyak 1990) is bizonyította.

Fordítás[szerkesztés]

  • Ez a szócikk részben vagy egészben a Split 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[szerkesztés]

  1. ↑ (Földes & Hammer 1977a) általánosabb definíciója szerint a split gráfoknak nevezett gráfok közé tartoznak a páros gráfok is (tehát a két független csúcshalmazba particionálható gráfok), továbbá a páros gráfok komplementerei (tehát a két klikkbe particionálható gráfok) is. (Földes & Hammer 1977b) az itteni definíciót használja, amit a későbbi irodalom is követ, például: (Brandstädt, Le & Spinrad 1999), Definition 3.2.3, p.41.
  2. ↑ (Földes & Hammer 1977a); (Golumbic 1980), Theorem 6.3, p. 151.
  3. ↑ (Golumbic 1980), Theorem 6.1, p. 150.
  4. ↑ (Földes & Hammer 1977a); (Golumbic 1980), Theorem 6.3, p. 151; (Brandstädt, Le & Spinrad 1999), Theorem 3.2.3, p. 41.
  5. ↑ (McMorris & Shier 1983); (Voss 1985); (Brandstädt, Le & Spinrad 1999), Theorem 4.4.2, p. 52.
  6. ↑ (Bender, Richmond & Wormald 1985).
  7. ↑ Lovásznál[halott link] „kettőzött kettéhasadó gráfok”
  8. ↑ (Földes & Hammer 1977b); (Golumbic 1980), Theorem 9.7, page 212.
  9. ↑ (Brandstädt, Le & Spinrad 1999), Corollary 7.1.1, p. 106, and Theorem 7.1.2, p. 107.
  10. ↑ (Hammer & Simeone 1981); (Golumbic 1980), Theorem 6.2, p. 150.
  11. ↑ (Müller 1996)
  12. ↑ (Bertossi 1984)
  13. ↑ (Hammer & Simeone 1981); (Tyshkevich 1980); (Tyshkevich, Melnikow & Kotov 1981); (Golumbic 1980), Theorem 6.7 and Corollary 6.8, p. 154; (Brandstädt, Le & Spinrad 1999), Theorem 13.3.2, p. 203. (Merris 2003) tovább vizsgálja a split gráfok fokszámsorozatait.

Kapcsolódó irodalom[szerkesztés]

  • Martin Charles Golumbic, "Algorithmic Graph Theory and Perfect Graphs" c. könyvének egy teljes fejezete a split gráfokat tárgyalja.
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Split_gráf&oldid=26250669”