Un diagramma di un grafo non orientato con 6 vertici e 7 spigoli.
In matematica, informatica e, più in particolare, geometria combinatoria, la teoria dei grafi è la disciplina che si occupa dello studio dei grafi, oggetti discreti che permettono di schematizzare una grande varietà di situazioni e processi, e spesso di consentirne delle analisi in termini quantitativi e algoritmici.
Il primo testo che prende in considerazione i grafi come entità matematiche è la pubblicazione di Eulero sui "Sette ponti di Königsberg". Questo testo rappresenta anche la prima volta in cui viene affrontato un problema di geometria topologica, che non dipende da alcuna misurazione: il problema dei ponti di Königsberg.
Nella seconda metà del XX secolo gli studi e i risultati si sono sviluppati ampiamente, in sintonia con i forti sviluppi della combinatoria e del calcolo automatico. L'introduzione del computer ha consentito da un lato lo sviluppo di indagini sperimentali sui grafi (come, in particolare, nella dimostrazione del teorema dei quattro colori) e dall'altro ha richiesto alla teoria dei grafi di indagare su algoritmi e modelli di forte impatto applicativo. Nel giro di cinquant'anni la teoria dei grafi è diventata un capitolo della matematica molto sviluppato, ricco di risultati profondi e con forti influenze applicative.
Rappresentazione
In termini informali, per grafo si intende una struttura costituita da:[1]
collegamenti tra i vertici; tali collegamenti possono essere:
non orientati (cioè dotati di una direzione, ma non dotati di un verso): in questo caso sono detti spigoli, e il grafo è detto "non orientato";
orientati (cioè dotati di una direzione e di un verso): in questo caso sono detti archi o cammini, e il grafo è detto "orientato" o digrafo;
eventuali dati associati a nodi e/o collegamenti; un grafo pesato è un esempio di grafo in cui a ogni collegamento è associato un valore numerico, detto "peso".
Un grafo viene generalmente raffigurato sul piano da punti o cerchietti, che rappresentano i nodi; i collegamenti tra i vertici sono rappresentati da segmenti o curve che collegano due nodi; nel caso di un grafo orientato, il verso degli archi è indicato da una freccia.
Esempio di grafo orientato
Esempio di grafo pesato
Il posizionamento dei nodi e la forma degli archi o spigoli è irrilevante, dal momento che a contare sono solo i nodi e le relazioni tra essi. In altri termini, lo stesso grafo può essere disegnato in molti modi diversi senza modificarne le proprietà.
Per un approfondimento sulla terminologia specifica della teoria dei grafi, si può consultare il glossario di teoria dei grafi.
Applicazioni
Le strutture che possono essere rappresentate da grafi sono presenti in molte discipline e molti problemi di interesse pratico possono essere formulati come questioni relative a grafi. In particolare, le reti possono essere descritte in forma di grafi. Ad esempio, la struttura dei link di Wikipedia, come tutti gli ipertesti, può essere rappresentata da un grafo orientato, dove i vertici sono gli articoli e gli archi rappresentano l'esistenza di un collegamento da un articolo all'altro.
