Топ-100
Indietro

ⓘ Raffigurazione di un grafo. La raffigurazione dei grafi, o tracciamento dei grafi, è una disciplina che si colloca tra la teoria dei grafi e linformatica, che s ..




Raffigurazione di un grafo
                                     

ⓘ Raffigurazione di un grafo

La raffigurazione dei grafi, o tracciamento dei grafi, è una disciplina che si colloca tra la teoria dei grafi e linformatica, che si occupa della rappresentazione dei grafi in due o tre dimensioni. Questa attività è motivata da importanti applicazioni della teoria dei grafi, come la progettazione di circuiti VLSI, la cartografia, la bioinformatica, lanalisi delle reti sociali. Essa richiede luso di nozioni di geometria e topologia e lo sviluppo di algoritmi e di impegnativi sistemi software.

                                     

1. Teoria

Consideriamo una superficie S nello spazio tridimensionale. In particolare S potrebbe essere un piano, una sfera o un toro. In teoria dei grafi si dice raffigurazione di un grafo G su una superficie S una figura tracciata su S in cui ogni nodo di G è rappresentato da un punto diverso di S punto-nodo mentre ogni vertice {p,q} di G è rappresentato da una curva curva-spigolo tendenzialmente regolare che ha le estremità nei punti-nodi corrispondenti a p e q e che non tocca nessun altro punto-nodo.

Quando la superficie S è un piano si parla di raffigurazione piana del grafo.

Due raffigurazioni di un grafo sopra una superficie si dicono topologicamente equivalenti se si possono trasformare luna nellaltra mediante una deformazione continua. Una tale deformazione non si può far attraversare una curva-spigolo da un punto-nodo.

Tra le raffigurazioni di un grafo si distinguono quelle nelle quali non si hanno spigoli che si intersecano: queste vengono chiamate raffigurazioni planari. In particolare, si distinguono le raffigurazioni piane planari.

Esistono grafi che non possiedono raffigurazioni piane planari, quali, ad esempio, i grafi di Kuratowski. Si possono ottenere raffigurazioni planari per ogni grafo a patto di complicare la superficie di immersione: da un punto di vista intuitivo, si tratta di aggiungere a tale superficie un sufficiente numero di manici.