Graficul cercului unitar

În teoria grafurilor, graficul cercului unitar este graficul de intersecție al unei familii de cercuri unitare pe planul euclidian . Adică, formăm un vârf pentru fiecare cerc și conectăm două vârfuri cu o muchie dacă cercurile corespunzătoare se intersectează.

Caracteristici

Există mai multe opțiuni pentru definirea graficului cercurilor unitare, care sunt echivalente până la alegerea coeficientului:

• Graficul intersecțiilor unor cercuri sau cercuri de aceeași rază.
• Un grafic format dintr-un set de cercuri de aceeași rază, în care două cercuri sunt conectate printr-o muchie dacă centrul unui cerc este în interiorul celuilalt.
• Un grafic format dintr-un set de puncte din planul euclidian în care două puncte sunt conectate printr-o muchie dacă distanța dintre aceste puncte este mai mică decât un anumit prag.

Proprietăți

Orice subgraf generat al graficului cerc unitar este, de asemenea, un grafic cerc unitar. Un exemplu de grafic care nu este un grafic circular unitar este steaua K 1,7 cu un vârf central conectat la șapte frunze - dacă fiecare dintre cele șapte cercuri atinge cercul central, orice pereche de cercuri trebuie să se atingă între ele ( deoarece numărul de contact din avion este 6). Astfel, graficul cerc unitar nu poate conține K 1,7 ca subgraf generat.

Aplicații

De la lucrările lui Huson și Sen ( Huson, Sen 1995 ), graficele cercului unitar au fost folosite în informatică pentru a modela topologia rețelelor de auto-organizare descentralizate fără fir . În această aplicație, nodurile sunt conectate prin comunicare directă fără fir fără o stație de bază . Se presupune că toate vârfurile sunt omogene și echipate cu antene omnidirecționale . Locația antenelor este modelată ca puncte pe planul euclidian, iar zona în care semnalul poate fi recepționat de un alt vârf este modelată ca un cerc. Dacă toate vârfurile au transmițători de aceeași putere, aceste cercuri vor avea aceeași rază. Graficele geometrice aleatorii formate ca grafice cerc unitare cu centre aleatoare pot fi folosite pentru a modela filtrarea și alte fenomene. [unu]

Complexitate computațională

Problema dacă un graf dat în mod abstract poate fi reprezentat ca un graf cerc unitar este NP-hard (mai precis, complet pentru teoria existențială a numerelor reale ) [2] [3] . În plus, este o imposibilitate dovedită în timp polinomial de a găsi anumite coordonate ale cercurilor unitare: există grafice cerc unitare care necesită un număr exponențial de biți de precizie în orice astfel de reprezentare [4] .

Cu toate acestea, multe probleme de optimizare importante și complexe ale graficelor, cum ar fi problema mulțimii independente , colorarea graficului și problema setului dominant minim , pot fi aproximate eficient folosind structura geometrică a acestor grafice [5] [6] și problema clicei. căci aceste grafice pot fi rezolvate exact în timp polinomial dacă este dată reprezentarea cercului [7] . Mai precis, pentru un grafic dat, în timp polinomial, se poate găsi fie clica maximă, fie se poate demonstra că graficul nu este un grafic cerc unitar [8] .

Dacă mulțimea dată de vârfuri formează o submulțime a rețelei triunghiulare , se cunoaște condiția necesară și suficientă pentru perfecțiunea graficului [9] . Pentru grafice perfecte, multe probleme de optimizare NP-completă ( problema de colorare a graficului , problema clicei maxime și problema seturilor independente ) pot fi rezolvate în timp polinomial.

Vezi și

• Colecția Vietoris-Rips , o generalizare a graficului cerc unitar, formează o construcție într-un spațiu topologic de ordin superior din distanțele unitare dintr-un spațiu metric.
• Graficul de distanță unitară , format prin conectarea punctelor care sunt exact unul, nu mai puțin de unul (ca în graficele cercului unitar).

Note

1. ↑ Vezi, de exemplu, lucrarea lui Dahl și Christensen ( 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 .

Link -uri

• Heinz Breu, David G. Kirkpatrick. Recunoașterea grafică a discului unitar este NP-hard // Teoria și aplicațiile geometriei computaționale. - 1998. - T. 9 , nr. 1–2 . — pp. 3–24 .
• Brent N. Clark, Charles J. Colbourn, David S. Johnson. Grafice disc unitare // Matematică discretă . - 1990. - T. 86 , nr. 1–3 . — S. 165–177 . - doi : 10.1016/0012-365X(90)90358-O .
• Jesper Dall, Michael Christensen. Grafice geometrice aleatorii // Fiz. Rev. E. - 2002. - T. 66 . - S. 016121 . - doi : 10.1103/PhysRevE.66.016121 . - arXiv : cond-mat/0203026 .
• Mark L. Huson, Arunabha Sen. Conferința de comunicații militare, 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 iunie 2011, Paris, Franța. - 2011. - S. 308-314 .
• Madhav V. Marathe, Heinz Breu, Harry B. Hunt, III, SS Ravi, Daniel J. Rosenkrantz. Euristică bazată pe geometrie pentru graficele de discuri unitare . - 1994. - arXiv : math.CO/9409226 .
• Tomomi Matsui. Algoritmi de aproximare pentru probleme de seturi independente maxime și probleme de colorare fracțională pe graficele de disc unități // Note de curs în informatică. - 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. Realizări de numere întregi ale graficelor de discuri și segmente. - 2011. - arXiv : 1111.2931 .
• Yuichiro Miyamoto, Tomomi Matsui. Perfecțiunea și imperfecțiunea puterii a k-a a graficelor latice // Note de curs în informatică. - 2005. - T. 3521 . — S. 233–242 . - ISBN 978-3-540-26224-4 . - doi : 10.1007/11496199_26 .
• Vijay Raghavan, Jeremy Spinrad. Algoritmi robusti pentru domenii restrânse // Journal of Algorithms. - 2003. - T. 48 , nr. 1 . — S. 160–172 . - doi : 10.1016/S0196-6774(03)00048-8 .