Cograf

Graafiteoriassa cograph , tai lisäksi pelkistävä tai P 4 : stä vapaa graafi  on graafi , joka voidaan saada graafista, jolla on yksi kärki K 1 graafien yhteenlasku- ja yhdistämisoperaatioilla . Siten kopioperhe on pienin graafien luokka, joka sisältää K 1 :n ja on suljettu komplementin ja liiton suhteen.

Useat kirjailijat ovat löytäneet kopioita itsenäisesti 1970-luvulta lähtien. Varhaisimmat maininnat ovat Young [1] , Lerchs [2] , Zainsche [3] ja Sumner [4] . Näitä kaavioita kutsuttiin D*-grafeiksi [1] , perinnöllisiksi Dacey -grafeiksi (James C. Dacey Jr.:n ortomodulaarisia hiloja käsittelevän työn mukaan . Katso Sumner [4] ) ja kaavioiksi , joissa on kaksi Barletin ja Uryn jälkeläistä [ 5] .

Katso Brandstedtin, Lie ja Spinradin kirja [6] saadaksesi yksityiskohtaisempaa keskustelua kuvakirjoista, mukaan lukien tässä annetut tosiasiat.

Määritelmä ja kuvaus

Mikä tahansa kopio voidaan rakentaa noudattamalla seuraavia sääntöjä:

  1. Mikä tahansa graafin yksittäinen kärkipiste on kopio;
  2. Jos  on cograph, niin sen komplementti on myös cograph;
  3. Jos ja  ovat cographs, niin niiden erillinen liitto on myös cograph.

Useita muita kuvauksia kuvauksista voidaan antaa. Heidän keskuudessaan:

Kaikki täydelliset kaaviot , täydelliset kaksiosaiset graafit , kynnyskaaviot ja Turan-kaaviot ovat kopiokaavioita. Mikä tahansa kopiokuvaaja on etäisyydeltä peritty täydellinen vertailukelpoisuuskaavio .

Codetrees

Koodipuu  on puu, jonka sisäiset kärjet on merkitty 0:lla ja 1:llä. Mikä tahansa koodipuu T määrittelee pisteen G , jonka T : n lehdet ovat kärjet, ja alipuu, jonka juuret ovat T :ssä , vastaa G :ssä generoitua aligraafia, jonka määrittelee joukko jälkeläisiä lehtiä. tämä toppi:

Vastaava tapa muodostaa kopio enkooderista on se, että kaksi kärkeä yhdistetään reunalla, jos ja vain, jos vastaavien lehtien vähiten yhteinen esi -isä on merkitty 1. Käänteisesti mikä tahansa kopio voidaan esittää kooderilla tällä tavalla. Jos vaadimme, että kaikki otsikot kaikilla poluilla juuresta lehtiin vuorottelevat, tällainen esitys on ainutlaatuinen [7] .

Laskennalliset ominaisuudet

Kopografi voidaan tunnistaa lineaarisessa ajassa ja koodirepresentaatio voidaan rakentaa käyttämällä modulaarista hajotusta [10] , hajotuksen tarkentamista [11] tai jaettua hajotusta [12] . Kun kooderi on rakennettu, monet tutut graafiteorian ongelmat voidaan ratkaista kulkemalla kooderin läpi alhaalta ylöspäin.

Esimerkiksi maksimiklikin löytämiseksi kopiokuvasta laskemme alhaalta ylöspäin kunkin aligraafin maksimiklikin, jota edustaa kooderin alipuu. Jokaiselle 0:lla merkitylle pisteelle maksimiklikki on huippun jälkeläisiltä saatu maksimiklikki. Huipulla, jonka nimi on 1, maksimiklikki on kärjen jälkeläisille laskettujen klikkien liitto, ja tämän klikkin koko on klikkin kokojen summa. Siten ottamalla vuorotellen maksimikoko ja summaamalla arvot kooderin kullekin kärkelle, laskemme maksimiklikin koon ja vuorotellen valitsemalla maksimiklikin ja ketjuttamalla, rakennamme itse maksimiklikin. Samanlainen alhaalta ylös -lähestymistapa mahdollistaa suurimman riippumattoman joukon , kromaattisen luvun , maksimiklikkipeiton ja Hamiltonin polun olemassaolon saamisen lineaarisessa ajassa. Puiden avulla voidaan myös määrittää lineaarisessa ajassa, ovatko kaksi kografia isomorfisia .

Jos H on G  :n generoitu osagraafi , niin H itse on kopiograafi. H :n kooderi voidaan saada poistamalla G :n kooderista joitakin lehtiä ja yhdistämällä sitten kärjet, joissa on yksi lapsi. Kruskalin puulauseesta seuraa , että aligraafilla generoitava relaatio on hyvä kvasijärjestys kografeille [13] . Joten jos sarjakuvaajien perhe (kuten tasokograafit ) suljetaan generoidun osagraafin rakentamisen yhteydessä, siinä on rajallinen määrä kiellettyjä luotuja aligraafia . Laskennallisesti tämä tarkoittaa sitä, että graafin kuuluvuus sellaiseen perheeseen voidaan tarkistaa lineaarisessa ajassa käyttämällä tietyn graafin kooderin alhaalta ylöspäin suuntautuvaa läpikulkua.

Muistiinpanot

  1. ↑ 1 2 3 Jung, 1978 .
  2. ↑ Lerchs, 1971 .
  3. ↑ Seinsche, 1974 .
  4. ↑ 12. Sumner , 1974 .
  5. ↑ Burlet, Uhry, 1984 .
  6. ↑ Brandstädt, Le, Spinrad, 1999 .
  7. ↑ 1 2 Corneil, Lerchs, Burlingham, 1981 .
  8. ↑ Courcelle, Olariu, 2000 .
  9. ↑ Bose, Buss, Lubiw, 1998 .
  10. ↑ Corneil, Perl, Stewart, 1985 .
  11. ↑ Habib, Paul, 2005 .
  12. ↑ Gioan, Paul, 2008 .
  13. ↑ Damaschke, 1990 .

Kirjallisuus

Linkit