Kográf

olyan gráf, mely megalkotható különálló csúcsokból komplementer és diszjunkt unió műveletek elvégzésével

A matematika, azon belül a gráfelmélet területén egy kográf (cograph), komplementer-redukálható gráf (complement-reducible graph) vagy P4-mentes gráf olyan gráf, ami a K1 egyetlen csúcsból álló gráfból kiindulva előállítható a komplementerképzés és diszjunkt unió gráfműveletek segítségével. Úgy is fogalmazhatunk, hogy a komplementer-redukálható gráfok családja a legkisebb gráfcsalád, ami tartalmazza a K1-et és a komplementerképzés, valamint a diszjunkt unió gráfműveleteire zárt.

AT(13,4) Turán-gráf, példa egy kográfra

A kográfokat az 1970-es évek során egymástól függetlenül több matematikus is leírta; a kográfokról szóló legkorábbi feljegyzések közé tartoznak: (Jung 1978), (Lerchs 1971), (Seinsche 1974) és (Sumner 1974). A szakirodalomban még a következő elnevezéseik is előfordulnak: D*-gráfok,[1] örökletes Dacey-gráfok (James C. Dacey Jr. ortomoduláris hálókon végzett kapcsolódó munkája után),[2] és 2-paritásgráfok.[3] Egyszerű, a diszjunkt unió és a komplementerképzés műveletein alapuló szerkezetük címkézett fa segítségével tömören ábrázolható, és hatékony algoritmusokkal oldhatók meg rajtuk olyan problémák (pl. a maximális klikk megkeresése), melyek általánosabb gráfosztályokon nehezebbek.

A kográfok speciális esetei közé tartoznak a teljes gráfok, a teljes páros gráfok, a klasztergráfok és a küszöbgráfok. Maguk a kográfok a távolság-örökletes gráfok, az összehasonlíthatósági gráfok és a perfekt gráfok speciális esetei.

DefinícióSzerkesztés

Rekurzív előállításaSzerkesztés

Bármely komplementer-redukálható gráf előállítható a következő szabályok alapján:

  1. az egy csúcsból álló gráf kográf;
  2. ha   kográf, akkor a komplementer gráfja,   is az;
  3. ha   és   kográfok, akkor diszjunkt uniójuk,   is az.

A komplementer-redukálható gráfok éppen azok a gráfok, melyek az egy csúcsból álló gráfból kiindulva, a fenti műveletek segítségével előállíthatók.[4] Alternatív megoldásként a komplementerképzés művelete helyett alkalmazható az összekapcsolás művelet, melynek során először a   diszjunkt uniót képezzük, majd behúzunk minden lehetséges élt a   és   csúcsai között.

Egyéb karakterizációkSzerkesztés

A komplementer-redukálható gráfok számos egyéb karakterizációja létezik. Néhány ezek közül:

Kográf-fákSzerkesztés

 
Egy kográf-fa és a hozzátartozó kográf. A kográf minden (u,v) élének színe megegyezik az u és v kográf-fabeli legközelebbi közös ősének színével.

A kográfok egyedi fa-reprezentációval rendelkeznek.[9] Ez a reprezentáció a kográf-fa (cotree), ami egy olyan fa, aminek a belső csomópontjai a 0 és 1 számokkal vannak megcímkézve. Minden T kográf-fa meghatároz egy olyan G kográfot, melynek csúcsai megegyeznek a T leveleivel, és T bármely csomópontjából kiinduló részfa megfelel G-ben a csomópontból leszármazó levelek által a következő módon meghatározott feszített részgráfnak:

  • Az egyetlen levélből álló részfa megfelel az egyetlen csúcsból álló feszített részgráfnak.
  • A 0 címkéjű csomópont alatti részfa megfelel a csomópont gyerekei által meghatározott részgráfok uniójának.
  • Az 1 címkéjű csomópont alatti részfa megfelel a csomópont gyerekei által meghatározott részgráfok összekapcsolásának (join művelet). Ezzel megegyezik, ha a részgráfoknak egyenként vesszük a komplementerét, ezek unióját képezzük, majd a végeredménynek újra a komplementerét vesszük.

A kográf-fa által meghatározott kográf leírásának egyenértékű módja a következő: két csúcs pontosan akkor van éllel összekötve, ha a nekik megfelelő levelek legközelebbi közös őse 1-gyel van címkézve. Megfordítva, minden kográf leírható ilyen módon egy kográf-fával. Ha megköveteljük, hogy bármely gyökér és levél közötti úton a címkék 0 és 1 között váltakozzanak, a reprezentáció egyértelmű.[4]

