Loading AI tools
Da Wikipedia, l'enciclopedia libera
La 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.
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 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.
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
Gli 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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.