Teoria dei grafi

Da Wikipedia, l'enciclopedia libera.
Un diagramma di un grafo con 6 vertici e 7 spigoli.

In matematica, informatica e, più in particolare, geometria combinatoria, la teoria dei grafi si occupa di studiare i grafi, che sono oggetti discreti che permettono di schematizzare una grande varietà di situazioni e di processi e spesso di consentirne delle analisi in termini quantitativi e algoritmici.

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

Rappresentazione[modifica | modifica wikitesto]

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

  • oggetti semplici, detti vertici o nodi,
  • collegamenti tra i vertici; tali collegamenti possono essere:
    • orientati: in questo caso sono detti archi o cammini, e il grafo è detto "orientato"
    • non orientati: in questo caso sono detti spigoli, e il grafo è detto "non orientato"
    • eventuali dati associati a nodi e/o collegamenti.

Un grafo viene generalmente raffigurato sul piano da punti o cerchietti, che rappresentano i nodi; archi o spigoli sono rappresentati da segmenti o curve che collegano due nodi. 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à.

Applicazioni[modifica | modifica wikitesto]

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, come ad esempio diagrammi di flusso, catene di Markov, schemi entità-relazione, reti di Petri e molti altri.

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

Storia[modifica | modifica wikitesto]

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 è stato posto e discusso il problema dei quattro colori, rivelatosi molto impegnativo e risolto solo nella seconda metà del XX secolo. È stato anche introdotto il problema dei cammini hamiltoniani. Fino a metà del XX secolo poco altro è stato scoperto.

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.

Note[modifica | modifica wikitesto]

  1. ^ Per una definizione formale, si veda alla voce «grafo».

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Controllo di autorità LCCN: (ENsh85056471 · GND: (DE4113782-6
matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica