Yksikköympyräkaavio

Graafiteoriassa yksikköympyrän graafi on yksikköympyräperheen leikkauskuvaaja euklidisella tasolla . _ Toisin sanoen muodostamme kullekin ympyrälle kärjen ja yhdistämme kaksi kärkeä reunalla, jos vastaavat ympyrät leikkaavat.

Ominaisuudet

Yksikköympyröiden kaavion määrittämiseen on useita vaihtoehtoja, jotka vastaavat kertoimen valintaa:

• Kaavio ympyröiden tai samansäteisten ympyröiden leikkauspisteistä.
• Kuvaaja, joka on muodostettu joukosta samansäteisiä ympyröitä, joissa kaksi ympyrää on yhdistetty reunalla, jos yhden ympyrän keskipiste on toisen sisällä.
• Euklidisen tason pistejoukosta muodostettu graafi, jossa kaksi pistettä on yhdistetty reunalla, jos näiden pisteiden välinen etäisyys on pienempi kuin jokin kynnys.

Ominaisuudet

Mikä tahansa yksikköympyräkaavion luotu osagraafi on myös yksikköympyräkaavio. Esimerkki kaaviosta, joka ei ole yksikköympyräkaavio, on tähti K 1,7 , jonka keskipiste on yhdistetty seitsemään lehtiin - jos jokainen seitsemästä ympyrästä koskettaa keskiympyrää, minkä tahansa ympyräparin on koskettava toisiaan ( koska yhteysnumero koneessa on 6 ). Siten yksikköympyrägraafi ei voi sisältää K 1,7 :ää generoituna osagraafina.

Sovellukset

Husonin ja Senin työstä lähtien ( Huson, Sen 1995 ) yksikköympyräkaavioita on käytetty tietojenkäsittelytieteessä langattomien hajautettujen itseorganisoituvien verkkojen topologian mallintamiseen . Tässä sovelluksessa solmut on yhdistetty suoralla langattomalla tiedonsiirrolla ilman tukiasemaa . Oletetaan, että kaikki kärjet ovat homogeenisia ja varustettu ympärisäteilevillä antenneilla . Antennien sijainti mallinnetaan pisteinä euklidisella tasolla ja alue, jossa signaali voi vastaanottaa toisen kärjen, mallinnetaan ympyränä. Jos kaikilla pisteillä on samantehoiset lähettimet, näillä ympyröillä on sama säde. Satunnaisia ​​geometrisia kuvaajia, jotka on muodostettu yksikköympyräkaavioiksi, joissa on satunnainen keskipiste, voidaan käyttää suodatuksen ja joidenkin muiden ilmiöiden mallintamiseen. [yksi]

Laskennallinen monimutkaisuus

Ongelma siitä, voidaanko abstraktisti annettu graafi esittää yksikköympyrägraafina, on NP-kova (tarkemmin sanottuna täydellinen reaalilukujen eksistentiaaliteorialle ) [2] [3] . Lisäksi on osoittautunut mahdottomaksi löytää polynomiajassa tiettyjä yksikköympyröiden koordinaatteja: on yksikköympyräkaavioita, jotka vaativat eksponentiaalisen määrän bittejä missä tahansa tällaisessa esityksessä [4] .

Kuitenkin monet tärkeät ja monimutkaiset graafien optimointiongelmat, kuten riippumaton joukko- ongelma , kuvaajan väritys ja vähimmäisdominoiva joukko -ongelma , voidaan tehokkaasti approksimoida käyttämällä näiden kuvaajien geometrista rakennetta [5] [6] ja klikkiongelmaa. nämä kuvaajat voidaan ratkaista täsmälleen polynomiajassa, jos ympyräesitys annetaan [7] . Tarkemmin sanottuna annetulle graafille polynomiajassa voidaan joko löytää maksimiklikki tai todistaa, että kuvaaja ei ole yksikköympyrägraafi [8] .

