Ympyräkaavio

Graafiteoriassa ympyräkaavio on kaavio ympyrän jännejoukon leikkauspisteistä . _ Toisin sanoen se on suuntaamaton graafi , jonka kärjet voidaan tunnistaa ympyrän sointujen kanssa, ja nämä kärjet ovat vierekkäin, jos ja vain jos vastaavat sointeet leikkaavat.

Algoritminen monimutkaisuus

Spinrad [1] esitteli O( n 2 ) -ajassa ajettavan algoritmin, joka testaa, onko tietty n -pisteen suuntaamaton graafi ympyrämäinen, ja jos se on ympyrämäinen, muodostaa joukon sointuja, jotka tuottavat ympyränmuotoisen graafin.

Monissa muissa ongelmissa, jotka ovat NP-täydellisiä yleisillä kaavioilla, on polynomiaikaiset algoritmit, jos ne rajoittuvat ympyräkaavioihin. Esimerkiksi Klox [2] osoitti, että ympyrägraafin puunleveys voidaan määrittää ja optimaalinen hajoamispuu muodostaa O( n 3 ) -ajassa. Lisäksi pienin korvaus (eli sointugraafi , jossa on mahdollisimman vähän reunoja ja joka sisältää annetun ympyrägraafin osagraafina) löytyy O( n 3 ) -ajassa [3] . Tiskin [4] osoitti, että ympyräkaavion suurin klikki löytyy O( n log 2 n ) ajasta, ja Nash ja Gregg [5] osoittivat, että painottamattoman ympyräkaavion suurin riippumaton joukko löytyy O( n min{ d , α }), missä d on kaavioparametri, joka tunnetaan nimellä tiheys , ja α on ympyräkuvaajan riippumattomuusluku .

Silti on ongelmia, jotka pysyvät NP-täydellisinä , vaikka ne rajoittuvat ympyräkaavioihin. Näihin tehtäviin kuuluu hallitsevan joukon , pienimmän yhdistetyn dominantin joukon ja pienimmän kokonaisdominoivan joukon etsiminen [6] .

Kromaattinen numero

Ympyräkaavion kromaattinen luku on pienin määrä värejä, joita voidaan käyttää sointujen värjäämiseen siten, että kahdella risteävällä soinnolla ei ole samaa väriä. Koska on mahdollista muodostaa ympyräkuvaaja, jossa mielivaltainen määrä sointuja leikkaa toisensa, ympyräkuvaajan kromaattinen luku voi olla mielivaltaisen suuri ja ympyräkuvaajan kromaattisen lukumäärän määrittäminen on NP-täydellinen tehtävä [8 ] . NP-täydellinen ongelma on myös sen tarkistaminen, onko mahdollista värittää ympyräkuvaaja neljällä värillä [9] . Unger [10] väitti, että värityksen etsiminen kolmella värillä voidaan tehdä polynomiajassa , mutta hänen tulosten kuvauksesta puuttuu monia yksityiskohtia [10] .

Jotkut kirjoittajat ovat tutkineet ongelmia värjätä rajoitettuja alaluokkia ympyräkaavioita pienellä määrällä värejä. Erityisesti ympyräkaavioita, joissa ei ole k tai useamman soinnun joukkoa, joissa kaikki sointeet leikkaavat toisensa, voidaan värjätä värejä ylittämättä [11] . Erityisesti, kun k  = 3 (eli kolmiottomissa ympyräkaavioissa ), kromaattinen luku ei ylitä viittä, ja tämä rajoitus on terävä – kaikki kolmiottomat ympyräkaaviot voidaan värjätä viidellä värillä, ja niissä on kolmioita. -ilmaiset ympyräkaaviot, joiden värjäys vaatii viisi väriä [12] . Jos ympyräkaaviossa on vähintään viisi ympärysmittaa (eli se ei sisällä kolmioita ja neljän kärjen sykliä), se voidaan värittää kolmella värillä [ 13] . Ongelma laatikkokaavioiden värittämisessä ilman kolmioita vastaa ongelmaa esittää laatikkograafit graafina isometrisenä puiden suoratuloon nähden . Tässä tehtävävastaannossa värien määrä vastaa tuotteessa olevien puiden määrää [14] .

