Teoria dei grafi

DESMATRON

TEORIA DEI GRAFI 0

Teoria dei Grafi Author: Desmatron

Release 1.0.0 Date of Release: October 28, 2004

Author website: desmatron.altervista.org

Book website: desmatron.altervista.org/teoriadeigrafi/index.html

teoriadeigrafi.altervista.org

E-mail: desmatron@email.it

teoriadeigrafi@email.it 1

Appunti di Teoria dei Grafi Premessa

PREMESSA

Questa è la prima edizione di un libro che non vuole avere la pretesa di essere un formale testo di

Teoria dei Grafi bensì, una gradevole lettura per tutti quegli esperti in materia ed un valido aiuto per

coloro che approcciano questi ‘recenti’ studi per la prima volta.

Per quanto riguarda il numero di release, ho pensato di utilizzare l’ultima cifra come indicativa per

eventuali correzioni di una stessa release. La seconda cifra dovrebbe star ad indicare l’aggiunta di

qualche esercizio, considerazione o dimostrazione di qualcosa già affrontata mentre la prima cifra

avrebbe lo scopo d’indicare una release dove sia stato aggiunto qualcosa di non affrontato; nuovi

teoremi, argomenti o altro.

Ho riletto il testo una sola volta per motivi di tempo e mi scuso sin d’ora per eventuali mancanze o

inesattezze. Cercherò di fare del mio meglio per trovare eventuali errori che, se volete, potrete

segnalare alle e-mails indicate a pagina 1.

Infine, se oltre a segnalare errori vorrete suggerire anche qualche argomento, fatelo pure.

☺

Buon divertimento

Appunti di Teoria dei Grafi Premessa

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

2

Appunti di Teoria dei Grafi - Introduzione Capitolo 1

Teoria dei Grafi

Capitolo 1

Introduzione

Innanzitutto poniamoci la domanda chiave:

"Di che cosa si occupa la Teoria dei Grafi"?

Questa materia relativamente molto recente fa parte di tutto un filone matematico-ingegneristico

che sta sotto il nome di Ricerca Operativa (Operations Research è il termine anglossasone).

In quest'ambito più vasto si vanno a risolvere problemi di minimo (e viceversa di massimo) sotto

opportune restrizioni poste dal problema preso in esame e con particolari metodi che sono tuttora

oggetto di studio. Si parla comunque quasi sempre di ottimizzazione di un problema piuttosto

complesso. Gli algoritmi creati ad hoc per la risoluzione di problemi all’apparenza irrisolubili

costituiscono l’ossatura di tutta la Ricerca Operativa e semplici ragionamenti possono essere

coadiuvati da potenti computers per la risoluzione di problemi con centinaia o migliaia di variabili.

Tornando però ad analizzare la Teoria dei Grafi, c'é da dire che a differenza di molte altri rami della

Ricerca Operativa, questa opera certamente sotto la visualizzazione grafica di archi, nodi e flussi.

Vedremo meglio in dettaglio questi termini, ma sottolineo che qualsiasi problema di Grafi e Reti

apparentemente descrivibile solo in forma grafica, ha invece una sua possibile descrizione

matematica e in particolare, una formulazione di programmazione lineare, lineare intera o non

lineare.

La Teoria dei Grafi è in possesso di algoritmi che permettono di capire quale sia il percorso minimo

su di un grafo qualsiasi e per grafo qualsiasi intendo quell’insieme di nodi, archi e flussi che

descrive una situazione reale e non. L’esempio più eclatante di un grafo è quello della rete stradale,

dove gli incroci sono nodi e le strade sono archi. Possiamo anche descrivere la possibilità di un

tratto stradale di sopportare un certo numero di veicoli tramite la variabile capacità massima del

flusso. Parliamo invece semplicemente di flusso quando vogliamo descrivere il numero di unità (in

questo caso autoveicoli) che passano sul tratto al tempo t.

Ma vediamo un primo esempio di grafo semplice nella figura 1.1.

Appunti di Teoria dei Grafi Capitolo 1

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

3

Appunti di Teoria dei Grafi - Introduzione Capitolo 1

Figura 1.1

Come si può facilmente capire abbiamo semplificato due percorsi che passano dalla città di Siena e

di Roma. Da notare quattro cose:

• non abbiamo né punti di partenza né punti d’arrivo

• non abbiamo restrizioni sul verso di percorrenza di ciascun arco

• non abbiamo restrizioni sulla capacità massima di ciascun arco

