Enhetscirkeldiagram

I grafteorin är enhetscirkelgrafen skärningsgrafen för en familj av enhetscirklar på det euklidiska planet . Det vill säga, vi bildar en vertex för varje cirkel och förbinder två hörn med en kant om motsvarande cirklar skär varandra.

Egenskaper

Det finns flera alternativ för att definiera grafen för enhetscirklar, som är likvärdiga upp till valet av koefficient:

• Graf över skärningspunkter mellan cirklar eller cirklar med samma radie.
• En graf bildad av en uppsättning cirklar med samma radie, där två cirklar är förbundna med en kant om centrum av en cirkel är innanför den andra.
• En graf som bildas av en uppsättning punkter i det euklidiska planet där två punkter är förbundna med en kant om avståndet mellan dessa punkter är mindre än någon tröskel.

Egenskaper

Varje genererad subgraf av enhetscirkelgrafen är också en enhetscirkelgraf. Ett exempel på en graf som inte är en enhetscirkelgraf är stjärnan K 1,7 med en central vertex kopplad till sju blad - om var och en av de sju cirklarna rör vid den centrala cirkeln måste alla par av cirklar vidröra varandra ( eftersom kontaktnummer i planet är 6 ). Enhetscirkelgrafen kan således inte innehålla K 1,7 som en genererad subgraf.

Applikationer

Sedan Huson och Sens arbete ( Huson, Sen 1995 ) har enhetscirkelgrafer använts inom datavetenskap för att modellera topologin för trådlösa decentraliserade självorganiserande nätverk . I den här applikationen är noderna anslutna med direkt trådlös kommunikation utan basstation . Det antas att alla hörn är homogena och utrustade med rundstrålande antenner . Antennernas placering modelleras som punkter på det euklidiska planet, och området där signalen kan tas emot av en annan vertex modelleras som en cirkel. Om alla hörn har sändare med samma effekt kommer dessa cirklar att ha samma radie. Slumpmässiga geometriska grafer utformade som enhetscirkelgrafer med slumpmässiga centra kan användas för att modellera filtrering och vissa andra fenomen. [ett]

Beräkningskomplexitet

Problemet med huruvida en abstrakt given graf kan representeras som en enhetscirkelgraf är NP-hårt (mer exakt, komplett för den existentiella teorin om reella tal ) [2] [3] . Dessutom är det en bevisad omöjlighet i polynomtid att hitta vissa koordinater för enhetscirklar: det finns enhetscirkelgrafer som kräver ett exponentiellt antal bitar av precision i varje sådan representation [4] .

Emellertid kan många viktiga och komplexa optimeringsproblem på grafer, såsom det oberoende uppsättningsproblemet , graffärgning och det minsta dominerande uppsättningsproblemet , effektivt approximeras med den geometriska strukturen hos dessa grafer [5] [6] och klickproblemet för dessa grafer kan lösas exakt i polynomtid om cirkelrepresentationen ges [7] . Mer exakt, för en given graf, i polynomtid, kan man antingen hitta den maximala klicken eller bevisa att grafen inte är en enhetscirkelgraf [8] .

Om den givna uppsättningen av hörn bildar en delmängd av det triangulära gittret , är det nödvändiga och tillräckliga villkoret för grafens perfektion känt [9] . För perfekta grafer kan många NP-kompletta optimeringsproblem ( graffärgningsproblemet , maximiklickproblemet och det oberoende uppsättningsproblemet ) lösas i polynomtid.

Se även

• Vietoris-Rips-samlingen , en generalisering av enhetscirkelgrafen, bildar en konstruktion i ett topologiskt utrymme av högre ordning från enhetsavstånd i ett metriskt utrymme.
• Enhetsavståndsgraf , bildad av att ansluta punkter som är exakt en från varandra, inte mindre än en (som i enhetscirkeldiagram).

Anteckningar

1. ↑ Se till exempel Dahls och Christensens arbete ( Dall, Christensen 2002 ).
2. ↑ Breu, Kirkpatrick, 1998 .
3. ↑ Kang, Müller, 2011 .
4. ↑ McDiarmid, Mueller, 2011 .
5. ↑ Marathe et al, 1994 .
6. ↑ Matsui, 2000 .
7. ↑ Clark, Colbourn, Johnson, 1990 .
8. ↑ Raghavan, Spinrad, 2003 .
9. ↑ Miyamoto, Matsui, 2005 .

Länkar

• Heinz Breu, David G. Kirkpatrick. Enhetsdiskdiagramigenkänning är NP-hård // Computational Geometry Theory and Applications. - 1998. - T. 9 , nr. 1–2 . — s. 3–24 .
• Brent N. Clark, Charles J. Colbourn, David S. Johnson. Enhetsskivor // Diskret matematik . - 1990. - T. 86 , nr. 1–3 . — S. 165–177 . - doi : 10.1016/0012-365X(90)90358-O .
• Jesper Dall, Michael Christensen. Slumpmässiga geometriska grafer // Phys. Varv. E. - 2002. - T. 66 . - S. 016121 . - doi : 10.1103/PhysRevE.66.016121 . - arXiv : cond-mat/0203026 .
• Mark L. Huson, Arunabha Sen. Militär kommunikationskonferens, 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 the Twenty-Seventh Annual Symposium on Computational Geometry (SCG'11), 13–15 juni 2011, Paris, Frankrike. - 2011. - S. 308-314 .
• Madhav V. Marathe, Heinz Breu, Harry B. Hunt, III, SS Ravi, Daniel J. Rosenkrantz. Geometribaserad heuristik för enhetsskivor . - 1994. - arXiv : math.CO/9409226 .
• Tomomi Matsui. Approximationsalgoritmer för maximala oberoende uppsättningsproblem och bråkfärgsproblem på enhetsskivor // Föreläsningsanteckningar i datavetenskap. - 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. Heltalsförverkliganden av disk- och segmentgrafer. - 2011. - arXiv : 1111.2931 .
• Yuichiro Miyamoto, Tomomi Matsui. Perfectness and imperfectness of the kth Power of Lattice Graphs // Lecture Notes in Computer Science. - 2005. - T. 3521 . — S. 233–242 . - ISBN 978-3-540-26224-4 . - doi : 10.1007/11496199_26 .
• Vijay Raghavan, Jeremy Spinrad. Robusta algoritmer för begränsade domäner // Journal of Algorithms. - 2003. - T. 48 , nr. 1 . — S. 160–172 . - doi : 10.1016/S0196-6774(03)00048-8 .