Sovellukset

Ympyräkaaviot näkyvät VLSI -suunnittelussa abstraktiona PCB-reitityksen erityistapauksesta, joka tunnetaan nimellä "bipolaarinen kanavan ylitysreititys". Tässä tapauksessa jäljitysalue on suorakulmio, kaikki verkot ovat kaksinapaisia ​​ja johtimet sijaitsevat suorakulmion kehällä. On helppo nähdä, että tämän verkon leikkauskuvaaja on ympyräkuvaaja [15] . Yksi reitityksen tavoitteista on varmistaa, että eri verkkojen välillä ei ole sähköistä kosketusta ja että mahdolliset päällekkäiset osat ovat eri kerroksilla. Siten ympyräkaaviot kaappaavat osan jäljitystehtävistä.

Ympyräkaavioiden väritystä voidaan käyttää myös mielivaltaisten graafien kirjaupotusten löytämiseen - jos tietyn graafin G kärjet sijaitsevat ympyrässä ja graafin G reunat muodostavat ympyrän jänteet, niin graafin kaavio Näiden sointeiden leikkauspisteet on ympyräkaavio, ja tämän ympyräkaavion värittäminen vastaa kirjan upottamista, joka säilyttää ympyrän järjestelyn . Tässä vastaavuudessa värien määrä vastaa kirjaliitteen sivujen määrää [16] .

Aiheeseen liittyvät graafiluokat

Suoralla olevien intervallien joukon leikkauskuvaajaa kutsutaan intervallikaavioksi .

Kaavio on pyöreä silloin ja vain, jos se on säännöllinen intervallikaavio . Nämä ovat graafit, joiden kärjet vastaavat (avoimia) janaja ja kaksi kärkeä on yhdistetty reunalla, jos kahdella välillä on ei-tyhjä leikkauspiste. Mikään intervalli ei kuitenkaan sisälly kokonaan toiseen väliin.

Merkkijonograafit , tason käyrien leikkauskaaviot , sisältävät erikoistapauksena ympyräkuvaajat.

Mikä tahansa etäisyydeltä peritty graafi on ympyräkuvaaja, kuten mikä tahansa permutaatio tai välinpitämätön graafi . Mikä tahansa ulkotasograafi on myös ympyrä [17] [16] .

Muistiinpanot

  1. ↑ Spinrad, 1994 .
  2. ↑ Kloks, 1996 .
  3. ↑ Kloks, Kratsch, Wong, 1998 .
  4. ↑ Tiskin, 2010 .
  5. ↑ Nash, Gregg, 2010 .
  6. ↑ Keil, 1993 .
  7. ↑ Ageev, 1996 .
  8. ↑ Garey, Johnson, Miller, Papadimitriou, 1980 .
  9. ↑ Unger (1988) .
  10. ↑ 12 Unger , 1992 .
  11. ↑ Černý, 2007 . Katso aikaisemmat rajat Gyárfás, 1985 , Kostochka, 1988 ja Kostochka, Kratochvíl, 1997 .
  12. ↑ Katso Kostochka, 1988 ylärajasta ja Ageev, 1996 alarajan saavuttavista kaavioista. Karapetyan ( Karapetyan 1984 ) ja ( Gyárfás, Lehel 1985 ) ovat aiemmin osoittaneet heikompia rajoja samalle ongelmalle.
  13. ↑ Ageev, 1999 .
  14. ↑ Bandelt, Chepoi, Eppstein, 2010 .
  15. ↑ Sherwani, 2000 .
  16. ↑ 12 Unger , 1988 .
  17. ↑ Wessel, Poschel, 1985 .

Kirjallisuus

Linkit