PéldaSzerkesztés

A következő példa bemutatja a   kográf előállítását a hozzá tartozó   kográf-fával együtt:

Kográf A kográf ábrázolása A kográf-fa illusztrációja Kográf-fa
       
       
       
       
       

Számítási jellemzőikSzerkesztés

A kográfok lineáris időben felismerhetők, és létrehozható a kográf-fa reprezentáció, a következő módszerekkel: moduláris dekompozíció,[10] partíció finomítása, [11] lexikografikus szélességi bejárás (LexBFS) [12] vagy split dekompozíció.[13] Ha egyszer a kográf-fa reprezentáció elkészült, számos gráfprobléma megoldható a kográf-fán alulról fölfelé végzett egyszerű műveletek segítségével.

Például egy kográf maximális elemszámú klikkjének megkereséséhez alulról fölfelé ki kell számolni minden a kográf-fa minden részfájának megfelelő részgráf maximális elemszámú klikkjét. A 0-val címkézett csomópontok esetében a maximális elemszámú klikk megegyezik a gyermek csomópontok maximális klikkjével. Az 1-gyel címkézett csomópontok maximális elemszámú klikkje a gyermek csomópontok klikkjeinek uniója, mérete pedig a gyermekek klikkméreteinek összegével egyezik meg. Tehát a kográf-fa csomópontjaiban tárolt értékek váltakozva maximálásával és összegzésével kiszámítható a maximális elemszámú klikk mérete, a maximalizálás és unióképzés műveleteinek váltogatásával pedig meg is konstruálható a maximális elemszámú klikk. Hasonló alulról fölfelé történő számításokkal meghatározható a maximális elemszámú független csúcshalmaz, kromatikus szám, maximális klikkfedés[14] és a Hamilton-kör létezése, melyek a kográf-fa segítségével mind csak lineáris idejűek.[4] Mivel a kográfok klikkszélessége korlátos, a Courcelle-tétel felhasználásával a monadikus másodrendű gráflogika (MSO1) bármely tulajdonsága lineáris időben tesztelhető.[15]

Annak problémája, hogy adott gráf k csúcs és/vagyt él távolságon belül van-e egy kográftól, rögzített paraméter mellett kezelhető (fixed-parameter tractable).[16] Annak eldöntése, hogy egy gráf k él törlésével átalakítható-e kográffá O*(2,415k) időben,[17] hogy k él szerkesztésével átalakítható-e kográffá, O*(4,612k) időben eldönthető.[18] Ha egy gráf legnagyobb feszített részgráf-kográfja előállítható k csúcs törlésével, akkor O*(3,30k) időben meg is található.[17]

Két kográf pontosan akkor izomorf, ha kográf-fáik (kanonikus alakjukban, amikor szomszédos csúcsok nem kaphatják ugyanazt a címkét) izomorfak. Emiatt az ekvivalencia miatt lineáris időben eldönthető, hogy két kográf izomorf-e, csak meg kell konstruálni a kográf-fáikat és a címkézett fákra lineáris idejű izomorfizmus-tesztet futtatni.[4]

Ha H egy G kográf feszített részgráfja, akkor H maga is kográf; H kográf-fája előállítható a G kográf-fájából néhány levél eltávolításával, majd az egyetlen gyerekkel rendelkező csomópontok elnyomásával. A Kruskal-tételből következik, hogy a feszített részgráfnak levés relációja a kográfokon „jó előrendezés” (well-quasi-ordering).[19] Tehát ha a kográfok egy alosztálya (például a síkbarajzolható kográfok) zárt a feszített részgráf műveletre, akkor véges számú tiltott feszített részgráfja lehet. Számításilag ez azt jelenti, hogy az alosztályba tartozás adott esetben lineárisan tesztelhető, a gráf kográf-fáján a tiltott feszített részgráfok alulról fölfelé történő keresésével. Ha azonban mindkét kográf mérete variábilis, akkor annak vizsgálata, hogy az egyik a másiknak feszített részgráfja-e, NP-teljes probléma.[20]

A kográfok fontos szerepet játszanak a read-once függvényeket felismerő algoritmusokban.[21]

LeszámlálásukSzerkesztés

