Grafo di dischi

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca
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

[modifica | modifica wikitesto]

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

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 K1,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 K1,7.

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

[modifica | modifica wikitesto]

È 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.

Voci correlate

[modifica | modifica wikitesto]
  • 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
  Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica