Kográf

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 P₄-mentes gráf olyan gráf, ami a K₁ 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 K₁-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ó

Rekurzív előállítása

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 ${\displaystyle G}$ kográf, akkor a komplementer gráfja, ${\displaystyle {\overline {G}}}$ is az;
3. ha ${\displaystyle G}$ és ${\displaystyle H}$ kográfok, akkor diszjunkt uniójuk, ${\displaystyle G\cup H}$ 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 ${\displaystyle G\cup H}$ diszjunkt uniót képezzük, majd behúzunk minden lehetséges élt a ${\displaystyle G}$ és ${\displaystyle H}$ csúcsai között.

Egyéb karakterizációk

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

• A kográfok azok a gráfok, melyek nem tartalmazzák feszített részgráfként a P₄-et, azaz a 4 csúcs közötti (3 él hosszúságú) útgráfot (nincs bennük 3 él hosszú feszített út). Tehát egy gráf pontosan akkor kográf, ha bármely négy csúcsára, jelöljük őket ${\displaystyle v_{1},v_{2},v_{3},v_{4}}$-gyel, igaz, hogy ha ${\displaystyle \{v_{1},v_{2}\},\{v_{2},v_{3}\}}$ és ${\displaystyle \{v_{3},v_{4}\}}$ a gráf élei, akkor a ${\displaystyle \{v_{1},v_{3}\},\{v_{1},v_{4}\}}$ és ${\displaystyle \{v_{2},v_{4}\}}$ közül legalább egynek szintén élnek kell lennie.^[4]
• A kográf olyan gráf, melynek feszített részgráfjaiban bármely maximális klikk bármely maximális független csúcshalmazt egyetlen csúcsban metsz.
• A kográf olyan gráf, melyben bármely nemtriviális feszített részgráf csúcsai közül legalább kettő ugyanabban a szomszédságban található.
• A kográf olyan gráf, melynek minden összefüggő feszített részgráfjának nem összefüggő a komplementere.
• A kográf olyan gráf, melynek minden összefüggő feszített részgráfjának legfeljebb 2 az átmérője.
• A kográf olyan gráf, melynek minden összefüggő komponense legfeljebb 2 átmérőjű távolság-örökletes gráf.
• A kográf olyan gráf, melynek klikkszélessége legfeljebb 2.^[5]
• A kográf egy soros-párhuzamos részbenrendezés összehasonlíthatósági gráfja.^[1]
• A kográf egy szétválasztható permutáció permutációgráfja.^[6]
• A kográf olyan gráf, melynek minimális húrgráffá kiegészítései triviálisan perfekt gráfok.^[7]
• A kográf örökletesen jól színezhető gráf, tehát olyan gráf, melynek minden feszített részgráfjának mohó színezése optimális.^[8]
• A kográfok pontosan azok a gráfok, melyekben a csúcsok minden rendezése perfekt rendezés, mivel a P₄ feszített részgráfok hiánya azt jelenti, hogy semmilyen sorrendben nincs akadálya a perfekt rendezésnek.

Kográf-fák

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

A következő példa bemutatja a ${\displaystyle G_{5}}$ kográf előállítását a hozzá tartozó ${\displaystyle T_{5}}$ kográf-fával együtt:

Kográf	A kográf ábrázolása	A kográf-fa illusztrációja	Kográf-fa
${\displaystyle G_{1}=\bullet }$			${\displaystyle T_{1}}$
${\displaystyle G_{2}=G_{1}\cup G_{1}}$			${\displaystyle T_{2}}$
${\displaystyle G_{3}=G_{1}\times G_{2}}$			${\displaystyle T_{3}}$
${\displaystyle G_{4}=G_{3}\cup G_{3}}$			${\displaystyle T_{4}}$
${\displaystyle G_{5}=G_{1}\times G_{4}}$			${\displaystyle T_{5}}$

Számítási jellemzőik

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 (MSO₁) 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,415^k) időben,^[16] hogy k él szerkesztésével átalakítható-e kográffá, O^*(4,612^k) 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,30^k) 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

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

Alosztályaik

Minden K_n 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 K_a,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

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 P₄-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

1. Jung (1978).
2. Sumner (1974).
3. Burlet & Uhry (1984).
4. 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. Nastos & Gao (2010).
17. Liu et al. (2012).
18. Damaschke (1990).
19. Damaschke (1991).
20. Golumbic & Gurvich (2011).
21. Brandstädt, Le & Spinrad (1999).
22. Berge & Duchet (1984).

Források

• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .

További információk

• Weisstein, Eric W.: Cograph (angol nyelven). Wolfram MathWorld