grafo
Indice
Descrizione generale
sm. [dal tema del greco gráphō, scrivere]. In matematica, configurazione formata da un insieme di punti, detti vertici del grafo, e di segmenti, o archi di curva, detti lati o spigoli del grafo, aventi per estremi due dei suddetti vertici. In un grafo possono esservi vertici isolati, che non sono estremi di nessun lato; non si esclude neppure che due vertici, a e b, siano estremi di più lati diversi. Uno spigolo può essere orientato: ciò accade quando la coppia dei vertici a esso associata (a, b), viene ordinata, stabilendo, per esempio, che a è il primo vertice, b il secondo (lo spigolo diventa una freccia, da a fino a b). In tal caso si ha un grafo orientato. Si chiama grafo nullo un grafo composto da soli vertici isolati, e con ciò privo di spigoli; grafo completo (non orientato e, rispettivamente, orientato) un grafo nel quale ogni coppia non ordinata (rispettivamente ordinata) di vertici è congiunta da uno spigolo e uno soltanto. Molte situazioni della vita pratica, così come fenomeni diversi della natura, danno luogo a grafi quando vengano schematizzati. Una rete di distribuzione, di energia elettrica, di acqua, ecc., diventa un grafo quando si considerano vertici i punti iniziali o finali o di giunzione dei fili (o tubi), lati i tratti di collegamento (fili o tubi) "Tutte le figure relative al grafo sono a pag. 156 dell’11° volume." . Le strade di una città costituiscono un grafo, del quale i vertici sono le piazze e i crocevia; i sensi unici introducono un orientamento su alcuni lati. Un albero genealogico è un grafo (grafo genetico): ogni vertice è il secondo estremo di due vertici, e due soltanto (padre e madre), a eccezione dei capostipiti. Un torneo di calcio all'italiana, con girone di andata e ritorno, è un grafo orientato completo. Le squadre sono rappresentate dai vertici, gli incontri tra le squadre sono rappresentati da lati aventi come primo vertice la squadra che gioca in casa, come secondo vertice la squadra che gioca fuori casa. Per ogni coppia di vertici (squadre) vi sono quindi due lati orientati con verso opposto che rappresentano gli incontri di andata e ritorno.
Problema dei servizi e planarità dei grafi
La teoria dei grafi ha importanti applicazioni pratiche; per esempio nella distribuzione di energia può essere importante evitare sovrapposizioni di cavi: ciò sarà possibile se e solo se il corrispondente grafo è planare, cioè a condizione che vertici e spigoli possano essere rappresentati in un piano con punti e archi di curva che li collegano senza incroci in punti diversi dai vertici stessi. Si consideri, a tal proposito, il seguente problema dei servizi. È possibile collegare due case, indicate con A e B, alle centrali dell'acqua e del gas, indicate con C e D, senza che i cavi e i tubi si sovrappongano? Il problema può essere schematizzato dal grafo, indicato dalla sigla k₂,₂, nel quale i collegamenti sono stati fatti con segmenti; si può anche fare in modo che non vi siano sovrapposizioni. Consideriamo ora il problema dei servizi nel caso di tre case A, B, C da collegare a tre centrali D, E, F (acqua, gas ed elettricità). Il problema è schematizzato dal grafo k₃,₃. Si possono evitare le sovrapposizioni? Si può creare una figura con una sola sovrapposizione. Non è possibile fare di meglio. Il grafo k₃,₃ non è quindi planare. Un altro esempio di grafo non planare è il grafo k5 completo con 5 vertici. I grafi k₃,₃ e k5 sono gli esempi base di grafi non planari. Il matematico polacco C. Kuratovski ha infatti dimostrato nel 1930 che un grafo è planare se e solo se non contiene i grafi k₃,₃ e k5. Questi due grafi vengono perciò chiamati grafi di Kuratovski. Il problema della planarità dei grafi ha acquistato notevole importanza con l'introduzione dei circuiti elettronici stampati. Per stampare infatti un circuito il cui grafo non sia planare è necessario utilizzare più di una piastra. Non è importante infatti la posizione dei vertici e dei lati; occorre invece che i grafi abbiano lo stesso numero di vertici e che i lati connettano gli stessi vertici. Due grafi verificanti questa proprietà si dicono grafi isomorfi. La teoria dei grafi è interessata quindi alle loro proprietà topologiche. Per questa ragione è considerata parte della topologia. All'interno di un grafo si chiama cammino la successione di lati tali che il punto finale di un lato coincida con il punto iniziale del lato successivo. Il primo vertice del primo lato e il secondo vertice dell'ultimo lato si dicono estremi del cammino. Un grafo si dice connesso se, dati comunque due suoi vertici, esiste un cammino che li abbia come estremi. Un cammino si dice circuito se i suoi estremi coincidono; un circuito si ottiene partendo dal vertice A e andando poi di volta in volta nei vertici D, B, E e di nuovo in A percorrendo i lati che congiungono tali vertici. Un grafo in cui non vi siano circuiti si dice albero. "Per l'albero vedi figura A al lemma del 10° volume." . Un grafo si dice bipartito se i suoi vertici possono essere suddivisi in due sottoinsiemi V e W tali che ogni lato del grafo abbia un vertice in V e un vertice in W. Tale grafo bipartito si dice poi completo se ogni vertice di V è unito a ogni vertice di W per mezzo di un lato del grafo. I k₂,₂ e k₃,₃ sono grafi bipartiti completi. I grafi sono usati in molte applicazioni nella tecnologia dei computer: i vertici rappresentano oggetti di qualche specie e i lati collegamenti di tipo logico o fisico tra i vertici. In questo modo i grafi possono essere usati per rappresentare un computer collegato alle sue periferiche, una rete di computer, un supercalcolatore con migliaia di microprocessori, un circuito neuronico, ecc.; alberi e liste sono tipi particolari di grafi. Un grafo “pesato” è un grafo con pesi associati ai suoi lati. Il peso rappresenta una funzione che ha come dominio l'insieme dei lati del grafo. Questa funzione viene a volte detta “funzione dei costi”. Per esempio nel campo dei circuiti elettrici ed elettronici al lato opportunamente orientato viene associata la funzione di trasferimento (amplificazione, transimpedenza, ecc.), mentre i due vertici rappresentano rispettivamente il segnale di ingresso e quello di uscita. In questa classe un grafo fondamentale è quello dell'anello di reazione dove i vertici di ingresso e uscita sono collegati da due lati, di cui il secondo riporta in ingresso il segnale di uscita conferendo così al circuito particolari proprietà di regolazione od oscillazione.
Problema di Königsberg e problema di Hamilton
La teoria dei grafi si fa risalire al 1736, data di pubblicazione della Memoria nella quale L. Eulero dava compiuta risposta al problema dei sette ponti di Königsberg. "Per la figura A vedi il lemma del 10° volume." È possibile fare una passeggiata per Königsberg percorrendo una e una sola volta i suoi sette ponti e tornando alla fine al punto di partenza? Il problema dei sette ponti di Königsberg viene generalizzato nel seguente problema: dato un grafo connesso, "Per la figura B vedi il lemma del 10° volume." esiste un suo circuito che percorra una e una sola volta tutti i lati del grafo? Un tale circuito, se esiste, si chiama linea di Eulero; la risposta di Eulero è che una tale linea esiste se e solo se da ciascun vertice esce un numero pari di lati, cioè se ogni vertice ha quello che si dice grado locale pari; poiché nella schematizzazione dei sette ponti ci sono vertici dai quali escono tre lati, il problema di Königsberg non ha soluzioni. Analogo, ma più difficile, è il problema di Hamilton: determinare i grafi, detti grafi di Hamilton, che possiedono un percorso che passa una volta e una soltanto per ciascun vertice. Anche questo problema ha importanza pratica, essendo collegato a problemi di minimo nel compiere un itinerario che tocchi un certo numero di punti (problema del commesso viaggiatore).
Problema dei quattro colori
Appartiene infine alla teoria dei grafi il problema dei quattro colori. Esso può essere espresso in questi termini: è vero, o non è vero, che per dipingere con colori diversi Stati confinanti, e l'oceano che circonda un continente, sono sempre sufficienti quattro colori? Immaginiamo un'isola formata da tre Stati. Per colorare i tre Stati e il mare sono necessari quattro colori indicati con 1, 2, 3 e 4. In un'altra isola formata da 6 Stati che hanno tutti un punto di frontiera in comune, due Stati aventi in comune un solo punto possono essere colorati con lo stesso colore senza che ciò rechi confusione. Per questa ragione nel problema dei 4 colori due regioni (Stati o mare) che abbiano in comune solo un numero finito di punti non vengono considerati confinanti. Nella figura dell'isola formata da tre Stati sono quindi necessari solo 3 colori indicati con 1, 2 e 3. A ogni carta geografica viene associato un grafo planare considerando come vertici i punti che siano di confine di almeno tre regioni e come lati i confini. Il grafo della carta geografica ha quindi 4 vertici, i punti A, B, C, D, e 6 lati. Il problema dei quattro colori è stato posto al matematico inglese A. De Morgan da un suo studente nel 1852. Molti matematici, tra cui lo stesso De Morgan e A. Cayley, hanno provato, senza successo, a dimostrare che quattro colori sono sufficienti. La dimostrazione è stata data solamente nel 1976 da K. Appel e W. Haken, i quali, per l'alto numero di casi da esaminare, hanno dovuto far uso di computer ad alta velocità. L'esempio della figura dei tre Stati mostra che non è possibile migliorare il teorema: tre colori non sono sempre sufficienti.