grafo Nel linguaggio scientifico, struttura relazionale formata da un insieme finito di oggetti detti nodio vertici, e da un insieme di relazioni tra coppie di oggetti dette archio spigoli. Per indicare un g. viene utilizzata una notazione del tipo: G(N, A), dove N indica l’insieme dei nodi e A l’insieme degli archi. Se vengono indicati con i e j due nodi del g., un arco che congiunge i a j viene spesso indicato con la notazione (i, j).
È, per es., possibile rappresentare come un g.: una rete telefonica in cui i nodi rappresentano gli utenti e i punti di smistamento e gli archi i cavi di collegamento tra i nodi; un circuito elettrico in cui i nodi rappresentano i punti di giunzione e gli archi i collegamenti elettrici; una rete stradale in cui i nodi rappresentano gli incroci e gli archi le strade; un impianto idraulico in cui i nodi rappresentano le giunzioni e gli archi i tubi; una rete di elaboratori in cui i nodi rappresentano gli elaboratori connessi in rete e gli archi le linee di comunicazione tra di essi; un programma di calcolo in cui i nodi rappresentano le istruzioni ed esiste un arco tra due nodi se le relative istruzioni possono essere eseguite nel programma in successione; una struttura dati in cui i nodi rappresentano i dati e gli archi i legami tra i dati realizzati tramite puntatori. Nel caso di un programma di calcolo o di una rete stradale, in cui tutte le strade sono a senso unico, gli archi del g. potranno essere percorsi in una sola direzione; nel caso invece di una rete idraulica i collegamenti sono tipicamente bidirezionali (a meno che nell’impianto esistano valvole).
1. Sviluppi della teoria dei grafi
L’origine storica della teoria del g. è in genere fatta risalire a una memoria di L. Eulero del 1736, nella quale veniva formulato il famoso problema dei sette ponti di Königsberg: attraverso Königsberg scorre il fiume Pregel e, in mezzo al fiume, vi sono due isole (che indichiamo con A e B e le due rive del fiume con C e D; fig. 1), collegate fra loro da un ponte; inoltre quattro ponti (due per parte) collegano l’isola A alle due rive e due ponti (uno per parte) collegano l’isola B alle due rive; il problema consiste nel decidere se sia possibile, partendo da un qualsiasi punto, camminare attraverso ogni ponte esattamente una volta, ritornando al punto di partenza.
Nel 1771 anche A.-T. Vandermonde trattò il problema del ciclo hamiltoniano. Nell’Ottocento vennero sviluppati importanti capitoli della teoria dei g.: nel 1813 A.-L. Cauchy enunciò in termini di g. alcuni problemi; su poliedri nel 1840 A.F. Möbius formulò la congettura dei 4 colori; nel 1847 G.R. Kirchhoff sviluppò la teoria delle reti elettriche; nel 1856 W.R. Hamilton elaborò alcuni procedimenti di calcolo basandosi su g. e T.P. Kirkman studiò alcune proprietà dei cicli hamiltoniani; nel 1875 e nel 1878 A. Cayley e J.J. Sylvester svilupparono alcuni aspetti della teoria dei g. per lo studio degli isomeri chimici; nel 1880 e nel 1890 A.B. Kempe e P.J. Heawood formularono in modo rigoroso il problema dei 4 colori e ne risolvettero alcuni aspetti; nel 1882
Nel corso del Novecento sono state sviluppate numerose elaborazioni e applicazioni basate sulla teoria dei grafi. Fra i risultati più significativi ricordiamo: nel 1900 il trattato di H. Pointcaré, Sécond complément à l’analysis situs; nel 1926 A. Sainte-Laguë studiò problemi di cammino ottimo e K. Kuratowski trovò una caratterizzazione completa dei g. planari; nel 1935 P. Hall affrontò alcuni problemi di matematica combinatoria legati ai g.; G. Polya ricollegò le caratteristiche di alcuni g. a relazioni chimiche, e H. Whitney a sistemi di equazioni lineari; nel 1936 D. König scrisse il primo trattato sistematico sui g. e, insieme a J. Egervàry, trovò importanti proprietà; nel 1937 A.W. Tuker sviluppò ulteriormente alcuni problemi di cammino ottimo; nel 1940 G.B. Dantzig, che più tardi proporrà il metodo del simplesso per risolvere problemi di programmazione lineare, affrontò alcuni problemi di assegnamento su g.; nel 1944 J.L. von Neumann con O. Morgenstern pubblicò un trattato di
Lo sviluppo e la diffusione di queste metodologie è dovuto principalmente al parallelo sviluppo dei mezzi di elaborazione. Il motivo dell’interesse dell’informatica per i modelli combinatori in generale, e la teoria dei g. in particolare, è evidente, in quanto i sistemi digitali di calcolo sono sistemi discreti e quindi rappresentabili con g.; i
G. orientatoG. in cui gli archi rappresentano relazioni tra coppie ordinate di nodi. In questo caso gli archi hanno una ‘testa’ o nodo di arrivo e una ‘coda’ o nodo di partenza (fig. 2A); se invece le relazioni sono tra coppie non ordinate, il g. è detto non orientato. Un nodo i di un g. orientato è detto predecessoredi un nodo j se esiste un arco diretto da i a j; è detto successore di j se esiste un arco diretto da j a i. Multigrafo G. in cui esistono più archi fra la stessa coppia di nodi (fig. 2B), oppure fra una stessa coppia ordinata. Sottografo, g. parziale e copertura di un g. Dato un g. non orientato G(N, A) e un g. non orientato H(V, E) con V appartenente a N ed E appartenente a A, tale che gli archi di E sono tutti gli archi di A aventi entrambi i nodi terminali nell’insieme V, H è detto sottografo di G (fig. 2C). Se invece E è formato solo da un sottoinsieme degli archi di A con entrambi i nodi terminali nell’insieme V, allora H è detto g. parziale di G (fig. 2D). Si dice che un g. G ‘copre’ un altro g. H, se H è un g. parziale di G. G. connesso G. in cui per ogni coppia di nodi esiste un percorso che li congiunge (fig. 3A). Nel caso di g. orientati, se esiste un cammino fra ogni coppia di nodi, si dice che il g. è fortemente connesso (fig. 3B); se esiste solo un cammino non orientato fra ogni coppia di nodi, si dice che il g. è debolmente connesso (fig. 3C). Un sottografo di un g. G connesso e tale che non esistano archi di G tra i nodi del sottografo e i nodi non appartenenti al sottografo è detto componente connessa di G. Un nodo i di un g. non orientato è detto adiacente a un nodo j se esiste l’arco (i, j); se il nodo non ha nodi adiacenti è detto isolato; se l’arco (i, j) esiste, esso è detto incidente sui nodi i e j. Due archi con almeno un nodo in comune sono detti archi adiacenti. Un g. (orientato o non orientato) tale che per ogni coppia (i, j) esiste un arco è detto completo (fig. 3D). Un g. orientato G(N, A) tale che se (i, j) appartiene ad A allora anche (j, i) appartiene ad A è detto simmetrico (fig. 3E). Se invece per ogni coppia non ordinata (i, j) esiste al più uno solo dei due archi (i, j) e (j, i), allora il g. è detto antisimmetrico. Dato un g. G(N, A) non orientato, un sottoinsieme di nodi S appartenente a N tale che il sottografo indotto sia privo di archi è detto insieme stabile, o anche insieme indipendente. Se invece il sottografo indotto da S forma un g. completo è detto clique. La cardinalità di un insieme stabile con il massimo numero di nodi è detta numero di stabilità del g.; la cardinalità della clique con il massimo numero di nodi è detta numero di clique del grafo. G. bipartito G. in cui l’insieme N dei nodi può essere diviso in due parti S e T tali che non esistono archi con entrambi i nodi terminali in S, né archi con entrambi i nodi terminali in T; tutti gli archi hanno quindi un nodo terminale in S e uno in T (fig. 3F). Un g. è bipartito se e solo se non ha cicli con un numero dispari di archi. G. planare G. che è possibile disegnare su di un piano senza che gli archi debbano intersecarsi. Se un g. contiene un sottografo completo di 5 nodi, spesso indicato con la notazione K 5 (fig. 3G), o un sottografo bipartito completo di 6 nodi con 3 nodi in ognuna delle due parti, spesso indicato con la notazione K 3,3 (fig. 3H), allora non può essere planare.
In un g. non orientato è un insieme ordinato di archi (a 1 , a 2 , a 3 , ..., an). In un g. orientato vi sono due tipi di cammini: il primo, chiamato cammino non orientato, o anche catena, non pone vincoli sull’orientamento degli archi; il secondo tipo, detto semplicemente cammino, richiede che la sequenza di archi sia tale che la testa di un arco coincida con la coda del successivo, vale a dire che sia possibile percorrere il cammino seguendo sempre il verso di percorrenza degli archi. Se un cammino non passa mai due volte per lo stesso nodo è detto cammino elementare, se non passa mai due volte per lo stesso arco è detto cammino semplice. Ciclo di un g. È un cammino tale che il nodo di partenza e quello di arrivo coincidono. Se il ciclo non passa mai due volte per lo stesso nodo è detto ciclo elementare. Nel caso di g. orientati, un ciclo formato da archi orientati in entrambi i due possibili versi di percorrenza è detto ciclo non orientato. Dato un g. o un multigrafo (orientato o non orientato), un ciclo che passa esattamente una volta per ogni arco è detto ciclo euleriano, un ciclo che passa esattamente una volta per ogni nodo è detto ciclo hamiltoniano. Un g. che ammette un ciclo euleriano è detto g. euleriano (fig. 3I). Un g. che ammette un ciclo hamiltoniano è detto hamiltoniano (fig. 3L). Condizione necessaria e sufficiente affinché un g. connesso non orientato sia euleriano è che tutti i suoi nodi abbiano grado pari (teorema di Eulero, 1736). Un g. orientato privo di cicli è detto aciclico. Nel caso di g. non orientati, sorge il problema che, potendo percorrere un arco in entrambi i sensi, un singolo arco forma un ciclo. Per evitare tale paradosso, in genere si vincola il ciclo a non utilizzare mai due volte uno stesso arco. Si definisce quindi ciclo una sequenza ordinata di archi distinti, tale che il nodo di partenza e quello di arrivo coincidono.
4. Grado, centro, raggio e diametro del grafo
Dato un g. non orientato, il numero di archi incidenti su di un dato nodo è detto grado del nodo. Se in un g. tutti i nodi hanno lo stesso grado k, il g. è detto regolare di grado k; se inoltre k=3, il g. è detto cubico. Per i g. orientati si può definire un grado di ingresso del nodo i come numero di archi entranti in i, e un grado di uscita di i come numero di archi uscenti. Dato un g. G(N, A) non orientato, sia d(i, j) il numero minimo di archi necessario per costruire un cammino da i a j. Si dice diametro del g. la quantità D=max d(i, j). Si dice centro del g. il nodo (o i nodi) per cui è minima la quantità R(i)=maxj d(i, j). Se k è il nodo centro (o uno dei nodi centrali) del g., il valore R(k) è detto raggio del grafo.
È un g. non orientato connesso e senza cicli (o anche, in modo del tutto equivalente, un g. connesso e senza cicli); un g. connesso con n nodi e n−1 archi; un g. senza cicli con n nodi e n−1 archi; un g. senza cicli tale che comunque si aggiunga un arco si crea un ciclo (e uno solo); un g. connesso tale che comunque si elimini un arco si ottiene un g. non connesso; un g. tale che per ogni coppia di nodi esiste esattamente un cammino che li collega. In un albero, i nodi di grado uguale a uno sono detti foglie. Scelto un nodo dell’albero, e denominato tale nodo radice, è possibile introdurre il concetto di livellodi un nodo come il numero di archi che è necessario percorrere per raggiungere la radice (la radice ha quindi livello zero). Il livello più elevato è detto profonditàdell’albero e dipende naturalmente dalla radice scelta. Togliendo da un albero uno o più archi si ottiene un insieme di alberi non connessi detto foresta. Nel caso di g. orientati valgono le stesse definizioni sostituendo ai termini ‘ciclo’ e ‘cammino’ le locuzioni ‘ciclo non orientato’ e ‘cammino non orientato’. Spesso, nel caso di g. orientati, gli alberi vengono denominati arbusti o arborescenze; l’equivalente di una foresta viene denominato boscaglia. Un albero in cui tutti i nodi hanno grado minore o uguale a tre, è detto albero binario (fig. 3M). Gli alberi binari sono di particolare importanza nelle applicazioni informatiche e nella
6. Colorazione di g. e numero cromatico
Una colorazione di un g. è una assegnazione di colori ai suoi nodi in modo tale che due nodi adiacenti (cioè fra i quali esista un arco) non siano mai colorati con lo stesso colore. L’insieme di tutti i nodi colorati con lo stesso colore è detta classe di colorazione. Una k-colorazione di un g. è una colorazione che usa k colori e suddivide quindi i nodi in k classi. Il numero cromatico di un g. è definito come il minimo k per cui esiste una k-colorazione del grafo. Uno dei più famosi problemi matematici rimasto aperto per oltre un secolo è il cosiddetto problema dei quattro colori (➔ colore), legato al problema della colorazione di carte geografiche. Secondo tale congettura ogni g. planare è 4-colorabile. Questa congettura, nota fino dagli inizi dell’Ottocento, è stata in seguito provata con tecniche enumerative, utilizzando in modo massiccio potenti calcolatori.