Split gráf

Innen: testwiki
Ugrás a navigációhoz Ugrás a kereséshez
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 Sablon:Harvs tanulmányozta őket, tőlük függetlenül Sablon:Harvs 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

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

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

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

∑i=1mdi=m(m−1)+∑i=m+1ndi.

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

Sablon:Harvtxt 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, ... Sablon:OEIS.

Ezt a gráfleszámlálási eredményt korábban Sablon:Harvtxt is bizonyította.

Fordítás

Jegyzetek

Sablon:Reflist

Sablon:Refbegin

Sablon:Refend

Kapcsolódó irodalom

  • Martin Charles Golumbic, "Algorithmic Graph Theory and Perfect Graphs" c. könyvének egy teljes fejezete a split gráfokat tárgyalja.
  1. ↑ Sablon:Harvtxt á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. Sablon:Harvtxt az itteni definíciót használja, amit a későbbi irodalom is követ, például: Sablon:Harvtxt, Definition 3.2.3, p.41.
  2. ↑ Sablon:Harvtxt; Sablon:Harvtxt, Theorem 6.3, p. 151.
  3. ↑ Sablon:Harvtxt, Theorem 6.1, p. 150.
  4. ↑ Sablon:Harvtxt; Sablon:Harvtxt, Theorem 6.3, p. 151; Sablon:Harvtxt, Theorem 3.2.3, p. 41.
  5. ↑ Sablon:Harvtxt; Sablon:Harvtxt; Sablon:Harvtxt, Theorem 4.4.2, p. 52.
  6. ↑ Sablon:Harvtxt.
  7. ↑ LovásználSablon:Halott link „kettőzött kettéhasadó gráfok”
  8. ↑ Sablon:Harvtxt; Sablon:Harvtxt, Theorem 9.7, page 212.
  9. ↑ Sablon:Harvtxt, Corollary 7.1.1, p. 106, and Theorem 7.1.2, p. 107.
  10. ↑ Sablon:Harvtxt; Sablon:Harvtxt, Theorem 6.2, p. 150.
  11. ↑ Sablon:Harvtxt
  12. ↑ Sablon:Harvtxt
  13. ↑ Sablon:Harvtxt; Sablon:Harvtxt; Sablon:Harvtxt; Sablon:Harvtxt, Theorem 6.7 and Corollary 6.8, p. 154; Sablon:Harvtxt, Theorem 13.3.2, p. 203. Sablon:Harvtxt tovább vizsgálja a split gráfok fokszámsorozatait.
A lap eredeti címe: „https://hu.wiki.beta.math.wmflabs.org/w/index.php?title=Split_gráf&oldid=3686”