|
Raffigurazione di un grafoLa raffigurazione dei grafi, o tracciamento dei grafi, è una disciplina che si colloca tra la teoria dei grafi e l'informatica, 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, l'analisi delle reti sociali. Essa richiede l'uso di nozioni di geometria e topologia e lo sviluppo di algoritmi e di impegnativi sistemi software. TeoriaConsideriamo 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 l'una nell'altra 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. Criteri sul disegno di grafiGrafi planari Si definisce planare un grafo che può essere disegnato sul piano in modo che le connessioni tra i nodi possano essere rappresentate da segmenti che non si intersecano. Un disegno senza intersezioni tra archi rende il grafo molto comprensibile ad occhio umano AlgoritmiAlgoritmi Force directedGli algoritmi force-directed, cioè orientati alle forze, sono una classe di algoritmi per disegnare grafi. Un algoritmo di questo tipo considera il disegno del grafo come un sistema fisico, in cui sono in gioco forze sui nodi. Ad esempio l'algoritmo di Eades (1984) prevede che vi siano forze attrattive tra i nodi adiacenti, come avviene in una molla. Queste forze fanno sì che i nodi adiacenti si avvicinino nel disegno finale. Allo stesso tempo l'algoritmo di Eades considera forze repulsive tra i nodi non adiacenti, queste forze fanno sì che due nodi non adiacenti tendano ad allontanarsi nel disegno finale. L'energia totale del sistema fisico diminuira' se i nodi adiacenti sono vicini e i nodi non adiacenti sono lontani. Un disegno comprensibile e gradevole è correlato ad un sistema fisico con bassa energia. [1] Note
Bibliografia
Voci correlateCollegamenti esterniI siti web sottoindicati sono particolarmente degni di nota.
|
