grafi, teoria dei

grafi, teoria dei

grafi, teoria dei settore della matematica che studia in modo formalizzato i grafi, riconducendo a un’unica teoria diversi problemi classici: dal problema dei → ponti di Königsberg a quello dei → quattro colori, dal problema del → commesso viaggiatore a questioni di topologia discreta riguardanti la migliore disposizione di uno schema di connessioni, a problemi di → cammino minimo (→ grafo). Poiché l’→ albero è un particolare grafo, la teoria dei grafi abbraccia anche questioni relative alla costruzione di algoritmi e strutture di dati. Da un punto di vista matematico i grafi sono oggi collegati alla combinatoria (la cosiddetta matematica discreta), alla topologia, alla teoria degli algoritmi, alla teoria dei nodi. L’efficacia pratica della teoria dei grafi dipende dalla possibilità di rappresentazione che essa offre, da cui deriva, oltre al nome stesso di grafo, tutta la terminologia connessa.

La prima formulazione di un problema relativo ai grafi viene fatta risalire a Eulero. In una memoria del 1736 il grande matematico svizzero affrontava il problema “turistico-ricreativo” di come compiere una passeggiata nella città di Königsberg, che si sviluppa sulle due rive e sulle due isole del fiume Pregel, attraversando una e una sola volta i 7 ponti che ne collegano i quartieri: si tratta del già menzionato problema dei ponti di Königsberg. Eulero arrivò alla conclusione che il problema non ammette soluzione schematizzandolo in forma di grafo e dimostrando che il grafo non ammette un ciclo che passa esattamente una volta su ogni arco (ciclo euleriano). Più di un secolo dopo, nel 1859, affrontando un altro rompicapo, quello del dodecaedro del viaggiatore, il matematico e fisico irlandese W.R. Hamilton introdusse nei grafi il cammino passante per ciascun nodo o vertice una e una sola volta, detto appunto ciclo di Hamilton. Lo stesso Hamilton si occupò anche del già ricordato problema dei quattro colori, problema classico della cartografia, che consiste nel chiedersi qual è il numero minimo di colori necessario e sufficiente per colorare i vari compartimenti di una figura aventi in comune alcuni tratti del contorno.

Altri matematici e fisici nel corso dell’Ottocento contribuirono in maniera pionieristica allo sviluppo di queste ricerche utilizzando concetti che sarebbero stati in seguito unificati nella teoria dei grafi: da A. Cayley, che li impiegò per studiare la numerazione degli isomeri dei composti chimici (1875), all’avvocato Alfred Bray Kempe (1849-1922), appassionato di musica e matematica, e a P.J. Heawood che formularono in modo rigoroso il problema dei quattro colori, risolvendone alcuni aspetti (1880, 1890). Tutti questi iniziali studi sui grafi hanno in comune la stilizzazione di un problema concreto mediante un grafo formato da punti e linee e la ricerca di possibili soluzioni tramite riflessioni sullo schema grafico associato al problema di partenza.

Nel corso del Novecento sono state sviluppate numerose elaborazioni e applicazioni della teoria dei grafi. Tra i contributi più rilevanti si segnalano: la completa caratterizzazione dei grafi piani o planari a opera di K. Kuratowski (1930); gli studi su problemi di cammino ottimo (A. Sainte-Laguë, 1926; A.W. Tucker, 1937); le ricerche su grafi particolari come gli alberi (G. Birkhoff, 1946) e sui cicli hamiltoniani (W.T.T. Tutte, 1946; S. Johnson, G. Dantzig e D.R. Fulkerson, 1954, problema del ciclo hamiltoniano ottimo o del commesso viaggiatore); la pubblicazione di trattati e testi sistematici a opera di D. König (1936), C. Berge (1958), O. Ore (1962), F. Harary (1969), considerato quest’ultimo il padre della moderna teoria dei grafi e noto con il soprannome di «Mr Graph Theory», e P. Erdős, cui si devono a partire dal 1961 studi trentennali su classi di problemi su grafi.

Oltre ad aver conosciuto importanti sviluppi matematici, nel secondo Novecento la teoria dei grafi ha trovato applicazioni in innumerevoli campi, specie nella risoluzione di problemi di pianificazione e ottimizzazione: dalla ricerca operativa alla viabilità e ai trasporti, dalle catene produttive alla distribuzione, dalla rappresentazione di strutture in fisica e chimica a quella di organigrammi istituzionali e aziendali, dalla progettazione urbanistica e architettonica alle scienze sociali per lo studio delle strutture e relazioni sociali, dalle reti digitali e di telecomunicazioni ai sistemi esperti e alle reti neurali. Lo sviluppo della metodologia dei grafi è proceduto di pari passo con l’informatica teorica e la crescita dei mezzi di elaborazione: i sistemi digitali di calcolo, i circuiti logici e le strutture di dati di un elaboratore, le reti di computer e persino le istruzioni di un programma di calcolo sono rappresentabili con grafi.