Jaettu kaavio

Graafiteoriassa jaettu graafi on graafi, jonka kärjet voidaan jakaa klikiksi ja itsenäiseksi joukoksi . Split-kaavioita tutkivat ensin Földes ja Hammer [1] [2] , ja Tyszkiewicz ja Czernyak esittelivät ne itsenäisesti [3] [4] .

Jaetulla graafilla voi olla useita hajotuksia klikkia kohti ja riippumaton joukko. Siten polku a - b - c on jaettu ja voidaan jakaa kolmella eri tavalla:

  1. klikki { a , b } ja riippumaton joukko { c }
  2. klikki { b , c } ja riippumaton joukko { a }
  3. klikki { b } ja riippumaton joukko { a , c }

Jaettavat graafit voidaan luonnehtia niiden kiellettyjen aligraafien avulla - graafi jaetaan silloin ja vain, jos mikään luotu osagraafi ei ole sykli , jossa on neljä tai viisi kärkeä, eikä myöskään ole irrotettuja pisteparia (eli syklin komplementtia). 4 pisteestä) [5 ] [6] .

Suhde muihin kaavioperheisiin

Määritelmän mukaan jaettujen graafien luokka on suljettu komplementtioperaation suhteen [7] . Toinen komplementtia sisältävien jaettujen graafien ominaisuus on sointukuvaajat , joiden komplementit ovat myös sointuja [8] . Koska sointukuvaajat ovat puun alipuiden leikkauskaavioita , jaetut graafit ovat eri tähtien alitähtien leikkauskaavioita [9] . Melkein kaikki sointukaaviot ovat jaettuja kaavioita. Toisin sanoen, koska n pyrkii äärettömään, n - pisteisten sointugraafien lukumäärän ja erotettavissa olevien graafien lukumäärän osamäärä on yksi [10] .

Koska sointukaaviot ovat täydellisiä , myös jaettavat kaaviot ovat täydellisiä. Kaksoisjaetut graafit , graafiperhe, joka on saatu jaetuista graafista kaksinkertaistamalla pisteiden lukumäärä (niin, että klikki antaa vastasaman - joukko reunoja, joiden välinen etäisyys on enintään 2, ja riippumattomasta joukosta tulee yhteensopivuus), näkyy yhtenä. täydellisten graafien viidestä pääluokasta, joista kaikki muut voidaan rakentaa tiukan täydellisen graafin lauseen todistamiseksi [11] .

Jos graafi on sekä jaettavissa että intervalli , niin sen komplementti on sekä jaettavissa että vertailukelpoinen graafi ja päinvastoin. Jaettavat vertailukelpoiset graafit ja siten jaettavat intervallikaaviot voidaan kuvata kolmen kielletyn aligraafin avulla [12] . Jaetut graafit ovat  täsmälleen kynnyskaavioita ja jaetut permutaatiokaaviot  ovat täsmälleen intervallikaavioita, joiden komplementit ovat myös intervalli [13] . Split-kaavioiden kokromaattinen luku on 2.

Maksimiklikki ja suurin riippumaton joukko

Olkoon G  jaettu graafi, joka on jaettu klikkiksi C ja itsenäiseksi joukoksi I . Tällöin mikä tahansa maksimiklikki jaetun graafin kohdalla joko osuu yhteen C :n kanssa tai on I :n kärjen ympäristö . Näin ollen jaetusta graafista on helppo löytää maksimiklikki ja lisäksi suurin riippumaton joukko . Kaikissa jaettavissa olevissa kaavioissa on oltava jokin seuraavista lauseista [14] :

  1. I :ssä on sellainen piste x , että C ∪ { x } on täydellinen. Tässä tapauksessa C ∪ { x } on maksimaalinen klikki ja I  on maksimaalinen riippumaton joukko.
  2. C :ssä on sellainen piste x , että I ∪ { x } on itsenäinen joukko. Tässä tapauksessa I ∪ { x } on maksimaalinen riippumaton joukko ja C  on maksimaalinen klikki.
  3. C on suurin klikki ja minä suurin itsenäinen joukko. Tässä tapauksessa G :llä on ainutlaatuinen hajoaminen ( C , I ) klikkiksi ja riippumattomaksi joukoksi, C on maksimiklikki ja I on maksimaalinen riippumaton joukko.

