Grafo
Nella matematica moderna, si dice grafo (da non confondere con grafico) una figura costituita da punti, detti vertici o nodi, e da linee che li uniscono, dette lati o spigoli o archi''. Più formalmente, dato un insieme A di nodi, un grafo è un sottoinsieme G ⊆ A × A del prodotto cartesiano. I grafi sono oggetto della Teoria dei grafi.
Storia
Il primo testo che prende in considerazione i grafi come entità matematiche è la pubblicazione di Eulero sui "Sette ponti di Königsberg". In questo testo viene anche per la prima volta affrontato un problema di geometria topologica, che non dipende da alcuna misurazione.
Ci sono due modi generali per reppresentare un grafo in una struttura dati di un programma: la lista di adiacenze e la matrice di adiacenze.
In una lista di adiacenze, una lista mantiene un elenco di nodi, ed ad ogni nodo è collegata una lista di puntatori ai nodi collegati da un arco.
In una matrice di adiacenze, una matrice N per N, dove N è il numero dei nodi, mantiene un valore vero in una cella (a,b) se il nodo a è collegato al nodo b. La matrice è simmetrica solo se il grafo non è orientato.
Ognuna delle due rappresentazioni ha alcuni vantaggi: con una lista di adiacenze è facile trovare tutti i nodi adiacenti ad un nodo dato e verificare l'esistenza di connessioni tra nodi; con una matrice di adiacenze è più facile invertire i grafi e individuarne sottografi.
Rappresentazioni informatiche dei grafi
| Astronomia | Biologia | Botanica | Chimica | Ecologia | Economia | Fisica | Geometria | Informatica | Matematica | Medicina | Statistica | Telecomunicazioni |
