Appunti di teoria dei grafi per Sociologia

1. Problemi classici che coinvolgono i grafi I PONTI DI KOENIGSBERG La bella cittadina tedesca di Koenigsberg si trova alla confluenza di due fiumi, comprende un isolotto ed è divisa in quattro parti, corrispondenti alle quattro regioni di terra che si venivano a formare (fig. 1): le due sponde A e B , l'isolotto C e la parte di terra D che si trova tra i due fiumi prima della confluenza. In città c'erano i sette ponti indicati in figura. I cittadini di Koenigsberg sottoposero al famoso matematico Leonhard Euler (Eulero) un problema che non erano riusciti a risolvere: tracciare un percorso che, partendo da una qualsiasi delle quattro zone della città, attraversava tutti i sette ponti, una ed una sola volta, ritornando alla fine al punto di partenza. Eulero associò al problema la rappresentazione schematica di fig.2: ciascuna della quattro zone della città è rappresentata da un cerchio, e ciascun ponte da una linea. Questa rappresentazione del problema è una struttura matematica ben definita, e prende il nome di grafo. Nel lavoro Solutio problematis ad geometriam situs pertinentis del 1736, (dove appare per la prima volta il termine grafo) Eulero dimostrò che il problema non aveva soluzioni. Mostreremo in seguito come ragionò. IL PROBLEMA DEI QUATTRO COLORI Un altro problema che coinvolge il modello "grafo" è il famoso problema dei quattro colori. Si tratta di determinare il numero di colori strettamente necessari per colorare le regioni di una qualsiasi carta geografica in modo tale che due regioni adiacenti abbiano colori diversi. Un esempio di regioni-colorazioni è in fig.3. Una rappresentazione del problema può essere fornita associando un cerchio ad ogni regione della mappa e collegando con una linea due cerchi corrispondenti a due regioni adiacenti (fig. 4). Come pei i ponti di Koenigsberg, anche questa rappresentazione trascura aspetti non essenziali come, per esempio, l'estensione delle regioni, la forma dei loro confini, ecc., e mette in evidenza esclusivamente gli aspetti utili a risolvere il problema.La struttura utilizzata in questa rappresentazione è la stessa dell'esempio precedente: anch'essa è un grafo. Anche su questo problema torneremo in seguito. I quattro esempi "storici" proposti mettono in evidenza come problemi molto diversi tra loro possono essere modellati mediante la stessa struttura matematica: il grafo. I grafi rappresentano uno strumento essenziale per la risoluzione di una ricca varietà di problemi provenienti da applicazioni reali. Tra le altre applicazioni: IL PROBLEMA DEL COMMESSO VIAGGIATORE Dato un insieme di città, qual è il percorso più breve che le attraversa tutte una sola volta ? IL PROBLEMA DELLE TRE CASE E DELLE TRE FORNITURE Si possono collegare tre case a tre fornitori senza che strade-tubature-cavi che le connettono si incrocino ? Qual è il numero minimo di incroci che si devono fare ? Nella tabella seguente alcuni esempi di situazioni problematiche concrete che possono ricnodnotte ai problemi classici: problema applicazioni reali I PONTI DI KOENIGSBERG Problemi di trasporto. Per esempio, stabilire la rotta di un veicolo postale in modo da distribuire la posta in maniera efficiente: Chinese Postman's Problem. Problemi di ispezione e manutenzione di sistemi distribuiti: reti elettriche, telefoniche, stradali. I QUATTRO COLORI Testi di circuiti elettronici stampati, allocazione di variabili e registri della CPU, assegnazione di frequenze radio-televisive IL COMMESSO VIAGGIATORE Determinare i flussi delle merci tra i magazzini dei fornitori e dei distributori, determinare il percorso più breve che connette due città LE TRE CASE E LE TRE FORNITURE Layout di reti elettriche, telefoniche, idriche; connettere nella maniera più efficiente un insieme di calcolatori in una rete telematica 2. Grafi : definizioni e proprietà fondamentali Un grafo è una struttura matematica utilizzata per rappresentare una relazione binaria tra gli elementi di due insiemi. GRAFO NON ORIENTATO Un grafo non orientato G è una coppia ordinata di insiemi (V, E) dove è un insieme di elementi chiamati vertici un insieme di coppie di vertici chiamate spigoli. In un grafo non orientato ogni spigolo e è individuato da una coppia di vertici (u,v), e si usa la notazione e=(u,v) per identificare tale spigolo. Da ora in poi con il termine grafo intenderemo grafo non orientato. Per rappresentare un grafo si utilizzano dei cerchi per i vertici e per gli spigoli delle linee che congiungono i vertici.Un esempio di rappresentazione di un grafo con 7 vertici e 10 spigoli è dato in Fig.5. In tale grafo l'insieme V dei vertici è L'insieme E degli spigoli è Notiamo subito che : · la presenza di una linea tra due vertici indica la presenza di una relazione tra di essi · per un grafo non orientato risulta (u,v)=(v,u) ADIACENZA E INCIDENZA Due vertici u e v si dicono adiacenti se e solo se (u,v) è uno spigolo Uno spigolo e=(u,v) si dice incidente su u e su v GRADO DI UN VERTICE Si chiama grado del vertice v il numero di spigoli incidenti in v. Il grado di un vertice si indica con deg(v). Un vertice si dice pari se il suo grado è pari. TEOREMA Indicando con vi un vertice di un grafo, con nv il numero di vertici e con ns il numero di spigoli, si ha . La dimostrazione viene lasciata al lettore. MULTIGRAFO Un multigrafo è un grafo con spigoli multipli, ossia con più di uno spigolo che congiunge gli stessi estremi. Un esempio di multigrafo e quello dato in fig.1 (Ponti di Koenigsberg). PASSEGGIATA - PERCORSO - SENTIERO - CICLO Una passeggiata in un multigrafo è una successione del tipo vertice-spigolo-vertice-, per es. v1 , e1 , v2 , e2 , ..., vn , en , dove ciascuno spigolo ei è incidente in vi-1 e vi . Il numero n degli spigoli si chiama lunghezza della passeggiata. La passeggiata si dice chiusa se v1 =vn . Quando il grafo non ha spigoli multipli (cioè non è un multigrafo), per identificare una passeggiata è sufficiente indicare la successione dei vertici o la successione degli spigoli. Un percorso è una passeggiata in cui tutti gli spigoli sono distinti. Un sentiero è una passeggiata in cui tutti i vertici sono distinti. Ovviamente, un sentiero deve essere un percorso. Un ciclo è una passeggiata chiusa tale che tutti i vertici siano distinti ad eccezione di v1 =vn . Un ciclo di lunghezza k si chiama k-ciclo. LEMMA