• non abbiamo informazioni sul flusso degli archi

Vedremo comunque più avanti tutte le tipologie di grafo.

Nella figura 1.2 ho riportato invece un esempio classico di Ricerca Operativa che potrete risolvere

con un software adeguato come il Lindo 6.1.

Potete scaricare i 3.3 Mb di programma al seguente sito:

• http://www.lindo.com/cgi/frameset.cgi?leftdwnld.html;downloadf.html

Si può vedere dalla figura che i problemi di Ricerca Operativa consistono in generale

nell’ottimizzazione di una funzione obiettivo. Quest’ottimizzazione verterà sulla minimizzazione se

parliamo ad esempio di costi di progetto o sulla massimizzazione se parliamo di ricavi monetari.

Appunti di Teoria dei Grafi Capitolo 1

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

4

Appunti di Teoria dei Grafi - Introduzione Capitolo 1

Figura 1.2

max 2X - 3X + 7X

1 2 3

st X - 2X ≤ 1

1 2

X + 3X ≥ 2

2 3

2X + 2X ≤ 3

1 3 , X e X )

In questo caso abbiamo voluto massimizzare una funzione che prevede tre variabili (X

1 2 3

sotto i vincoli descritti dal ‘subject to’ (st). Le restrizioni che necessita ciascun problema sono quasi

sempre rappresentabili, anche il fatto che si voglia dal problema una soluzione delle tre variabili di

tipo intero. Quest’ultimo caso ricade nell’Integer Linear Programming ovvero, nella

Programmazione Lineare Intera dove sono esplicitamente richieste soluzione appartenenti ai numeri

naturali.

In generale si può dire che le peculiarità della Teoria dei Grafi e della Ricerca Operativa siano

quelle di abbreviare i tempi computazionali di qualsiasi problema. Una volta trovata una buona

strada per l’ottimo, è compito degli studiosi trovare un algoritmo ancora più efficiente per rendere

minimi i tempi di calcolo dei computers.

Fatta questa breve e semplice premessa, addentriamoci nel mondo della Teoria dei Grafi.

Appunti di Teoria dei Grafi Capitolo 1

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

5

Appunti di Teoria dei Grafi – Definizioni di base Capitolo 2

Teoria dei Grafi

Capitolo 2

Definizioni di base

Andiamo a vedere una per una le simbologie e le definizioni che useremo lungo tutto il libro.

Grafo

Con la dicitura G = (V,E) indichiamo il generico grafo con V nodi ed E archi.

La denominazione delle lettere deriva dal fatto che in inglese si indicano i nodi con la parola

“vertex” e gli archi con la parola “edge”.

Nodi adiacenti

Due nodi si dicono adiacenti se sono connessi da un arco.

Figura 2.1

I nodi A e B sono adiacenti, così come lo sono A e C, ma non sono adiacenti tra loro i nodi B e C.

Appunti di Teoria dei Grafi Capitolo 2

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

6

Appunti di Teoria dei Grafi – Definizioni di base Capitolo 2

Archi adiacenti

Si dicono archi adiacenti quegli archi che hanno un nodo in comune.

Figura 2.2

Sono adiacenti gli archi:

• AC-AB

• AC-CD

• CD-DB

• DB-BA

Non sono adiacenti gli archi:

• AC-BD

• AB-CD

Appunti di Teoria dei Grafi Capitolo 2

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

7

Appunti di Teoria dei Grafi – Definizioni di base Capitolo 2

Vicinato

Per vicinato s’intende l’insieme di tutti i nodi adiacenti al generico nodo j.

Figura 2.3

In questo caso il vicinato di j è il seguente insieme: {a,b,c,d,e,f,g}.

Archi multipli e loops

Gli archi multipli e i loops non verranno trattati molto in questo libro, ma per completezza

d’informazione diciamo che i primi sono archi differenti che collegano due stessi nodi, mentre i

secondi sono archi che hanno come punto di partenza ed arrivo sempre lo stesso generico nodo j.

Si vedano le relative figure 2.4 e 2.5.

Appunti di Teoria dei Grafi Capitolo 2

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

8

Appunti di Teoria dei Grafi – Definizioni di base Capitolo 2

Figura 2.4 ARHI MULTIPLI

Figura 2.5 LOOPS

Grafo semplice

Si dice grafo semplice quel grafo che non contiene né archi multipli né loops.

Appunti di Teoria dei Grafi Capitolo 2

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

9

Appunti di Teoria dei Grafi – Definizioni di base Capitolo 2

Alcuni esempi di descrizione di un grafo

Come abbiamo visto a pagina 4, un grafo generico lo possiamo indicare con la dicitura (V,E), ma

esistono anche altri modi per dire che G è un grafo contenente V nodi ed E archi.

Vediamone alcune:

• G = G (V,E)

• G = ( V(G), E(G) )

• G = { 12,27,78,86,45,53,31 }

Nell’ultimo esempio abbiamo indicato l’insieme degli archi del grafo G. Questo tipo di descrizione

contiene una preziosa informazione: i nodi che collegano ed il numero di nodi presenti in G.

Figura 2.6

Da notare la totale indifferenza nel descrivere un arco non orientato nel modo AB o BA; entrambe

le diciture indicano lo stesso arco. Dunque, potremo descrivere indifferentemente il grafo di figura

Appunti di Teoria dei Grafi Capitolo 2

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

10

Appunti di Teoria dei Grafi – Definizioni di base Capitolo 2

2.6 nel seguente modo: G = { 21,72,78,86,54,53,31 } dove abbiamo cambiato la posizione dei nodi

di tre archi; il primo, il secondo e il terzultimo.

Vedremo più avanti il significato di archi orientati e le loro conseguenti implicazioni.

Un’ulteriore ed interessante notazione per descrivere un grafo è questa:

• G = ( n, f(n) )

Come si vede, gli archi sono descritti in funzione dei nodi e questo ci dice che i nodi sono collegati

tra loro con un criterio che obbedisce ad una legge ben definita, la funzione f(n) appunto.

Esempio 2.1

G = ( j, 2n ) per n = 1,2,….,6

Appunti di Teoria dei Grafi Capitolo 2

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

11

Appunti di Teoria dei Grafi – Definizioni di base Capitolo 2

Sottografi

I sottografi rappresentano una qualsivoglia partizione G’ del grafo originario G.

Esempio 2.2 GRAFO G SOTTOGRAFO G’

Sottografo completo

Considerando i nodi facenti parte della partizione G’, se questi preservano gli archi originari, allora

essi formano un sottografo completo.

L’esempio 2.2 non rappresenta un sottografo completo in quanto vi sono tutti i nodi originari, ma

manca più di un arco. Quando avviene questo è immediato capire che la sola assenza di un arco

determina un sottografo incompleto.

Nell’esempio 2.3 abbiamo invece un sottografo completo del grafo H.

Appunti di Teoria dei Grafi Capitolo 2

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

12

Appunti di Teoria dei Grafi – Definizioni di base Capitolo 2

Esempio 2.3

Faccio notare come l’esistenza di un arco sia legata alla previa esistenza di due nodi. Un nodo non

connesso si dice nodo isolato o nodo singolo, mentre non esistono archi isolati.

Quando non siamo in presenza di un sottografo completo, questo si dice allora indotto.

Appunti di Teoria dei Grafi Capitolo 2

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

13

Appunti di Teoria dei Grafi – Definizioni di base Capitolo 2

Sottografo ricoprente

E’ quel sottografo non completo che connette ciascun nodo originario. Riprendendo l’esempio

precedente ci troveremmo di fronte ad un grafo simile:

Esempio 2.4

Non esistono dunque, in un sottografo ricoprente, nodi esposti o isolati.

In inglese, il termine spanning sta proprio ad indicare ‘ricoprente’. Incontreremo più avanti questo

vocabolo.

Ordine di un grafo

Il numero di nodi di un grafo G costituisce il suo ordine:

Appunti di Teoria dei Grafi Capitolo 2

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

14

Appunti di Teoria dei Grafi – Definizioni di base Capitolo 2

Dimensione di un grafo

La dimensione di un grafo è data dal numero di archi m che possiede il grafo.

Considerando grafi semplici, possiamo stabilire un range di appartenenza per qualsiasi grafo:

Ricordo che con n indichiamo il numero di nodi presenti nel grafo e che con il simbolo:

indichiamo tutte le possibili combinazioni di n oggetti presi due a due.

Dalle proprietà delle combinazioni, abbiamo che:

dove

ovvero, ‘n su r’ sta ad indicare tutte le combinazioni possibili di n oggetti presi a gruppi di r.

Risolvendo il nostro ‘n su 2’, avremo che:

Che semplificando numeratore e denominatore diviene:

Appunti di Teoria dei Grafi Capitolo 2

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

15

Appunti di Teoria dei Grafi – Definizioni di base Capitolo 2

Dato dunque un grafo semplice con n nodi ed m archi, possiamo dire a priori che il numero di archi

può variare da un minimo di zero ad un massimo di n su 2. Nel caso fossimo in presenza del

massimo numero di archi disponibile, avremmo un grafo completo.

Grafo completo o clique

Si dice completo quel grafo semplice per il quale non è più possibile aggiungere un arco senza

ricrearne uno già presente.

Esempi di grafi completi

Appunti di Teoria dei Grafi Capitolo 2

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

16

Appunti di Teoria dei Grafi – Definizioni di base Capitolo 2

Con la lettera K ed il pedice n siamo soliti indicare una clique di ordine n, ovvero un grafo completo

con n nodi.

Grafo complemento

Un grafo complemento di G è un grafo formato dagli stessi nodi, ma da tutti gli altri archi non

presenti in G.

Esempio 2.5

GRAFO G

e il suo GRAFO COMPLEMENTO

Appunti di Teoria dei Grafi Capitolo 2

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

17

Appunti di Teoria dei Grafi – Accenni di coloring, cammini e isomorfismo Capitolo 3

Teoria dei Grafi

Capitolo 3

Coloring

Numero cromatico di un grafo

E’ il minimo numero di colori necessari tale che due nodi adiacenti non abbiano mai lo stesso

colore.

Con etichetta e colore indicheremo la stessa cosa ovvero, lo ‘status’ di un nodo.

Esempio 3.1

Nel seguente grafo possiamo notare che con 3 colori o come in questo caso 3 numeri, siamo in

grado d’etichettare tutti i nodi:

Come si può vedere dall’esempio 3.1, non vi sono nodi adiacenti che abbiano la stessa etichetta (o

numero da 1 a 3). Dunque abbiamo colorato correttamente il grafo.

Appunti di Teoria dei Grafi Capitolo 3

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

18

Appunti di Teoria dei Grafi – Accenni di coloring, cammini e isomorfismo Capitolo 3

Notiamo adesso una cosa importante; non è possibile colorare questo grafo con due colori poiché

avremo sempre due nodi ‘in conflitto’ tra loro e se facciamo caso alle cliques presenti nel grafo,

osserviamo che queste sono tutte di ordine tre e che in particolare sono le clique di ordine massimo.

Quest’osservazione ci permette di dire che data una clique di ordine n in un grafo G, non sarà

possibile colorare quest’ultimo con un numero di colori minori di n.

Si usa indicare il numero cromatico di un grafo con la lettera greca ‘chi’: χ (G).

Il problema del coloring ha avuto enorme successo con il famoso “Teorema dei quattro colori”, il

quale ha stabilito che per colorare una qualsiasi mappa bidimensionale sono sufficienti per

l’appunto solamente quattro colori.

Dalla figura 3.1 si capisce come si possa passare dal problema reale ad un problema su grafi.

Figura 3.1

Supponiamo che ogni regione debba essere colorata con un unico colore e supponiamo d’indicare

ogni regione con un nodo e l’adiacenza tra una regione ed un’altra con un arco che connette i due

nodi.

Appunti di Teoria dei Grafi Capitolo 3

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

19

Appunti di Teoria dei Grafi – Accenni di coloring, cammini e isomorfismo Capitolo 3

Si vede bene come si possa risolvere il problema di colorazione minima di una situazione reale con

l’ausilio della teoria dei grafi.

Quest’altra figura che potrete trovare al seguente sito:

• http://www.math.gatech.edu/~thomas/FC/fourcolor.html

vi chiarirà sicuramente le idee:

Se volete approfondire l’argomento del coloring, qui ci sono una serie di links che potrebbero

esservi utili per cominciare:

• dal The Geometry Junkyard http://www.ics.uci.edu/~eppstein/junkyard/color.html

un altro buon punto di partenza contenente programmi di coloring e generazione di grafi è:

• http://www.cs.ualberta.ca/~joe/Coloring/

per quanto riguarda invece il problema dei quattro colori ed il suo conseguente teorema:

• http://www.math.gatech.edu/~thomas/FC/fourcolor.html

un ultimo sito degno di nota è quello della University of Southern Denmark nel quale potrete trovare

altro materiale interessante;

• http://www.imada.sdu.dk/Research/Graphcol/

Appunti di Teoria dei Grafi Capitolo 3

Author: Desmatron – http://desmatron.altervista.org http://teoriadeigrafi.altervista.org

20

Appunti di Teoria dei Grafi – Accenni di coloring, cammini