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.

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: Sablon:Harvtxt, Sablon:Harvtxt, Sablon:Harvtxt és Sablon:Harvtxt. A szakirodalomban még a következő elnevezéseik is előfordulnak: D*-gráfok,Sablon:Sfnp örökletes Dacey-gráfok (James C. Dacey Jr. ortomoduláris hálókon végzett kapcsolódó munkája után),Sablon:Sfnp és 2-paritásgráfok.Sablon:Sfnp 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:

az egy csúcsból álló gráf kográf;
ha $G$ kográf, akkor a komplementer gráfja, $\overline{G}$ is az;
ha $G$ és $H$ kográfok, akkor diszjunkt uniójuk, $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.Sablon:Sfnp 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 $G \cup H$ diszjunkt uniót képezzük, majd behúzunk minden lehetséges élt a $G$ és $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 $v_{1}, v_{2}, v_{3}, v_{4}$ -gyel, igaz, hogy ha ${v_{1}, v_{2}}, {v_{2}, v_{3}}$ és ${v_{3}, v_{4}}$ a gráf élei, akkor a ${v_{1}, v_{3}}, {v_{1}, v_{4}}$ és ${v_{2}, v_{4}}$ közül legalább egynek szintén élnek kell lennie.Sablon:Sfnp
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.Sablon:Sfnp
A kográf egy soros-párhuzamos részbenrendezés összehasonlíthatósági gráfja.Sablon:Sfnp
A kográf egy szétválasztható permutáció permutációgráfja.Sablon:Sfnp
A kográf olyan gráf, melynek minimális húrgráffá kiegészítései triviálisan perfekt gráfok.Sablon:Sfnp
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.Sablon:Sfnp
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

A kográfok egyedi fa-reprezentációval rendelkeznek.Sablon:Sfnp 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ű.Sablon:Sfnp

Példa

A következő példa bemutatja a $G_{5}$ kográf előállítását a hozzá tartozó $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
$G_{1} = ∙$			$T_{1}$
$G_{2} = G_{1} \cup G_{1}$			$T_{2}$
$G_{3} = G_{1} \times G_{2}$			$T_{3}$
$G_{4} = G_{3} \cup G_{3}$			$T_{4}$
$G_{5} = G_{1} \times G_{4}$			$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ó,Sablon:Sfnp partíció finomítása, Sablon:Sfnp lexikografikus szélességi bejárás (LexBFS) Sablon:Sfnp vagy split dekompozíció.Sablon:Sfnp 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^[1] és a Hamilton-kör létezése, melyek a kográf-fa segítségével mind csak lineáris idejűek.Sablon:Sfnp 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ő.Sablon:Sfnp

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).Sablon:Sfnp 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,Sablon:Sfnp hogy k él szerkesztésével átalakítható-e kográffá, O^*(4,612^k) időben eldönthető.Sablon:Sfnp 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ó.Sablon:Sfnp

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.Sablon:Sfnp

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).Sablon:Sfnp 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.Sablon:Sfnp

A kográfok fontos szerepet játszanak a read-once függvényeket felismerő algoritmusokban.Sablon:Sfnp

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

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 Sablon:Math teljes gráf kográf, melynek kográf-fája egy 1-címkéjű csomópontból és Sablon:Mvar levélből áll. Hasonlóan, minden Sablon:Mvar 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 Sablon:Mvar, a másik alatt Sablon:Mvar 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ó. Sablon:Sfnp

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.Sablon:Sfnp

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.Sablon:Sfnp

Jegyzetek

Sablon:Jegyzetek

Források

További információk

↑ 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. – Sablon:DOI

[1] 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. – Sablon:DOI

[1]

Kográf

Tartalomjegyzék

Definíció

Rekurzív előállítása

Egyéb karakterizációk

Kográf-fák

Példa

Számítási jellemzőik

Leszámlálásuk

Kapcsolódó gráfcsaládok

Alosztályaik

Bővebb halmazok

Jegyzetek

Források

További információk

Navigációs menü

Kográf

Definíció

Rekurzív előállítása

Egyéb karakterizációk

Kográf-fák

Példa

Számítási jellemzőik

Leszámlálásuk

Kapcsolódó gráfcsaládok

Alosztályaik

Bővebb halmazok

Jegyzetek

Források

További információk

Navigációs menü

Keresés