In un grafo, ogni ciclo deve avere lunghezza maggiore o uguale a 3

GRAFO CONNESSO
Un grafo si dice connesso (Fig.6) se esiste un sentiero tra due qualsiasi suoi vertici. In fig.7 è riportato un esempio di grafo non connesso (p.e., non esiste un sentiero da v₄ a v₇ ).

GRAFO TRAVERSABILE
Un grafo (o un multigrafo) si dice traversabile se può essere disegnato senza mai alzare la penna dal foglio e senza mai passare due volte per lo stesso spigolo.
In un grafo traversabile, quindi, esiste un passeggiata nella quale sono inclusi tutti i vertici e dove vengono usati tutti gli spigoli una sola volta (mentre si può passare per un vertice quante volte si vuole). Tale passeggiata si chiama percorso traversabile. Un esempio di grafo traversabile è dato in Fig. 6: (v₁ , v₂ , v₄ , v₁ , v₃ , v₄ , v₅ ) è un percorso traversabile.

A titolo di esempio determiniamo le caratteristiche del grafo connesso di Fig.8. Consideriamo la passeggiata da v4 a v6 : (v4, v1, v2, v5, v1, v2, v3, v6). Questa passeggiata non è un percorso, perché lo spigolo (v1, v2) viene usato due volte. La successione (v4, v1, v5, v2, v6) non è una passeggiata, perché manca lo spigolo (v2, v6). La successione (v4, v1, v5, v2, v3, v5, v6) è un percorso perché nessuno spigolo è stato usato due volte, ma non è un sentiero perché il vertice v5 è usato due volte. La successione (v4, v1, v5, v3, v6) è un sentiero da v4 a v6.

3. Analisi del grafo dei ponti di Koenigsberg
Siamo ora in grado di studiare il problema dei ponti di Koenigsberg.
Il problema ammette soluzioni se si riesce a dimostrare che il multigrafo associato al problema (fig.9) è traversabile.

Vediamo come ha ragionato Eulero. Consideriamo un multigrafo traversabile, e supponiamo che un percorso traversabile P non inizi (e quindi non finisca) in V. Il vertice V è sicuramente di grado pari perché ogni volta che P entra in V da uno spigolo, deve sempre uscirne da uno spigolo non usato in precedenza; in altre parole nel vertice V il numero di ingressi è uguale al numero di uscite, e quindi il grado di V è pari. Questo significa che se un vertice U ha grado dispari, allora il percorso P deve iniziare e finire in U. Di conseguenza, se un multigrafo ha più di due vertici dispari, allora non è traversabile. Il grafo fig. 9 ha quattro vertici dispari, e quindi non è traversabile: il problema dei ponti di Koenigsberg non ha soluzione.

Eulero, in effetti, dimostrò la proposizione inversa a quella esposta in precedenza. In particolare dimostrò il seguente teorema.

TEOREMA DI EULERO

Un grafo connesso finito è un GRAFO traversabile se e solo se ha due vertici di valenza dispari, oppure nessuno.

