Grafo di dischi

Una collezione di cerchi unitari e il corrispondente grafo di dischi.

Nella teoria geometrica dei grafi, un grafo di dischi è il grafo d'intersezione di una famiglia di dischi unitari nel piano euclideo. Ossia, formiamo un vertice per ciascun disco e connettiamo due vertici mediante uno spigolo ogni volta che i dischi corrispondenti hanno un'intersezione non vuota.

Caratterizzazioni

Ci sono varie definizioni possibili del grafo di dischi, l'una equivalente all'altra fino alla scelta di un fattore di scala:

• Un grafo d'intersezione di cerchi di uguale raggio, o di dischi di uguale raggio
• Un grafo formato da una collezione di dischi di uguale raggio, in cui due cerchi sono connessi da uno spigolo se un cerchio contiene il centro dell'altro cerchio
• Un grafo formato da una collezione di punti nel piano euclideo, nel quale due punti sono connessi se la loro distanza è al di sotto di una soglia fissa

Proprietà

Ogni sottografo indotto di un grafo di dischi è anch'esso un grafo di dischi. Un esempio di un grafo che non è un grafo di dischi è la stella K_1,7 con un nodo centrale connesso a sette foglie: se ciascuno dei sette dischi tocca un disco comune, qualche coppia dei sette dischi deve toccarsi tra loro (in quanto il numero di osculazione nel piano è 6). Perciò, i grafi di dischi non possono contenere un sottografo indotto K_1,7.

Applicazioni

A cominciare dal lavoro di Huson & Sen (1995), i grafi di dischi sono stati usati in informatica per modellare la topologia delle reti di comunicazione senza fili ad hoc. In questa applicazione, i nodi sono connessi attraverso una connessione senza fili diretta senza una stazione base. Si assume che tutti i nodi siano omogenei e attrezzati con antenne omnidirezionali. Le localizzazioni dei nodi modellati come punti euclidei, e l'area all'interno della quale un segnale proveniente da un nodo può essere ricevuto da un altro nodo è modellata come un cerchio. Se tutti i nodi hanno trasmittenti di uguale potenza, questi cerchi sono tutti uguali. Grafi geometrici casuali, formati come grafi di dischi con i centri dei dischi generati in modo casuale, sono stati usati anche come modello della percolazione e di vari altri fenomeni.[1]

Complessità computazionale

È NP-difficile (più specificamente, completo per la teoria esistenziale dei numeri reali) determinare se un grafo, dato senza geometria, possa essere rappresentato come un grafo di dischi.[2] In aggiunta, è dimostrabilmente impossibile emettere in tempo polinomiale le coordinate esplicite della rappresentazione di un grafo di dischi: esistono grafi di dischi che richiedono esponenzialmente molti bit di precisione in una qualsiasi rappresentazione di questo tipo.[3]

Tuttavia, molti importanti e difficili problemi di ottimizzazione dei grafi quali l'insieme indipendente massimo, la colorazione dei grafi e l'insieme dominante minimo possono essere approssimati in modo efficiente usando la struttura geometrica di questi grafi,[4] e il problema della cricca massima può essere risolto esattamente per questi grafi in tempo polinomiale, data una rappresentazione mediante dischi.[5] In modo più forte, se a un grafo si dà un'entrata, è possibile produrre in tempo polinomiale o una cricca massima o una dimostrazione che il grafo non è un grafo di dischi.[6]

Quando un dato insieme di vertici forma un sottoinsieme di un reticolo triangolare, è nota una condizione necessaria e sufficiente per la perfezione di un grafo di dischi.[7] Per i grafi perfetti, numerosi problemi di ottimizzazione NP-completi (problema della colorazione dei grafi, problema della cricca massima e problema del massimo insieme indipendente) sono polinomialmente risolvibili.

Note

1. Vedi, ad es., Dall & Christensen (2002).
2. Breu & Kirkpatrick (1998); Kang & Müller (2011).
3. McDiarmid & Mueller (2011).
4. Marathe et al. (1994); Matsui (2000).
5. Clark, Colbourn & Johnson (1990).
6. Raghavan & Spinrad (2003).
7. Miyamoto & Matsui (2005).

Bibliografia

• Heinz Breu e David G. Kirkpatrick, Unit disk graph recognition is NP-hard, in Computational Geometry Theory and Applications, vol. 9, 1–2, 1998, 3–24.
• Brent N. Clark, Charles J. Colbourn e David S. Johnson, Unit disk graphs, in Discrete Mathematics, vol. 86, 1–3, 1990, 165–177, DOI:10.1016/0012-365X(90)90358-O.
• Jesper Dall e Michael Christensen, Random geometric graphs, in Phys. Rev. E, vol. 66, 2002, 016121, DOI:10.1103/PhysRevE.66.016121, arXiv:cond-mat/0203026.
• Mark L. Huson e Arunabha Sen, Broadcast scheduling algorithms for radio networks, in Military Communications Conference, IEEE MILCOM '95, vol. 2, 1995, 647–651, DOI:10.1109/MILCOM.1995.483546, ISBN 0-7803-2489-7.
• Ross J. Kang e Tobias Müller, Sphere and dot product representations of graphs, in Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SCG'11), 13-15 giugno 2011, Parigi, Francia, 2011, 308–314.
• Madhav V. Marathe, Heinz Breu, Harry B. Hunt, III, S. S. Ravi e Daniel J. Rosenkrantz, Geometry based heuristics for unit disk graphs, 1994, arXiv:math.CO/9409226.
• Tomomi Matsui, Approximation Algorithms for Maximum Independent Set Problems and Fractional Coloring Problems on Unit Disk Graphs, in 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 e Tobias Mueller, Integer realizations of disk and segment graphs, 2011, arXiv:1111.2931.
• Yuichiro Miyamoto e Tomomi Matsui, Perfectness and Imperfectness of the kth Power of Lattice Graphs, in 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 e Jeremy Spinrad, Robust algorithms for restricted domains, in Journal of Algorithms, vol. 48, n. 1, 2003, 160–172, DOI:10.1016/S0196-6774(03)00048-8, MR 2006100.

Voci correlate

• Complesso di Vietoris-Rips, una generalizzazione del grafo di dischi che costruisce spazi topologici di ordine superiore da distanze unitarie in uno spazio metrico
• Grafo a distanza unitaria, un grafo formato connettendo punti che sono esattamente a distanza uno piuttosto che (come qui) al massimo a una data soglia