Graficul discurilor
În teoria graficelor geometrice , un grafic de disc este graficul de intersecție al unei familii de discuri unitare în planul euclidian . Adică, formăm un vârf pentru fiecare disc și conectăm două noduri printr-o margine ori de câte ori discurile corespunzătoare au o intersecție ne-goală.
Caracterizări
Există diferite definiții posibile ale graficului discului, una echivalentă cu cealaltă până la alegerea unui factor de scară:
- Un grafic de intersecție a cercurilor cu rază egală sau a discurilor cu rază egală
- Un grafic format dintr-o colecție de discuri cu rază egală, în care două cercuri sunt conectate printr-o margine dacă un cerc conține centrul celuilalt cerc
- Un grafic format dintr-o colecție de puncte din planul euclidian, în care două puncte sunt conectate dacă distanța lor este sub un prag fix
Proprietate
Fiecare subgraf indus al unui grafic pe disc este, de asemenea, un grafic pe disc. Un exemplu de grafic care nu este un grafic pe disc este steaua K 1,7 cu un nod central conectat la șapte foi: dacă fiecare dintre cele șapte discuri atinge un disc comun, unele perechi din cele șapte discuri trebuie să se atingă (deoarece numărul de osculații în plan este 6). Prin urmare, graficele de disc nu pot conține un subgraf indus de K 1,7 .
Aplicații
Începând cu lucrările lui Huson și Sen (1995) , graficele de discuri au fost utilizate în informatică pentru a modela topologia rețelelor de comunicații fără fir ad hoc . În această aplicație, nodurile sunt conectate printr-o conexiune directă fără fir, fără o stație de bază . Se presupune că toate nodurile sunt omogene și sunt echipate cu antene omnidirecționale . Locațiile nodurilor modelate ca puncte euclidiene și zona în care un semnal de la un nod poate fi primit de un alt nod este modelată ca un cerc. Dacă toate nodurile au emițătoare de putere egală, aceste cercuri sunt la fel. Graficele geometrice aleatorii, formate ca grafice pe discuri cu centre de disc generate aleatoriu, au fost, de asemenea, utilizate ca model de percolație și de alte fenomene. [1]
Complexitatea computațională
Este NP-dificil (mai precis, complet pentru teoria existențială a numerelor reale ) să se determine dacă un grafic, dat fără geometrie, poate fi reprezentat ca un grafic pe disc. [2] În plus, este demonstrabil imposibil să se producă coordonatele explicite ale reprezentării unui grafic de disc în timp polinomial: există grafice de disc care necesită exponențial mulți biți de precizie în orice reprezentare de acest tip. [3]
Cu toate acestea, multe probleme importante și dificile de optimizare a graficului, cum ar fi setul maxim independent , colorarea graficului și setul dominant minim, pot fi aproximate eficient utilizând structura geometrică a acestor grafice [4], iar problema maximă a fisurilor poate fi rezolvată exact pentru aceste grafice în polinom timp, dat o reprezentare prin intermediul discurilor. [5] Mai puternic, dacă se dă o intrare unui grafic, este posibil să se producă în timp polinomial fie o fisură maximă, fie o dovadă că graficul nu este un grafic pe disc. [6]
Când un set dat de vârfuri formează un subset al unei rețele triunghiulare , se cunoaște o condiție necesară și suficientă pentru perfecțiunea unui grafic pe disc. [7] Pentru grafice perfecte, numeroase probleme de optimizare NP-complete ( problema de colorare a graficului , problema maximă a fisurilor și problema maximă a setului independent ) sunt rezolvabile polinomial.
Notă
Bibliografie
- Heinz Breu și David G. Kirkpatrick , Unitatea de recunoaștere a graficelor pe disc este NP-hard , în Computational Geometry Theory and Applications , vol. 9, 1-2, 1998, 3-24.
- Brent N. Clark, Charles J. Colbourn și David S. Johnson , Graficele discurilor unitare , în Discrete Mathematics , vol. 86, 1–3, 1990, 165–177, DOI : 10.1016 / 0012-365X (90) 90358-O .
- Jesper Dall și Michael Christensen, grafice geometrice aleatorii , în Phys. Rev. E , vol. 66, 2002, 016121, DOI : 10.1103 / PhysRevE.66.016121 , arXiv : cond-mat / 0203026 .
- Mark L. Huson și Arunabha Sen, Algoritmi de programare a difuzării pentru rețelele radio , în Conferința de comunicații militare, IEEE MILCOM '95 , vol. 2, 1995, 647-651, DOI : 10.1109 / MILCOM.1995.483546 , ISBN 0-7803-2489-7 .
- Ross J. Kang și Tobias Müller, Sphere and dot product representations of graphs , în Proceedings of the Douăzeci și șaptelea Simpozion anual de geometrie computațională (SCG'11), 13-15 iunie 2011, Paris, Franța , 2011, 308-314.
- Madhav V. Marathe, Heinz Breu, Harry B. Hunt, III, SS Ravi și Daniel J. Rosenkrantz, Euristică bazată pe geometrie pentru graficele pe discuri , 1994, arXiv : math.CO/9409226 .
- Tomomi Matsui, Algoritmi de aproximare pentru probleme maxime de seturi independente și probleme de colorare fracționată pe graficele discurilor de unitate , în Lecture Notes in Computer Science , Lecture Notes in Computer Science, vol. 1763, 2000, 194–200, DOI : 10.1007 / 978-3-540-46515-7_16 , ISBN 978-3-540-67181-7 .
- Colin McDiarmid și Tobias Mueller, realizări întregi ale graficelor de disc și segment , 2011, arXiv : 1111.2931 .
- Yuichiro Miyamoto și Tomomi Matsui, Perfectness și Imperfectness of the kth Power of Lattice Graphs , în Lecture Notes in Computer Science , Lecture Notes in Computer Science, vol. 3521, 2005, 233–242, DOI : 10.1007 / 11496199_26 , ISBN 978-3-540-26224-4 .
- Vijay Raghavan și Jeremy Spinrad, Algoritmi robusti pentru domenii restricționate , în Journal of Algorithms , vol. 48, nr. 1, 2003, 160-172, DOI : 10.1016 / S0196-6774 (03) 00048-8 , MR 2006100 .
Elemente conexe
- Complex Vietoris-Rips , o generalizare a graficului de disc care construiește spații topologice de ordin superior de la distanțe unitare într-un spațiu metric
- Graficul distanței unitare , un grafic format din puncte de legătură care sunt exact la distanța unu, mai degrabă decât (ca aici) cel mult la un prag dat