4. Grafi hamiltoniani
I grafi traversabili si chiamano grafi euleriani. In questi grafi, esiste una passeggiata chiusa che comprende tutti gli spigoli del grafo una sola volta.
Il matematico William Rowland Hamilton si pose il problema duale: quali sono le condizioni affinché esista una passeggiata chiusa che includa tutti i vertici una sola volta? Tale passeggiata è evidentemente un ciclo, e prende il nome di ciclo di Hamilton. Non è ancora stato trovato un metodo generale per determinare il ciclo hamiltoniano di un grafo qualunque, e molti matematici sono attualmente impegnati nella ricerca di questo metodo.
Un interessante problema "hamiltoniano" è il problema del commesso viaggiatore, già accennato all'inizio: un commesso viaggiatore deve visitare dei clienti in alcune città. Come deve scegliere il percorso stradale che collega tutte le città da visitare con la città di partenza, in modo da minimizzare i chilometri da percorrere?
Il problema può essere modellato da un grafo, in cui i vertici sono le città (e qualche incrocio stradale…), mentre gli spigoli sono tutte le strade percorribili che collegato le città tra di loro (compresa la città di partenza)

Il lettore provi a risolvere il problema seguente, costruendo il grafo appropriato.

Problema Un tecnico di manutenzione di impianti termici, residente a Teramo, deve visitare dei clienti nelle seguenti località: · Torricella Sicura · Montorio · Faiano · Villa Petto · Villa Maggiore · Castel Castagna · Basciano Il tecnico vuole percorrere meno strada possibile. Qual è il percorso minimo? O, in altri termini, qual è il ciclo hamiltoniano del grafo associato al problema? I dati sulle lunghezze delle strade sono inseriti nella cartina.

5. Grafi planari
Un grafo si dice planare se può essere tracciato in un piano e se i suo spigoli non si intersecano. Chiameremo mappa un grafo planare. Una mappa divide in facce il piano che la contiene.

Per esempio la mappa in fig. 11 è suddivisa in cinque facce . La faccia è uguale alla differenza tra l'insieme dei punti del piano euclideo e i punti delle 4 facce restanti, ed è quindi (lei sola) illimitata.Per grado di una faccia F si intende un ciclo (passeggiata chiusa) i cui spigoli sono le frontiere di F.Non sarà difficile per il lettore dimostrare il seguente TEOREMA La somma dei gradi delle facce di una mappa è uguale al doppio del numero degli spigoli.

Importante (anche nella geometria solida) è il seguente:

TEOREMA DI EULERO
Indicando con n_v il numero di vertici di una mappa connessa M, con n_s il numero di spigoli e con il numero delle facce, si ha: n_v - n_s + n_F =2

6. Mappe colorate
Consideriamo una mappa M. Due facce di M si dicono adiacenti se hanno uno spigolo in comune. Una colorazione di M consiste nell'assegnare ad ogni faccia di M un colore in modo che facce adiacenti abbiano colori diversi.
Una mappa M è n-colorabile se bastano n colori. Possiamo ora esaminare il seguente teorema :

TEOREMA DEI QUATTRO COLORI

Ogni mappa è 4-colorabile

La formulazione del teorema è di una semplicità disarmante. Nonostante questo, la sua dimostrazione ha impegnato per quasi 130 anni i migliori matematici. La sua prima formulazione risale al 1852, quando l'inglese Francis Guthrie in una lettera lo propose al fratello Frederick, allievo del famoso matematico Augustus De Morgan. Del problema venne a conoscenza Hamilton, al quale De Morgan il 23 ottobre del 1852 scriveva :
"… un mio studente mi ha chiesto oggi il perché di un fatto. Egli dice che se si divide una figura, in modo qualsiasi, in regioni e si vogliono colorare queste regioni in modo diverso, cioè in modo che regioni confinanti risultino colorate in modo diverso, possono essere necessari quattro colori ma non di più: ossia ogni carta geografica può essere colorata con un massimo di 4 colori".

Il problema non interessò immediatamente né Hamilton né i matematici dell'epoca. Tuttavia, il fatto che non si riusciva a trovare una dimostrazione coinvolse via via sempre più matematici. Per 124 anni il teorema rimase una congettura fino a che, nel 1976, due matematici dell'Università dell'Illinois (USA), Kenneth Appel e Wolfgang Haken, con l'ausilio determinante dei più potenti calcolatori dell'epoca, riuscirono a dimostrare il teorema. Occorsero più di 1200 ore di tempo-macchina su tre diversi elaboratori elettronici. Era la prima volta che un teorema veniva dimostrato con l'ausilio di un elaboratore elettronico, cosa che suscitò all'epoca non poche discussioni tra i matematici.

7. Il salto del cavallo
Il matematico Dudeney inventò 80 anni fa il seguente problema, assai facile da risolvere con un grafo, ma che presenta notevoli difficoltà se risolto per tentativi.
Consideriamo la scacchiera ridotta di fig. 12, in cui ci sono 2 cavalli neri e due cavalli bianchi. Il gioco consiste nello scambiare di posto i due cavalli bianchi con i due neri.

Costruito il grafo del problema (fig.13), notiamo innanzitutto che il grafo non è planare. Ma questo non è un problema: si può fare in modo di disegnare un grafo equivalente a quello di fig.13, ma senza lati che si intersecano.
Un'interessante articolo su un problema analogo a questo (con una scacchiera più grande di quella di fig.12) può essere letto alla pagina

http://space.tin.it/scuola/vdepetr/t18/Text18.htm

Giovanni Valentini

www.matematico.it