Ugrás a tartalomhoz

Kográf

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából
AT(13,4) Turán-gráf, példa egy kográfra

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.

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ása

[szerkeszté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ók

[szerkeszté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ák

[szerkeszté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élda

[szerkeszté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őik

[szerkeszté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ó,[9] partíció finomítása, [10] lexikografikus szélességi bejárás (LexBFS) [11] vagy split dekompozíció.[12] 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[13] é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ő.[14]

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).[15] Annak eldöntése, hogy egy gráf k él törlésével átalakítható-e kográffá O*(2,415k) időben,[16] hogy k él szerkesztésével átalakítható-e kográffá, O*(4,612k) időben eldönthető.[17] 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ó.[16]

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).[18] 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.[19]

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

Leszámlálásuk

[szerkeszté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ádok

[szerkesztés]

Alosztályaik

[szerkeszté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ó. [21]

Bővebb halmazok

[szerkeszté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.[22]

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.[21]

Jegyzetek

[szerkesztés]

Források

[szerkesztés]

További információk

[szerkesztés]