Kruunu (graafiteoria)

Graafiteoriassa 2n -kärkikruunu on suuntaamaton graafi , jossa on kaksi joukkoa pisteitä u i ja v i sekä reunat u i :n ja v j :n välillä , jos i ≠ j . Kruunua voidaan pitää täydellisenä kaksiosaisena graafina , josta täydellinen vastaavuus on poistettu , täydellisen graafin kaksoiskaksiosaisena graafina tai Kneserin kaksiosaisena graafina H n ,1, joka edustaa 1 alkion ja ( n - ) osajoukkoja 1) n - alkiojoukon elementit, joiden reunat ovat kahden osajoukon välissä, jos toinen osajoukko sisältyy toiseen.

Esimerkkejä

Kruunu, jossa on kuusi pistettä, muodostaa syklin , ja kruunu, jossa on kahdeksan kärkeä , on isomorfinen kuutiograafin kanssa . Kaksoiskuuden Schläfli - konfiguraatiossa, jossa on 12 viivaa ja 30 pistettä kolmiulotteisessa avaruudessa, kaksitoista viivaa leikkaavat toisensa kruunukuviossa, jossa on 12 kärkeä.

Ominaisuudet

Kruunun reunojen lukumäärä on suorakaiteen muotoinen luku n ( n − 1). Sen akromaattinen luku on n — täydellinen väritys  löytyy valitsemalla väriluokiksi pari { u i , v i } [1] . Kruunut ovat symmetrisiä ja etäisyystransitiivisia kuvaajia. Archdeacon ym . [2] kuvaavat kruunun reunojen jakautumista samanpituisiin sykleihin.

Kruunu, jossa on 2n kärkeä, voidaan upottaa neliulotteiseen euklidiseen avaruuteen siten, että sen kaikkien reunojen pituus on yksi. Tällainen upottaminen voi kuitenkin sijoittaa ei-viereisiä kärkipisteitä yhden etäisyydelle. Upotus, jossa reunojen pituus on yksi ja ei-viereisten kärkien välinen etäisyys ei ole yhtä suuri, vaatii vähintään mittasuhteen n − 2. Tämä osoittaa, että graafin esittäminen yksikköetäisyyksien kuvaajana ja tiukasti yksikköetäisyyksien kuvaajana , vaaditaan täysin erilaiset mitat [3 ] . Vähimmäismäärä täydellisiä kaksiosaisia ​​alikaavioita , jotka vaaditaan kattamaan kruunun reunat (sen kaksiosainen ulottuvuus tai klikkin vähimmäispeittokoko) on

eli keskusbinomikertoimen käänteisfunktio [ 4] .

2n -kärkisen kruunun komplementti on täydellisten graafien K 2 K n suora tulo , joka vastaa 2 ×  n: n tornigraafia .

Sovellus

Etiketissä - perinteisissä säännöissä vieraiden istuttamiseen  ruokapöytään - miesten ja naisten tulisi vaihdella, eikä avioparien tulisi istua vierekkäin. Nämä säännöt täyttävää istumapaikkaa n parin seurueelle voidaan kuvata Hamiltonin koronasykliksi. Mahdollisten istumajärjestelyjen lukumäärän laskemisen ongelma tai, joka on lähes sama [5] kuin kruunun Hamiltonin syklien lukumäärä, tunnetaan kombinatoriikassa vierasongelmana . Koronoissa, joissa on 6, 8, 10, … kärkeä, (suuntautuneiden) Hamiltonin syklien määrä on

2, 12, 312, 9600, 416880, 23879520, 1749363840, ... OEIS - sekvenssi A094047 .

Kruunuilla voidaan osoittaa, että ahne värjäysalgoritmi käyttäytyy joissakin tapauksissa huonosti – jos kruunun kärjet esitetään algoritmille järjestyksessä u 0 , v 0 , u 1 , v 1 jne., niin ahne väritys on käytössä. n väriä, vaikka värien optimaalinen määrä on kaksi. Tämä rakenne johtuu Johnsonista [6] , ja itse kruunuja kutsutaan joskus Johnson-graafiksi merkinnällä J n [7] . Fuhrer [8] käytti kruunuja osana rakennetta, joka osoitti väritysongelman lähentämisen monimutkaisuuden.

