GRAFO
GRAFO
. Con linguaggio informale, si può dire che un g. è formato da certe entità (vertici) e da certi collegamenti fra queste (spigoli o archi): s'intende che ciascuno spigolo collega due vertici. I collegamenti possono essere "orientati", nel senso che fra le due entità collegate se ne distingue una iniziale e una finale, o "non orientati". Se tutti i collegamenti sono non orientati, si parla di "g. non orientato"; se sono tutti orientati, si parla di "g. orientato"; se ve ne sono di entrambi i tipi, di "g. misto". Togliendo le orientazioni, un g. orientato o misto diviene non orientato. Le figg.1, A e B rappresentano rispettivamente un g. orientato e uno misto, i quali, togliendo le orientazioni, dànno luogo al g. non orientato della fig. 1, C. Solitamente, come nella fig.1, i g. si rappresentano in forma geometrica, le "entità" essendo date da punti del piano e i "collegamenti" da linee che li uniscono. È bene fare attenzione a non attribuire al g. stesso proprietà che sono invece della sua rappresentazione geometrica, come la posizione effettiva dei vertici, la forma e la lunghezza degli spigoli, e così via.
In termini più precisi, una struttura di g. orientato si definisce come una terna (V,S,f), dove V e S sono insiemi i cui elementi si dicono rispettivamente vertici e spigoli e f è un'applicazione (App. III, 1, p. 115) di S nell'insieme V2 avente per elementi le coppie ordinate di elementi di V. Se allo spigolo x la f associa la coppia (a,b) di vertici, a si dice estremo iniziale (o primo vertice) e b estremo finale (o secondo vertice). Per una struttura di g. non orientato si può dare una definizione analoga, sostituendo a V2 l'insieme V delle coppie non ordinate di elementi di V. Non si fa dunque distinzione fra i due estremi d'uno spigolo (nel caso dei g. non orientati si parla più frequentemente di spigoli anziché di archi). Non tratteremo qui dei g. misti. I vertici a e b si dicono "adiacenti" se esiste uno spigolo di estremi a e b (se esso è orientato da a a b diremo che b è un successore di a). Abbiamo parlato di "struttura di g." (invece che di "grafo"), poiché gli stessi insiemi V e S possono venir dotati d'una struttura di g. orientato quanto d'una di g. non orientato; anzi, da una struttura di g. orientato se ne può dedurre una di g. non orientato semplicemente "togliendo" le orientazioni, cioè sostituendo a ogni coppia ordinata (a,b) la coppia non ordinata {a,b}, e tutte le considerazioni riferibili a una struttura di g. non orientato si possono anche applicare a un g. orientato (ma non viceversa). Per tale motivo, d'ora in poi parleremo di "proprietà di g. orientati" (proprietà che dipendono dall'orientazione).
Un esempio di g. è dato da un sistema di comunicazioni: le stazioni (o i porti, o gl'incroci) sono i vertici, i tratti fra questi gli spigoli (un tale g. è di regola non orientato). Anche una formula chimica di struttura si può considerare un g. non orientato (essa contiene inoltre le informazioni relative agli atomi della molecola). Lo schema di un'organizzazione, con i vari reparti e i collegamenti fra essi, è un grafo.
Le cosiddette "reti di trasporto" sono g. orientati, con un vertice che non è estremo iniziale di alcun arco e uno che non è estremo finale di alcun arco (sono detti rispettivamente vertice d'uscita e vertice d'entrata): a ciascun arco si associa un numero reale non negativo, detto la sua "capacità". Un "flusso" è un'applicazione di S nell'insieme dei numeri reali non negativi, tale che il flusso di ogni arco non superi la capacità e per ogni vertice intermedio la somma dei flussi in entrata sia uguale a quella dei flussi in uscita (una rete di trasporto simboleggia un sistema di comunicazioni con il quale si debbano trasferire certe merci da un insieme di località a un altro, simboleggiati rispettivamente dai vertici che seguono immediatamente quello d'entrata e da quelli che precedono immediatamente quello d'uscita). Il problema caratteristico d'una rete di trasporto è quello di trovare il flusso massimo.
Altri esempi di g. orientati sono i cosiddetti progetti, anche questi dotati d'un vertice d'entrata e d'un vertice d'uscita: ogni vertice rappresenta una certa azione volta a raggiungere, a partire dallo stato rappresentato dal vertice d'entrata, quello rappresentato dal vertice d'uscita. Gli archi dànno i possibili passaggi da un'azione a un'altra, a ciascuna delle quali è associato un numero che rappresenta il tempo necessario (o altra quantità, come il costo). Il problema consiste nella determinazione di una sequenza d'azioni che renda minimo il tempo (o il costo), fra tutte quelle che dallo stato iniziale portano allo stato finale.
Un g. si dice "finito" se tali sono gl'insiemi V e S. Uno spigolo i cui estremi coincidono si dice un "laccio" o "cappio". Due spigoli distinti si dicono "in parallelo" se hanno gli stessi estremi (nel caso d'un g. orientato debbono avere lo stesso estremo iniziale e lo stesso estremo finale: quindi può accadere che s e s′ non siano in parallelo in un g. orientato, e lo siano nel g. non orientato corrispondente). Un g. (orientato o non orientato) si dice "semplice" se è privo di lacci e di spigoli in parallelo.
Una relazione in un insieme I (essendo un insieme di coppie ordinate di elementi di I) si può considerare come un g. orientato in cui V = I mentre S è l'insieme delle coppie di elementi associati nella relazione: esso è privo di spigoli in parallelo. Le proprietà delle relazioni si traducono in proprietà dei g.: per es., la relazione è riflessiva se e solo se per ogni vertice del g. v'è un laccio.
Un "percorso" o "catena" è una sequenza (successione finita) v0, s1, v1, s2, ..., vn-1, sn, vn (vi ∈ V, si ∈ S), tale che gli estremi di si siano vi-1 e vi (se il g. è orientato, non importa quale sia il primo e quale il secondo). Se v0 = vn (n ≥ 1), il percorso si dice "ciclo". In un g. orientato, si dice "cammino" un percorso tale che vi-1 sia l'estremo iniziale e vi quello finale di si. Un cammino che sia anche un ciclo si dice "circuito". Un percorso che non impegni lo stesso spigolo più volte si dice "semplice", uno che non impegni due volte lo stesso vertice si dice "elementare".
Si dice "sottografo" del g. G "individuato da V′ ⊆ V" il g. formato dai vertici di V′ e dagli spigoli che li collegano in G (gli estremi d'uno spigolo sono gli stessi estremi che esso ha in G). Si dice grafo "parziale" di G un g. i cui vertici sono quelli di G, mentre gli spigoli sono alcuni degli spigoli di G. Un sottografo parziale di G si dirà anche "g. subordinato" a G. Nella fig. 2 è rappresentato un g. non orientato: le linee più grosse (sia continue sia tratteggiate) sono gli spigoli di un sottografo (individuato dai vertici 1,2,3,4) mentre quelle tratteggiate (sia grosse sia sottili) sono gli spigoli d'un g. parziale.
Un g. si dice "connesso" allorché, presi due vertici qualsiasi, esiste un percorso che ha per estremi tali vertici. (Per i g. orientati vi sono ulteriori tipi di connessione, per es., quella "forte", che si ha allorché, presi due vertici, esiste un cammino che inizia nel primo e termina nel secondo). In un g. non connesso G si distinguono le componenti connesse, che sono sottografi connessi massimali di G.
Sia n il numero dei vertici d'un g. finito, m quello degli spigoli e p quello delle sue componenti connesse. Il numero dei cicli "indipendenti)" (mediante i quali, cioè, si possono "costruire" gli altri), detto "numero ciclomatico", vale m − n + p. (Per es., nella fig. 1,C il ciclo formato degli spigoli s,u,v,r si può immaginare come componibile mediante i cicli s,t,r e t,v,u.).
Un "albero" è un g. connesso e privo di cicli (quindi m = n − 1). Tipico esempio è un albero genealogico, nel quale sono indicati i discendenti (o gli antenati) d'una persona fino a una certa generazione (tale g. potrebbe però non risultare un albero, nel caso di figli di consanguinei). Un albero genealogico è anzi orientato, a partire da un certo vertice, allontanandosi via via da questo (un albero orientato in questo modo si dice anche "arborescenza").
In un linguaggio naturale o matematico si può solitamente, per ogni espressione, rilevare una struttura ad albero, che rappresenta il modo in cui gli elementi (parole in un linguaggio naturale, costanti o variabili in un linguaggio matematico) si raggruppano in blocchi via via più complessi. Nella fig. 3 sono rappresentate le strutture ad albero di una semplice frase italiana e di un'espressione algebrica: ogni vertice rappresenta un blocco di termini (per es., un vertice rappresenta l'espressione parziale "a + 2b").
Il g. parziale connesso (d'un dato g. connesso) che abbia il minimo numero di spigoli è un albero (un caso particolare di questo problema: dato un sistema di linee di comunicazione fra certe località, scegliere quelle linee che siano in numero minimo e permettano di collegare tutte le località, in modo diretto o indiretto).
Un ciclo (o una catena, o un circuito, o un cammino) d'un g. finito si dice "euleriano" se in esso ogni spigolo figura una e una sola volta, "hamiltoniano" se ogni vertice figura una e una sola volta.
Come dimostrò Eulero, condizione necessaria e sufficiente affinché un g. finito ammetta un ciclo euleriano è che esso sia connesso e il "grado" di ogni vertice (cioè il numero degli spigoli di cui quel vertice è estremo) sia pari. Invece, esiste una catena euleriana che non sia un ciclo se e solo se il g. è connesso e tutti i vertici, meno due, hanno grado pari (quei due debbono avere grado dispari). Per i g. infiniti, si possono introdurre concetti analoghi, ma la condizione non è più sufficiente. In un g. orientato v'è un circuito euleriano allorché per ogni vertice vi sono tanti spigoli "in entrata" quanti ve ne sono "in uscita".
Non si conosce invece una condizione necessaria e sufficiente affinché un g. ammetta un ciclo hamiltoniano.
Come per le altre strutture matematiche, anche per quelle di g. orientato e non orientato si definiscono gli omomorfismi e gl'isomorfismi: in termini approssimativi, si potrebbero dire le applicazioni, o rispettivamente le biiezioni, che conservano le "adiacenze". Si possono dare due definizioni leggermente diverse anche nella sostanza.
Siano date le strutture di g. non orientato G = (V,S,f) e G′ = (V′,S′,f′)
1) Un omomorfismo è una coppia di applicazioni, ϕ di V in V′ e ψ di S in S′, tali che gli estremi di ψ (s) siano le immagini in ϕ degli estremi di s (per ogni s ∈ S).
2) Un omomorfismo è un'applicazione Ψ di V ⋃ S in V′ ⋃ S′ tale che a un vertice corrisponda un vertice, e a uno spigolo s di estremi v1 e v2 corrisponda uno spigolo di estremi Ψ (v1) e Ψ (v2) oppure un vertice Ψ (s) = Ψ (v1) = Ψ (v2).
In una trasformazione del tipo 1) uno spigolo si trasforma necessariamente in uno spigolo, mentre in una del tipo 2) un intero sottografo di G può essere portato in un vertice di G′.
Per le strutture di g. orientato si dànno definizioni analoghe, nelle quali si chiede che il primo (rispettivamente il secondo) vertice d'uno spigolo si trasformi nel primo (nel secondo) vertice del corrispondente (se questo è uno spigolo).
Se non vi sono spigoli in parallelo, ogni spigolo è individuato dalla coppia (ordinata nel caso d'un g. orientato, non ordinata in quello d'un g. non orientato) dei suoi vertici, e quindi per dare un omomorfismo è sufficiente indicare come esso opera sui vertici: si dice allora che un'applicazione ϕ di V in V′ "è" un omomorfismo se trasforma vertici adiacenti in vertici adiacenti.
Un "isomorfismo" tra g. è un omomorfismo definito da biiezioni (anche le biiezioni inverse definiscono un omomorfismo). Un "automorfismo" d'un g. è un isomorfismo su sé stesso. Per es., il g. della fig.1,C ammette, oltre l'identità, i seguenti automorfismi (sotto ogni elemento è scritto il corrispondente):
Definizioni analoghe valgono per i g. orientati. Gli automorfismi d'un g. (orientato o no) formano un gruppo.
Un altro importante carattere d'un g. è il "numero cromatico". Si dice "colorazione" d'un g. un'applicazione dell'insieme dei vertici in un insieme K, i cui elementi si dicono "colori", tale che due vertici adiacenti abbiano colori diversi. (In una carta geografica politica, prendiamo un vertice per ogni stato e uno spigolo per ogni coppia di stati che abbiano un tratto di confine in comune: i territori di stati confinanti debbono colorarsi in modo diverso, e quindi si ha a che fare con una colorazione del g. or ora definito). Il minimo numero di colori necessari per colorare i vertici d'un g. si dice "numero cromatico" del grafo. Il numero cromatico k d'un g. connesso non supera il massimo dei gradi dei suoi vertici, fatta eccezione per i g. formati da un ciclo di lunghezza dispari, nel qual caso k = 3, e per quelli in cui due vertici qualsiasi sono collegati (per essi k uguaglia il numero dei vertici); inoltre nel g. si può trovare una catena contenente k vertici, colorati con colori differenti. Un g. ha numero cromatico ≤ 2 se tutti i suoi cicli hanno un numero pari di spigoli. Un tale g. si dice anche "bipartito", poiché i suoi vertici si possono ripartire in due classi tali che due vertici della stessa classe non siano adiacenti (ciascuna delle due classi è formata dai vertici che, in una colorazione, hanno ugual colore). Dette V1 e V2 le due classi di vertici d'un g. bipartito senza spigoli in parallelo, quest'ultimo si può considerare come rappresentativo di una relazione fra due insiemi, rappresentati da V1 e V2.
Un "couplage" d'un g. è un insieme di spigoli che a due a due non hanno estremi in comune. Consideriamo un g. bipartito, nel quale i vertici della prima classe rappresentano alcuni posti di lavoro, mentre quelli della seconda alcuni aspiranti e gli spigoli segnalano che un aspirante è qualificato per un certo posto. Una qualsiasi scelta di personale è un couplage del grafo. Il problema più importante è quello di trovarne uno massimo, cioè che impegni il massimo numero possibile di spigoli.
Un "g. topologico" è un g. avente per vertici punti di una superficie e per spigoli linee congiungenti a due a due tali punti, con la condizione che due linee non abbiano intersezioni all'infuori di quelle che provengono da un (eventuale) vertice in comune. Si parlerà dunque di g. topologico (o semplicemente di g.) tracciato su una certa superficie.
Sia dato un g. finito G tracciato in un piano o su una superficie sferica: ogni suo ciclo è una linea chiusa e dà luogo a due regioni. Può darsi che queste contengano altre regioni, contornate da altri cicli; ma, argomentando su ciascuna di esse, si trovano infine alcune regioni, contornate da cicli, che non ne contengono altre. Esse si dicono "facce" del grafo. Per es., se pensiamo al g. della fig.1,C come un g. topologico tracciato nel piano, le facce sono le regioni contornate dalle sequenze di spigoli (r,s,t) e (t,u,v), oltre alla "faccia infinita" esterna alla sequenza (r,s,u,v). Consideriamo un nuovo grafo G* avente un vertice per ogni faccia di G e uno spigolo per ogni coppia di facce di G aventi uno spigolo in comune: esso si dice "duale" di G (a sua volta G è duale di G*). Se m*, n*, f* sono rispettivamente il numero degli spigoli, quello dei vertici e quello delle facce di G, e m*, n* e f* gli analoghi numeri relativi a G*, abbiamo
I vertici, gli spigoli e le facce d'un poliedro si possono considerare come gli omonimi elementi d'un g. tracciato su una superficie sferica. Vale quindi la formula citata, e in base a questa si può provare che esistono solo cinque tipi di poliedri tali che in ciascun vertice confluisca lo stesso numero di spigoli e ciascuna faccia abbia lo stesso numero di lati: sono, a meno di trasformazioni topologiche, i cinque "poliedri regolari platonici".
Si dice che un g. è tracciabile su una superficie S se è isomorfo a un g. topologico tracciato su S. Si dice "planare" un g. tracciabile su un piano (questa è una proprietà che riguarda un g. qualsiasi, non solamente un g. topologico). Un g. planare finito è isomorfo a un g. finito tracciabile su una superficie sferica, e viceversa (si passa da un piano a una superficie sferica mediante una proiezione stereografica, v. XXXI, p. 567). Un g. è planare se e solo se, aboliti tutti i vertici di grado 2 (se il vertice a è collegato solamente con b e con c, lo si abolisce e si sostituiscono ai relativi spigoli uno spigolo di estremi b e c), esso non contiene sottografi parziali isomorfi al g. "pentagonale" (formato da 5 vertici collegati in tutti i modi possibili) o al grafo "esagonale" (formato da 6 vertici a,b,c,d,e,f e dagli spigoli {a,b}, {b,c}, {c,d}, {d,e}, {e,f}, {f,a}, {a,d}, {b,e}, {c,f}).
Vi sono notevoli relazioni fra il numero cromatico d'un g. e la sua tracciabilità su una superficie. È noto che il numero cromatico d'un g. planare non supera 5: non sono però stati trovati g. planari di numero cromatico 5. È questo il celebre "problema dei quattro colori". Per g. tracciabili su superfici più complesse, l'analogo problema è stato risolto: per es., il numero cromatico d'un g. tracciabile su un toro (superficie ottenuta facendo ruotare una circonferenza intorno a una retta complanare esterna) non supera 7, ed è noto un esempio di g. che richiede 7 colori.
Il "genere" d'un g. è il più piccolo numero g tale che il g. sia tracciabile su una "sfera con g manici" (per g = 0 una sfera, per g = 1 un toro).
Il g. "commutato" d'un g. G è un g. G′ avente per vertici gli spigoli di G, mentre s1 e s2 sono collegati da uno spigolo allorché, in G, s1 e s2 hanno un estremo comune. Non tutti i g. sono isomorfi al commutato d'un g.; invece, due g. connessi, i cui commutati sono isomorfi, sono anch'essi isomorfi, a meno che non si tratti dei due g. della fig. 4. Infine, il g. "aggiunto" d'un g. orientato G è un g. orientato G″ che ha per vertici gli archi di G, e si ha un arco avente s1 e s2 rispettivamente come primo e come secondo vertice allorché in G l'estremo iniziale di s2 coincide con l'estremo finale di s1.
Siano a, b due vertici d'un g. connesso. Sia d(a,b) il minimo numero di spigoli d'un percorso di estremi a, b: per a = b, è
d(a,b) si dice "distanza" di a da b. Oltre alla (1) valgono le relazioni:
le quali permettono di considerare l'insieme dei vertici del g., con la funzione d, uno "spazio metrico" (App. II, 11, p. 874). Il "diametro" d'un g. connesso è la massima fra le distanze fra i vertici del grafo. Per ogni vertice del g., possiamo considerare la massima fra le distanze di questo dagli altri vertici: la più piccola di tali massime distanze si dice "raggio" del g., e i vertici cui essa compete si dicono "centri" del grafo.
Per un g. orientato, possiamo definire lo "scarto" s(a,b) del vertice a dal vertice b come il minimo numero di archi d'un cammino che inizia in a e termina in b (se un tale cammino non esiste, scriveremo s(a,b) = ∞). Valgono relazioni analoghe a (1) e a (3), ma di regola non vale una relazione del tipo (2).
In un g. orientato, si dice "nucleo" un insieme N di vertici tale che, se a appartiene a N, non v'è in N alcun vertice successore di a, mentre se a non appartiene a N v'è in N almeno un vertice successore di a. In un g. privo di circuiti esiste uno e un sol nucleo.
Il concetto di g. si può generalizzare in quello di "ipergrafo". Un ipergrafo semplice è dato da un insieme V (detto "insieme dei vertici") e da un insieme E di parti (finite) di V: gli elementi di E si dicono spigoli (o simplessi) dell'ipergrafo. Per definire un ipergrafo in generale, premettiamo che si dice "famiglia" Xi di elementi d'un insieme X un'applicazione di un prefissato insieme I di indici in X (per es., una successione è una famiglia il cui insieme degl'indici è l'insieme dei numeri naturali). Un ipergrafo è dato da un insieme V (insieme dei vertici) e da una famiglia E di parti (finite) di V (famiglia degli spigoli): sono così ammessi anche spigoli distinti con gli stessi vertici, come gli spigoli in parallelo d'un grafo. Nel caso in cui tutti gli elementi di E abbiano lo stesso numero di vertici, l'ipergrafo si dice "uniforme". Un concetto analogo è quello di "n-grafo" (orientato o non orientato), intendendo con questo una terna (V, E, f) dove V ed E sono insiemi e f è un'applicazione di E nell'insieme delle (n + 1)-ple (rispettivamente ordinate o non ordinate) di elementi di V (nelle medesime condizioni, altri autori parlano di "(n + 1)-grafo").
Dato un g., si possono associargli vari ipergrafi: basta prendere come verticì quelli del g., e come spigoli i cicli, o. i circuiti, o gli alberi contenuti nel g. con il massimo numero di spigoli, o i g. subordinati di tipo prefissato.
I vari concetti della teoria dei g. si possono di regola estendere agl'ipergrafi (o agli n-grafi): a volte, anzi, più estensioni sono possibili. Per es., si dice sotto-ipergrafo individuato da V′ ⊆ V l'ipergrafo avente come vertici gli elementi di V′ e come spigoli le intersezioni non vuote degli elementi di E con V′. Un ipergrafo parziale ha come insieme degli spigoli un sottoinsieme di E e come vertici quelli che interessano tale sottoinsieme. Possiamo colorare i vertici d'un ipergrafo, chiedendo che i vertici (distinti) d'uno stesso spigolo non abbiano tutti il medesimo colore: il minimo numero di colori che occorrono per una tale colorazione è il "numero cromatico" dell'ipergrafo. Si possono però considerare anche le colorazioni tali che tutti i vertici d'uno stesso spigolo abbiano colori differenti. Una sezione d'un n-grafo G è un m-grafo (m ≤ n) che ha gli stessi vertici di G e come spigoli ha le (m + 1)-ple di vertici contenute nelle (n + 1)-ple.
Bibl.: D. Konig, Theorie der endlichen und unendlichen Graphen, Lipsia 1936; C. Berge, Théorie des graphes et ses applications, Parigi 1958; G. Ringel, Farbungsprobleme auf Flachen und Graphen, Berlino 1959; O. Ore, Theory of Graphs, Providence 1962; id., I grafi e le loro applicazioni, Bologna 1965; F. Harary, R. Z. Norman, D. Cartwright, Structural Models, New York 1965; O. Ore, The four color problem, ivi 1967; L. Muracchini, Introduzione alla teoria dei grafi, Torino 1967; F. Harary, Graph Theory, New York 1969; C. Berge, Graphes et hypergraphes, Parigi 1970.