Teoria dei grafi

Da Wikipedia, l'enciclopedia libera.

Un diagramma di un grafo con 6 vertici e 7 archi.

In matematica, e più in particolare in calcolo combinatorio i grafi sono oggetti discreti che permettono di schematizzare una grande varietà di situazioni e di processi e spesso di consentire di analizzarli in termini quantitativi ed algoritmici.

In termini informali, per grafo si intende una struttura costituita da:

oggetti semplici, detti vertici (vertices) o nodi (nodes),
collegamenti tra i vertici. I collegamenti possono essere:
- orientati, e in questo caso sono detti archi (arcs), e il grafo è detto orientato
- non orientati, e in questo caso sono detti spigoli (edges), e il grafo è detto non orientato
- eventualmente dati associati a nodi e/o collegamenti

Per una definizione formale, vedi grafo.

Un grafo viene generalmente raffigurato sul piano da punti o cerchietti, che rappresentano i nodi, e da segmenti o curve che collegano due nodi che rappresentano gli archi o gli spigoli. In questo caso, il posizionamento dei nodi e la forma degli archi o spigoli è irrilevante, contano solo i nodi e le relazioni tra di loro. In altri termini, lo stesso grafo può essere disegnato in molti modi diversi senza modificare le sue proprietà.

Per un'approfondimento sulla terminologia specifica della teoria dei grafi, si può consultare il Glossario di teoria dei grafi.

Le strutture che possono essere rappresentate da grafi sono onnipresenti 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 della Wikipedia, come tutti gli ipertesti, può essere rappresentata da un grafo orientato, dove i vertici sono gli articoli e gli archi rappresentato l'esistenza di un link tra un articolo e l'altro. I grafi orientati sono anche utilizzati per rappresentare le macchine a stati finiti e molti altri formalismi, ad esempio diagrammi di flusso, catene di Markov, schemi entità-relazione, reti di Petri e molti altri.

Lo sviluppo di algoritmi per maneggiare i grafi è una delle aree di maggior interesse dell'informatica.

[modifica] Storia

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.

Nel XIX secolo si è posto e discusso il problema dei quattro colori, rivelatosi molto impegnativo e risolto solo nella seconda metà del XX secolo. Si è anche introdotto il problema dei cammini hamiltoniani. Fino a metà del XX secolo poco altro si è scoperto.

Nella seconda metà del XX secolo gli studi e i risultati si sono sviluppati ampiamente, in sintonia con i forti sviluppi della combinatorica e del calcolo automatico. Il computer da un lato ha consentito di sviluppare indagini sperimentali sui grafi (usate in particolare per dimostrare il 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.