teoria dei grafi

teoria dei grafi

Lo studio delle proprietà combinatorie, topologiche, probabilistiche ecc. dei grafi, sviluppatosi come teoria matematica autonoma negli anni Trenta del Novecento a opera di Dénes Koenig, Hassler Whitney, Oystein Ore e altri. Esempi di grafi finiti o infiniti si trovano ovunque: diagrammi, strutture ad albero ecc. Un grafo è un oggetto relativamente semplice. Una definizione formale è quella di dare un grafo come una coppia (V,E) dove V è un insieme non vuoto, i cui elementi sono detti vertici, ed E è un sottoinsieme del prodotto cartesiano V×V, i cui elementi vengono detti lati. I lati possono essere orientati se viene assegnato un vertice iniziale e uno finale oppure possono essere non-orientati, quando non si distingue tra l’inizio e la fine. Ogni grafo – come provato da Casimir Kuratowski – si può rappresentare nello spazio tridimensionale in modo che i vertici siano punti, gli spigoli curve di Jordan, così che i punti d’intersezione tra le curve siano punti corrispondenti a vertici connessi; tuttavia le proprietà interessanti dei grafi non sono solo quelle topologiche. Molti problemi algebrici, probabilistici, logici si possono tradurre in termini di proprietà dei grafi. Per es., problemi riguardanti l’esistenza di cammini chiusi che godono di particolari proprietà, quali quella di passare per tutti i vertici una e una sola volta (grafi hamiltoniani) o di passare una e una sola volta per ogni spigolo (grafi euleriani). Quest’ultimo è il caso del famoso problema dei ponti di Königsberg, risolto da Leonhard Euler nel 1736, in cui ci si chiedeva se fosse possibile passare una e una sola volta per i sette ponti della città. Nell’affrontare in termini generali la questione Euler introdusse diversi concetti fondamentali della teoria. Egli schematizzò il problema come segue: dato un grafo qualsiasi (insieme finito di vertici collegati da vari lati), stabilire se sia possibile determinare un percorso che partendo da uno dei vertici attraversi tutti i lati una e una sola volta. Da allora la teoria dei grafi ha subito un sorprendente sviluppo con applicazione a vari settori delle scienze, in particolare i legami con le reti elettriche, le passeggiate aleatorie, le catene di Markov, i polinomi dei nodi e le funzioni di partizioni della fisica teorica. Altri problemi riguardano gli accoppiamenti tra parti disgiunte dell’insieme dei vertici che utilizzino spigoli del grafo; altri ancora le rappresentazioni planari dei grafi o problemi di colorazione. Famoso tra questi è il problema dei quattro colori, che chiede se è sempre possibile colorare tutti i vertici di un grafo (finito o infinito) con soli quattro colori in modo che vertici adiacenti abbiano colori distinti. Presentato per la prima volta nel 1852, il problema è stato finalmente risolto nel 1977 da Kenneth Appell e Wolfgang Haken mediante una dimostrazione che (pur notevolmente semplificata in seguito) richiede il ricorso a verifiche via computer. Fondamentali in un’altra direzione sono le ricerche iniziate da Paul Erdös sui grafi casuali (random graphs), che introducono metodi probabilistici nello studio dei grafi e hanno trovato interessanti applicazioni anche nella teoria dei modelli.

→ Informatica teorica; Logica matematica; Matematica: problemi aperti