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 tanulmányozta őket, tőlük függetlenül is bevezette a fogalmat. á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. az itteni definíciót használja, amit a későbbi irodalom is követ, például: , Definition 3.2.3, p.41.

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: az {a,b} klikk és a {c} a {b,c} klikk és az {a} független halmaz 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).; , Theorem 6.3, p. 151.

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., Theorem 6.1, p. 150. Egy másik karakterizáció szerint a split gráfok azok a merev körű gráfok, melyek komplementere is merev körű.; , Theorem 6.3, p. 151; , Theorem 3.2.3, p. 41. 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.; ; , Theorem 4.4.2, p. 52. 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..

Mivel a merev körű gráfok perfektek, ezért a split gráfok is azok. A dupla split gráfokLovásznál „kettőzött kettéhasadó gráfok” 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 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.; , Theorem 9.7, page 212. 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., Corollary 7.1.1, p. 106, and Theorem 7.1.2, p. 107. 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:; , Theorem 6.2, p. 150. 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. 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. 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. Ismert továbbá, hogy a minimális domináló csúcshalmaz problémája split gráfokra is NP-teljes.

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

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.; ; ; , Theorem 6.7 and Corollary 6.8, p. 154; , Theorem 13.3.2, p. 203. tovább vizsgálja a split gráfok fokszámsorozatait.

Split gráfok leszámlálása 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, ... . Ezt a gráfleszámlálási eredményt korábban is bizonyította.

Jegyzetek

. . . . . . . . . . . .

. . Translated as "Yet another method of enumerating unmarked combinatorial objects" (1990), Mathematical notes of the Academy of Sciences of the USSR 48 (6): 1239–1245, . . .

Fordítás

További információk Martin Charles Golumbic, "Algorithmic Graph Theory and Perfect Graphs" c. könyvének egy teljes fejezete a split gráfokat tárgyalja

Kategória:Gráfcsaládok Kategória:Metszetgráfok alapján meghatározott gráfosztályok Kategória:Perfekt gráfok