Az n csúcsú, összefüggő kográfok száma, n = 1, 2, 3-ra:

1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, ... (A000669 sorozat az OEIS-ben)

Az n > 1 esetekben ugyanennyi nem összefüggő kográf létezik, mivel mindegyiküknek pontosan egy komplementere összefüggő.

Kapcsolódó gráfcsaládokSzerkesztés

AlosztályaikSzerkesztés

Minden Kn teljes gráf kográf, melynek kográf-fája egy 1-címkéjű csomópontból és n levélből áll. Hasonlóan, minden Ka,b teljes páros gráf is kográf, melynek kográf-fája gyökerében 1-címkéjű csomópont van, két 0-címkéjű gyermekkel, melyek közül az egyik alatt a, a másik alatt b levél található. A Turán-gráf előállítható azonos méretű független csúcshalmazokon végzett összekapcsolás művelettel; ezért szintén kográf, melynek kográf-fája gyökerében 1-címkéjű csomópont van, mely alatt minden független csúcshalmazhoz egy-egy 0-címkéjű csomópont található.

A küszöbgráfok szintén kográfok. A küszöbgráf megkapható 1-1 olyan csúcs hozzáadásával, mely vagy az összes addigi csúcshoz kapcsolódik, vagy egyikhez sem; ezen műveletek mindegyike diszjunkt unió vagy összekapcsolás, melyekkel a kográf-fa előállítható. [22]

Bővebb halmazokSzerkesztés

A kográfok azon karakterizációja, miszerint minden klikkjüknek és maximális független csúcshalmazuknak a metszete nem üres, az erősen perfekt gráf definíciójának erősebb változata; az erősen perfekt gráfokban elegendő, ha minden feszített részgráf tartalmaz olyan független csúcshalmazt, ami metszi a maximális klikkeket. A kográfokban az összes maximális független csúcshalmaz metszi az összes maximális klikket, ezért minden kográf erősen perfekt.[23]

Mivel a kográfok P4-mentesek, ezért perfekt rendezhetőek. Valójában a kográfok csúcsainak minden rendezése perfekt rendezés, amiből következik, hogy a maximális klikkeket és a minimális színezéseket lineáris időben lehet bennük keresni mohó algoritmussal, kográf-fára felbontás nélkül is.

Minden kográf egyben távolság-örökletes gráf, ami azt jelenti, hogy a kográf minden feszített útja egy legrövidebb út. A kográfok egyik karakterizációja szerint azok a távolság-örökletes gráfok, melyek minden komponensének legfeljebb kettő az átmérője. Minden kográf egyben egy soros-párhuzamos részbenrendezés hasonlítási gráfja is, ami úgy kapható meg, hogy a kográfot előállító diszjunkt unió és összekapcsolás műveletek helyett a részben rendezésen diszjunkt unió és lexikografikus összeg műveletet alkalmazunk. Mivel az erősen perfekt gráfok, perfekt rendezhető gráfok, távolság-örökletes gráfok és a hasonlítási gráfok mind perfektek, ezért a kográfok is mind perfekt gráfok.[22]

JegyzetekSzerkesztés

  1. a b Jung (1978).
  2. Sumner (1974).
  3. Burlet & Uhry (1984).
  4. a b c d e Corneil, Lerchs & Stewart Burlingham (1981).
  5. Courcelle & Olariu (2000).
  6. Bose, Buss & Lubiw (1998).
  7. Parra & Scheffler (1997).
  8. Christen & Selkow (1979).
  9. Corneil, Perl & Stewart (1985).
  10. Habib & Paul (2005).
  11. Bretscher et al. (2008).
  12. Gioan & Paul (2012).
  13. The maximum clique cover of a graph G = (V, E) is a set V' ⊆ V with the property that each maximum clique of G contains some vertex in the cover. – doi:10.1186/1471-2105-13-S10-S5
  14. Courcelle, Makowsky & Rotics (2000).
  15. Cai (1996).
  16. a b Nastos & Gao (2010).
  17. Liu et al. (2012).
  18. Damaschke (1990).
  19. Damaschke (1991).
  20. Golumbic & Gurvich (2011).
  21. a b Brandstädt, Le & Spinrad (1999).
  22. Berge & Duchet (1984).

Forráshivatkozás-hiba: Olyan <ref> címke lett lett definiálva egy <references> címkében, amely csoportattribútuma („”) nem szerepel a szöveg korábbi részében.

További információkSzerkesztés