Enhedscirkelgraf
I grafteori er enhedscirkelgrafen skæringsgrafen for en familie af enhedscirkler på det euklidiske plan . Det vil sige, at vi danner et toppunkt for hver cirkel og forbinder to toppunkter med en kant, hvis de tilsvarende cirkler skærer hinanden.
Karakteristika
Der er flere muligheder for at definere grafen for enhedscirkler, som svarer til valget af koefficient:
- Graf over skæringspunkter mellem cirkler eller cirkler med samme radius.
- En graf dannet af et sæt cirkler med samme radius, hvor to cirkler er forbundet med en kant, hvis midten af den ene cirkel er inde i den anden.
- En graf dannet ud fra et sæt punkter i det euklidiske plan, hvor to punkter er forbundet med en kant, hvis afstanden mellem disse punkter er mindre end en tærskel.
Egenskaber
Enhver genereret undergraf af enhedscirkelgrafen er også en enhedscirkelgraf. Et eksempel på en graf, der ikke er en enhedscirkelgraf, er stjernen K 1,7 med et centralt toppunkt forbundet med syv blade - hvis hver af de syv cirkler rører den centrale cirkel, skal ethvert par cirkler røre hinanden ( da kontaktnummer i flyet er 6 ). Enhedscirkelgrafen kan således ikke indeholde K 1,7 som en genereret undergraf.
Ansøgninger
Siden Huson og Sens arbejde ( Huson, Sen 1995 ) er enhedscirkelgrafer blevet brugt i datalogi til at modellere topologien af trådløse decentraliserede selvorganiserende netværk . I denne applikation er noderne forbundet med direkte trådløs kommunikation uden en basestation . Det antages, at alle toppunkter er homogene og udstyret med omnidirektionelle antenner . Antennernes placering er modelleret som punkter på det euklidiske plan, og området, hvor signalet kan modtages af et andet toppunkt, er modelleret som en cirkel. Hvis alle hjørner har sendere med samme effekt, vil disse cirkler have samme radius. Tilfældige geometriske grafer dannet som enhedscirkelgrafer med tilfældige centre kan bruges til at modellere filtrering og nogle andre fænomener. [en]
Beregningsmæssig kompleksitet
Problemet med, hvorvidt en abstrakt givet graf kan repræsenteres som en enhedscirkelgraf, er NP-hårdt (mere præcist komplet for den eksistentielle teori om reelle tal ) [2] [3] . Derudover er det en bevist umulighed i polynomisk tid at finde bestemte koordinater af enhedscirkler: Der er enhedscirkelgrafer, der kræver et eksponentielt antal bits af præcision i enhver sådan repræsentation [4] .
Imidlertid kan mange vigtige og komplekse optimeringsproblemer på grafer, såsom det uafhængige sætproblem , graffarvning og det minimale dominerende sætproblem effektivt tilnærmes ved hjælp af den geometriske struktur af disse grafer [5] [6] og klikproblemet for disse grafer kan løses nøjagtigt i polynomisk tid, hvis cirkelrepræsentationen er givet [7] . Mere præcist kan man for en given graf, i polynomisk tid, enten finde den maksimale klike eller bevise, at grafen ikke er en enhedscirkelgraf [8] .
Hvis det givne sæt toppunkter danner en delmængde af trekantgitteret , kendes den nødvendige og tilstrækkelige betingelse for grafens perfektion [9] . For perfekte grafer kan mange NP-komplette optimeringsproblemer ( graffarveproblemet , det maksimale klikproblem og det uafhængige sætproblem ) løses i polynomisk tid.
Se også
- Vietoris-Rips-samlingen , en generalisering af enhedscirkelgrafen, danner en konstruktion i et topologisk rum af højere orden ud fra enhedsafstande i et metrisk rum.
- Enhedsafstandsgraf , dannet ved at forbinde punkter, der er nøjagtigt én fra hinanden, ikke mindre end én (som i enhedscirkelgrafer).
Noter
- ↑ Se for eksempel Dahl og Christensens arbejde ( Dall, Christensen 2002 ).
- ↑ Breu, Kirkpatrick, 1998 .
- ↑ Kang, Müller, 2011 .
- ↑ McDiarmid, Mueller, 2011 .
- ↑ Marathe et al., 1994 .
- ↑ Matsui, 2000 .
- ↑ Clark, Colbourn, Johnson, 1990 .
- ↑ Raghavan, Spinrad, 2003 .
- ↑ Miyamoto, Matsui, 2005 .
Links
- Heinz Breu, David G. Kirkpatrick. Enhedsdisk-grafgenkendelse er NP-hård // Computational Geometry Theory and Applications. - 1998. - T. 9 , no. 1-2 . — s. 3–24 .
- Brent N. Clark, Charles J. Colbourn, David S. Johnson. Enhedsdiske grafer // Diskret matematik . - 1990. - T. 86 , no. 1-3 . — S. 165–177 . - doi : 10.1016/0012-365X(90)90358-O .
- Jesper Dall, Michael Christensen. Tilfældige geometriske grafer // Fysisk. Rev. E. - 2002. - T. 66 . - S. 016121 . - doi : 10.1103/PhysRevE.66.016121 . - arXiv : cond-mat/0203026 .
- Mark L. Huson, Arunabha Sen. Militær kommunikationskonference, 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), juni 13-15, 2011, Paris, Frankrig. - 2011. - S. 308-314 .
- Madhav V. Marathe, Heinz Breu, Harry B. Hunt, III, SS Ravi, Daniel J. Rosenkrantz. Geometribaseret heuristik for enhedsdiskgrafer . - 1994. - arXiv : math.CO/9409226 .
- Tomomi Matsui. Approksimationsalgoritmer for maksimale uafhængige sætproblemer og brøkfarveproblemer på enhedsdiskgrafer // Lecture Notes in Computer Science. - 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. Heltalsrealiseringer af disk- og 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. Robuste algoritmer til begrænsede domæner // Journal of Algorithms. - 2003. - T. 48 , no. 1 . — S. 160–172 . - doi : 10.1016/S0196-6774(03)00048-8 .