Matushek [9] käytti etäisyyttä koronassa esimerkkinä metrisestä avaruudesta , jota on vaikea upottaa normaaliin vektoriavaruuteen .

Kuten Miklavic ja Poroshnik [10] ovat osoittaneet , kruunut sisältyvät pieneen määrään erityyppisiä kaavioita, jotka ovat etäisyyden säännöllisiä kiertokaavioita .

Agarwal ym . [11] kuvaavat polygoneja, joissa on kruunuja näkyvyyskaavioina . He käyttävät niitä esimerkkinä osoittamaan, että graafien esittäminen täydellisten kaksiosaisten graafien liittona ei aina ole muistitehokasta.

Kruunu, jossa on 2n kärkeä, joiden reunat on suunnattu kaksiosaisen graafin toiselta puolelta toiselle, muodostaa vakioesimerkin osittain järjestetystä joukosta , jonka järjestysmitta n .

Muistiinpanot

  1. ↑ Amitabh Chaudhary, Sundar Vishwanathan. SODA '97: Diskreettejä algoritmeja käsittelevän 8. ACM-SIAM-symposiumin julkaisut. - 1997. - S. 558-563 .
  2. ↑ D. Archdeacon, M. Debowsky, J. Dinitz, H. Gavlas. Kierrä järjestelmät täydellisessä kaksiosaisessa graafissa miinus yksikerroin // Diskreetti matematiikka . - 2004. - T. 284 , no. 1-3 . - S. 37-43 . - doi : 10.1016/j.disc.2003.11.021 .
  3. ↑ Paul Erdős, Miklos Simonovits. Geometristen graafien kromaattisesta lukumäärästä // Ars Combinatoria. - 1980. - T. 9 . - S. 229-246 .
  4. ↑ Dominique de Caen, David A. Gregory, Norman J. Pullman. Proc. 3rd Caribbean Conference on Combinatoriics and Computing / toim. Charles C. Cadogan. - Matematiikan laitos, Länsi-Intian yliopisto, 1981. - S. 169-173 .
  5. ↑ Vierastehtävässä syklin alkusijainti on merkitsevä, joten Hamiltonin syklien määrä ja vierastehtävän ratkaisu eroavat kertoimella 2n .
  6. ↑ D.S. Johnson. Proc. 5th Southeastern Conf. Kombinatoriikasta, Graafiteoriasta ja Computingista, Utilitas Mathematicae. - Winnipeg, 1974. - S. 513-527 .
  7. ↑ M. Kubale. Graafin väritykset. - American Mathematical Society, 2004. - ISBN 0-8218-3458-4 .
  8. ↑ Furer. Proc. 36. IEEE Symp. Tietojenkäsittelytieteen perusteet (FOCS '95) . - 1995. - S. 414 -421 . - ISBN 0-8186-7183-1 . - doi : 10.1109/SFCS.1995.492572 .
  9. ↑ Jiri Matousek. Vääristymisestä, joka vaaditaan äärellisten metristen avaruuksien upottamiseksi normidavaruuksiin // Israel Journal of Mathematics. - 1996. - T. 93 , no. 1 . - S. 333-344 . - doi : 10.1007/BF02761110 .
  10. ↑ Štefko Miklavic, Primož Poročnik. Distance-säännölliset kiertoliikkeet // European Journal of Combinatorics. - 2003. - T. 24 , no. 7 . - S. 777-784 . - doi : 10.1016/S0195-6698(03)00117-3 .
  11. ↑ Pankaj K. Agarwal, Noga Alon, Boris Aronov, Subhash Suri. Voidaanko näkyvyyskaavioita esittää kompaktisti? // Diskreetti ja laskennallinen geometria. - 1994. - T. 12 , no. 1 . - S. 347-365 . - doi : 10.1007/BF02574385 .

Linkit