Jotkut muut optimointiongelmat, jotka ovat NP-täydellisiä yleisemmissä kaavioperheissä, mukaan lukien väritys , ratkaistaan ​​yksinkertaisesti jaetuilla kaavioilla.

Tutkintosarjat

Eräs jaetun graafin suurista ominaisuuksista on se, että ne voidaan tunnistaa puhtaasti niiden kärkiastesekvenssien perusteella . Olkoon d 1 ≥ d 2 ≥ … ≥ d n  graafin G kärkiasteiden sarja ja m i :  n suurin arvo, jolle d i ≥ i  - 1. Silloin G on jaettu graafi jos ja vain jos

Jos tämä on totta, niin m pisteitä, joilla on suurin aste, muodostavat maksimaalisen klikin G , ja loput pisteet itsenäisen joukon [15] .

Jaettujen kaavioiden laskeminen

Royle [16] osoitti, että jaetut graafit, joissa on n pistettä , vastaavat yhtä tietyissä Sperner-perheissä . Tätä tosiasiaa käyttäen hän löysi kaavan (ei-isomorfisten) split-graafien lukumäärälle, joissa on n kärkeä. Pienille n:n arvoille , alkaen n = 1, nämä luvut ovat

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... OEIS - sekvenssi A048194 .

Tyszkiewicz ja Chernyak ovat aiemmin todistaneet tämän luettelon [17] .

Muistiinpanot

  1. ↑ Földes, Hammer, 1977a .
  2. ↑ Földes, Hammer, 1977b .
  3. ↑ Tyshkevich, Chernyak, 1979 .
  4. ↑ Földes ja Hammer Földes, Hammer, 1977a antoi yleisemmän määritelmän, jossa graafit, joita he kutsuvat jaettaviksi, sisältävät myös kaksiosaiset graafit (eli kahdeksi itsenäiseksi joukoksi jaetut graafit) ja kaksiosaisten graafien komplementit (eli graafit, jotka voidaan hajottaa kahdeksi osaksi ). klikkit). Földer ja Hammer Földes, Hammer, 1977b antavat tässä annetun ja myöhemmässä kirjallisuudessa käytetyn määritelmän, esim. Brandstädt, Le ja Spinrad Brandstädt, Le, Spinrad, 1999 , määritelmä 3.2.3, s. 41
  5. ↑ Földes, Hammer, 1977a ; Golumbic, 1980 , Lause 6.3, s. 151.
  6. ↑ Pinar Heggernes, Dieter Kratsch. Lineaariaikaiset varmentavat tunnistusalgoritmit ja kielletyt indusoidut aligraafit // Nordic Journal of Computing. - 2007. - T. 14 .
  7. ↑ Golumbic, 1980 , Lause 6.1, s. 150.
  8. ↑ Földes, Hammer, 1977a ; Golumbic, 1980 , Lause 6.3, s. 151; Brandstädt, Le, Spinrad, 1999 , Lause 3.2.3, s. 41.
  9. ↑ McMorris, Shier, 1983 ; Voss, 1985 ; Brandstädt, Le, Spinrad, 1999 , Lause 4.4.2, s. 52.
  10. ↑ Bender, Richmond, Wormald, 1985 .
  11. ↑ Chudnovsky, Robertson, Seymour, Thomas, 2006 .
  12. ↑ Földes, Hammer, 1977b ; Golumbic, 1980 , Lause 9.7, s. 212.
  13. ↑ Brandstädt, Le, Spinrad, 1999 , Seuraus 7.1.1, s. 106 ja Lause 7.1.2, s. 107.
  14. ↑ Hammer, Simeone, 1981 ; Golumbic, 1980 , Lause 6.2, s. 150.
  15. ↑ Hammer, Simeone, 1981 ; Tyshkevich, 1980 ; Tyshkevich, Melnikov, Kotov, 1981 ; Golumbic, 1980 , Lause 6.7 ja seuraus 6.8, s. 154; Brandstädt, Le, Spinrad, 1999 , Lause 13.3.2, s. 203. Merris, 2003 jaetun graafin astesekvenssin lisäkäsittely.
  16. ↑ Royle, 2000 .
  17. ↑ Tyshkevich, Chernyak, 1990 .

Kirjallisuus

Lue lisää