Jos annettu kärkijoukko muodostaa kolmiohilan osajoukon, graafin täydellisyyden välttämätön ja riittävä ehto tunnetaan [9] . Täydellisten graafien kohdalla monet NP-täydelliset optimointiongelmat ( kuvaajan väritysongelma , maksimiklikkitehtävä ja riippumaton joukkotehtävä ) voidaan ratkaista polynomiajassa.

Katso myös

• Vietoris-Rips-kokoelma , yksikköympyrägraafin yleistys, muodostaa konstruktion korkeamman asteen topologiseen avaruuteen metrisen avaruuden yksikköetäisyyksistä.
• Yksikköetäisyyskaavio , muodostettu yhdistämällä pisteitä, jotka ovat täsmälleen yhden, vähintään yhden päässä toisistaan ​​(kuten yksikköympyräkaavioissa).

Muistiinpanot

1. ↑ Katso esimerkiksi Dahlin ja Christensenin työ ( Dall, Christensen 2002 ).
2. ↑ Breu, Kirkpatrick, 1998 .
3. ↑ Kang, Müller, 2011 .
4. ↑ McDiarmid, Mueller, 2011 .
5. ↑ Marathe et ai, 1994 .
6. ↑ Matsui, 2000 .
7. ↑ Clark, Colbourn, Johnson, 1990 .
8. ↑ Raghavan, Spinrad, 2003 .
9. ↑ Miyamoto, Matsui, 2005 .

Linkit

• Heinz Breu, David G. Kirkpatrick. Yksikkölevykuvaajan tunnistus on NP-hard // Computational Geometry Theory and Applications. - 1998. - T. 9 , no. 1-2 . — s. 3–24 .
• Brent N. Clark, Charles J. Colbourn, David S. Johnson. Yksikkölevykaaviot // Diskreetti matematiikka . - 1990. - T. 86 , no. 1-3 . — S. 165–177 . - doi : 10.1016/0012-365X(90)90358-O .
• Jesper Dall, Michael Christensen. Satunnaiset geometriset kaaviot // Phys. Rev. E. - 2002. - T. 66 . - S. 016121 . - doi : 10.1103/PhysRevE.66.016121 . - arXiv : cond-mat/0203026 .
• Mark L. Huson, Arunabha Sen. Military Communications Conference, IEEE MILCOM '95. - 1995. - T. 2 . — S. 647–651 . — ISBN 0-7803-2489-7 . - doi : 10.1109/MILCOM.1995.483546 .
• Ross J. Kang, Tobias Müller. Proceedings of Twenty-7th Annual Symposium on Computational Geometry (SCG'11), 13.–15.6.2011, Pariisi, Ranska. - 2011. - S. 308-314 .
• Madhav V. Marathe, Heinz Breu, Harry B. Hunt, III, SS Ravi, Daniel J. Rosenkrantz. Geometriaan perustuva heuristiikka yksikkölevykaavioille . - 1994. - arXiv : math.CO/9409226 .
• Tomomi Matsui. Approksimaatioalgoritmit riippumattomien enimmäisjoukkojen ongelmiin ja murto-osien väritysongelmiin yksikkölevykaavioissa // Tietojenkäsittelytieteen luentomuistiinpanot. - 2000. - T. 1763 . — S. 194–200 . — ISBN 978-3-540-67181-7 . - doi : 10.1007/978-3-540-46515-7_16 .
• Colin McDiarmid, Tobias, Mueller. Levy- ja segmenttikaavioiden kokonaislukutoteutukset. - 2011. - arXiv : 1111.2931 .
• Yuichiro Miyamoto, Tomomi Matsui. Hilagraafien k:nnen tehon täydellisyys ja epätäydellisyys // Tietojenkäsittelytieteen luentomuistiinpanot. - 2005. - T. 3521 . — S. 233–242 . - ISBN 978-3-540-26224-4 . - doi : 10.1007/11496199_26 .
• Vijay Raghavan, Jeremy Spinrad. Vahvat algoritmit rajoitetuille verkkotunnuksille // Journal of Algorithms. - 2003. - T. 48 , no. 1 . — S. 160–172 . - doi : 10.1016/S0196-6774(03)00048-8 .