GRAFI E COMBINATORIAGRAFI E COMBINATORIA

Laurea Magistrale in Ingegneria Informatica

Politecnico di Bari

Prof. ssa Bambina Larato

A.A. 2012 - 2013

TEORIA DEI GRAFI

La Teoria dei Grafi ha una nascita ben precisa:

EULERO , 1736 ,

con il famoso problema dei ponti di Konigsberg.

Il problema è passare almeno una volta per

ciascuna zona della città senza fare due volte

la stessa strada o attraversare lo stesso ponte

(ma si può passare anche più volte per lo

stesso punto).

TEORIA DEI GRAFI

Altro problema famoso:

Hamilton , 1859 , Gioco delle città:

organizzare un giro turistico per alcune

delle città più famose del mondo.Il problema è visitare tutte le cittàprescelte senza passare due volte per la stessa città.Commesso viaggiatore, Guardie notturne.

SVILUPPI MATEMATICI

Eulero fu probabilmente il primo a intuire che con un processo di astrazione si potevano risolvere anche problemi molto più importanti. Su queste basi lo stesso Eulero ha avviato lo studio di due grandi rami della Matematica e, in particolare, della Geometria:� Teoria dei Grafi (Punto di vista discreto);� Topologia (Punto di vista continuo).

APPLICAZIONI DELLA TEORIA DEI GRAFI

Il problema delle reti, in generale:stradali, informatiche, elettriche, idrauliche.

Il problema degli isomeri chimici: esistono sostanze chimiche di identica composizione sia per elementi e per quantità aventi proprietàchimiche differenti solo perché è differente la disposizione degli atomi nella molecola (Berzelius, 1832).

QUATTRO COLORI

Uno dei problemi più famosi di tutta la Matematica è relativo ai grafi ed è

il problema dei 4 colori.Abbiamo una carta geografica dell'Europa, degli Stati Uniti, ecc. Naturalmente vogliamo colorare in modo diverso gli Stati confinanti.Domanda: Qual è il numero minimo di colori che serve per colorare la carta geografica ? Questo problema è fondamentale, tra l’altro, per il funzionamento dei telefoni cellulari.

GRAFI E MODELLI MATEMATICI

In Matematica Combinatoria i grafi sono “oggetti

discreti” che permettono di trattare in modo unitario

vari problemi applicativi di ricerca operativa, di

viabilità, di trasporti, di cammino minimo, ecc.

L’efficienza della Teoria dei Grafi consiste nella

possibilità di schematizzare una grande varietà di

situazioni e di processi, analizzandoli in termini

quantitativi e algoritmici.

I PONTI DI KONIGSBERG

La Teoria dei Grafi è il risultato di contributi provenienti da molteplici settori. Alcuni problemi sui grafi fanno ormai parte della storia della Matematica:

� Il Problema dei ponti di Königsberg (1736)

Mappa topografica dei

sette ponti di Königsberg

Grafo che schematizza il problema

Il Problema dei quattro colori (1852)

� Quanti colori sono necessari per colorare le varie regioni d’Italia, in modo tale che due regioni confinanti non abbiano lo stesso colore?

Modello di Grafo per una carta geografica:

� indicare ogni regione con un punto;

� rappresentare due regioni confinanti mediante un lato che unisce i due punti corrispondenti.

Il Grafo così ottenuto è planare, cioè può essere disegnato su un piano senza che i suoi lati si intersechino

TEOREMA DEI QUATTRO COLORI (1976): Ogni grafo planare è 4-colorabile

ALCUNE DEFINIZIONI

DEF.: Si dice grafo semplice (o grafo) una coppia

ordinata G = (V, E) dove:

� V è un insieme di elementi detti punti (vertici ,

nodi ). V deve essere un insieme non vuoto: V≠Ø .

� E è UN insieme di coppie non ordinate di punti distinti {u, v} di V, dette lati (spigoli, archi, rami)

E ⊆ { { u , v} | u, v ∈ V }

Può essere E = Ø : il grafo è costituito di soli punti.

ALCUNE DEFINIZIONI

� Si indica con V(G) l’insieme dei punti V del grafo G

� Si indica con E(G) l’insieme dei lati E del grafo G

� Si chiama (p, q) - grafo un grafo con:

p punti, cioè |V| = p

q lati, cioè |E| = q .

� Si dice grafo banale, o (1,0) – grafo, il grafo con un solo punto e zero lati:

G = (V,E) , V = {u} , E = Ø , |V| = 1, |E| = 0

LINGUAGGIO

Per riferirsi al lato x = {u, v}, u ∈ V e v ∈ V , si dice che:

Il lato x congiunge i punti u e vIl lato x unisce i punti u e v (rete informatica)Il lato x collega i punti u e v (rete stradale)Nei problemi concreti il linguaggio dipende dalla situazione particolare.

u

vx

LINGUAGGIO

Nel linguaggio matematico non è così.Si dice che:� i punti u e v sono adiacenti se sono uniti da un lato x = {u, v} ;

� i lati x ed y sono adiacenti se hanno un punto (vertice) in comune;

� il punto u è incidente il lato x = {u,v};� il lato x = {u,v} è incidente sia il punto u , sia il punto v .

DEF.: La coppia ordinata (u,u) si chiama laccio (cappio, loop).

DEF.: Se in un grafo G si ammettono anche i loop, allora G si dice pseudografo.

DEF.: Si dice multigrafo un grafo in cui si hanno anche più lati che uniscono la stessa coppia di punti.

ALTRI TIPI DI GRAFO

u

x1

u

vx2

x3

N.B. In un insieme non si ammettono le ripetizioni,

in un grafo semplice c’è al più un lato tra 2 punti.

DEF. : Si dice grafo diretto un grafo in cui un lato è una coppia ordinata (u,v) e può essere lato anche la coppia ordinata (v,u)es.: rete stradale

DEF. : Si dice grafo orientato un grafo in cui tra due punti u e v c’è al più uno dei due lati,

x = (u,v) oppure y = (v, u), mai entrambi.es.: rete fluviale

� Un grafo orientato è sempre diretto� Un grafo diretto non è detto che sia orientato

ALTRI TIPI DI GRAFO

a b

cd

DEF. - Un grafo G = (V, E) si dice grafo pesato se

esiste una funzione

w : E → R

che ad ogni lato x = {u, v} associa uno ed un solo

numero reale w(x) , detto peso di x .

Il peso w(x) può rappresentare informazioni varie:

la lunghezza del lato x , il tempo di transito da u a v,

il costo del collegamento x = {u, v} .

ALTRI TIPI DI GRAFI

UGUAGLIANZA

Come è ben noto, il concetto di

“uguaglianza tra due oggetti”

riguarda esclusivamente il caso in cui

si attribuiscono due nomi diversi allo

stesso oggetto, dunque:

“un oggetto è uguale solo a se stesso”.

EQUIVALENZA

In tutte le attività umane siamo soliti

considerare “uguali” oggetti diversi che

abbiano però alcune proprietà in comune,

cioè siamo abituati a considerare una sorta di

“uguaglianza allargata”,

una “uguaglianza da un certo punto di vista”.

In Matematica questa si chiama EQUIVALENZA

ESEMPIO

Due poligoni si dicono equivalenti se hanno la

stessa superficie; quindi può accadere che

uno sia un triangolo e l’altro sia un rettangolo:

sono “uguali dal punti di vista della superficie”

ma non dal punto di vista del numero dei lati.

“La Ferrari è un’auto sportiva” :

potrebbe sembrare che ne esiste solo una !

ISOMORFISMO

In Matematica si ragiona sempre non su

oggetti singoli ma su classi di oggetti

equivalenti; l’equivalenza viene determinata

mediante una funzione bigettiva che

conservi la proprietà comune agli oggetti

considerati: queste funzioni si chiamano

ISOMORFISMI .

ISOMORFISMO TRA GRAFI

DEF. : Si dice che due grafi G = (V,E) e

G’ = (V’, E’) sono isomorfi se esiste una

bigezione

f : V → V’

che conserva i lati, cioè tale che se:

{u,v}∈E , allora { f(u), f(v) }∈E’ ;

la funzione f si chiama

isomorfismo di G in G’ .

ISOMORFISMO TRA GRAFI

L’esistenza di una bigezione tra gli insiemi V e V’

assicura anzitutto che i due insiemi abbiano la stessa

cardinalità: |V| = |V’| , cioè che i due grafi G e G’

abbiano lo stesso numero di vertici. Inoltre, la

proprietà richiesta assicura anche che la funzione f

conservi le adiacenze: se i vertici u e v di G sono

uniti da un lato, allora anche i vertici f(u) e f(v)

devono essere uniti da un lato del grafo G’ .

ISOMORFISMO TRA GRAFI

Quindi si dicono isomorfi e si considerano “uguali”

due grafi aventi gli “stessi” vertici e gli “stessi” lati.

Questo vuol dire che due grafi isomorfi possono

avere vertici e lati con nomi diversi, possono essere

collocati in posizioni diverse, possono essere

rappresentati in modo diverso, possono anche

rappresentare fatti e situazioni diverse.

Non ostante queste differenze come grafi possono

essere considerati uguali.

ISOMORFISMO TRA GRAFI

DEF. : Si dice labelled graph (grafo etichettato)

un grafo i cui punti siano contraddistinti da nomi

(che possono essere lettere, numeri, o entrambi).

Due grafi isomorfi sono grafi etichettati in maniera

differente. Sono conservati i vertici e i lati; ma ai

vertici e ai lati sono stati dati nomi differenti, magari

perché rappresentano cose diverse.

LA RAPPRESENTAZIONE DEI GRAFI

Questi disegni rappresentano grafi isomorfi, cioè lo stesso grafo. Si preferisce un disegno oppure un altro sia per rappresentare una situazione concreta diversa, sia per evidenziare particolari proprietà del grafo.

Abitualmente i grafi sono rappresentati mediante disegni, ma i grafi NON SONO disegni.

SOTTOGRAFI

DEF. : Sia G = (V, E) un grafo e siano V’ ⊆ V ,

E’ ⊆ E ; allora il grafo G’=(V’, E’) si dice

sottografo di G , purché sia V’ ≠ Ø .

Oss.: un sottografo di un grafo G si ottiene

eliminando un certo numero di punti e/o un

certo numero di lati al grafo G.

SOTTOGRAFI

DEF. : Se un grafo G’ è sottografo di un grafo

G e G’ è stato ottenuto eliminando solo alcuni

lati di G ma sono stati conservati tutti i punti di

G , allora il grafo G’ = (V,E’) , con E’ ⊂ E , si

dice che G’ è un sottografo coprente

(spanning subgraph) di G .

SOTTOGRAFI

DEF.: Sia G = (V, E) un grafo e sia S ⊂ V , S ≠ Ø ;

allora il grafo G’ = (S, E’ ) dove

E’ = { x = {u,v}∈E | u,v∈S }

si chiama sottografo indotto da S , essendo S

un sottoinsieme di vertici di G , e si scrive

G’ =< S > .

SOTTOGRAFI

DEF. : Sia G = (V, E) un grafo e sia X ⊂ E ; il grafo

G’ = (V’, X) dove

V’ = { v∈V | v è incidente con qualche x∈X } ,

si dice sottografo indotto da X , essendo X un

sottoinsieme di lati di G , e si scrive

G’ =< X > .

COMMENTO

In generale un sottografo G’ di un grafo G=(V,E) si

ottiene eliminando certi vertici e certi lati di G senza

un particolare legame tra i vertici e i lati esclusi.

Nel caso di un grafo indotto, invece, all’eliminazione

di certi vertici corrisponde l’eliminazione dei lati ad

essi adiacenti (questo è inevitabile) e solo di questi;

all’eliminazione di certi lati corrisponde l’eliminazione

dei vertici adiacenti (anche se questo non è

inevitabile).

ESEMPIO 1

G1

G

V = {v1, v2, v3, v4, v5, v6}

E = { {v1, v2}, {v2, v3}, {v3, v4}, {v1, v6}, {v2, v5},

{v5, v4}, {v6, v5} }

V1 = {v2, v4, v5, v6}

E1 = { {v2, v5}, {v6, v5}, {v5, v4}} G1 = < V1 >

v1 v2 v3

v6 v5 v4

v6 v5 v4

v2

ESEMPIO 2

G3

G2V2 = V - {v6}

E2 = { {v1, v2}, {v2, v3}, {v2, v5}, {v5, v4} {v3, v4} }

G2 = < E2 >

V3 = V

E3 = E - { {v2, v3}, {v1, v6}, {v6, v5} }

G3 è uno spanning subgraph di G

v1 v2 v3

v5 v4

v1 v2 v3

v6 v5 v4

GRADO DI UN PUNTO

DEF: Dato un grafo G = (V,E) si dice grado o

valenza (degree, valency) di un punto v il

numero di lati incidenti il punto v.

Notazione: il grado di un punto v si denota con d

oppure deg v oppure d(v) .

GRADO DI UN PUNTO

ESEMPIO:

v1

v5v4

v3

v2v6

Indicando con di il grado del vertice vi si ha:

d1 = 2 d2 = 3 d3= 4 d4 = 2 d5 = 2 d6 = 3.

GRADO DI UN VERTICE

OSS.: nell’esempio in figura si ha

8)(,166

1

==∑=

GEdi

i

La somma dei gradi di tutti i punti del grafo è il doppio del numero dei lati del

grafo. Questo risultato non è per niente casuale; in realtà dipende dal fatto che

ciascun lato congiunge due vertici e, quindi, nel conteggio dei gradi ciascun lato

viene contato due volte: una prima volta per uno dei vertici e una seconda volta

per l’altro. Questo risultato sussiste in generale, come stabilito dal Teorema di

Eulero.

TEOREMA DI EULERO(I° Teorema della Teoria dei grafi)

TEOREMA: La somma dei gradi di tutti i punti di

un grafo G è uguale al doppio del numero dei

lati di G:

|)(|2)()(

GEvdGVv

=∑∈

COROLLARIO

COROLLARIO: Ogni grafo ha un numero pari di

vertici di grado dispari.

In un (p,q) – grafo (semplice) si ha che

∀ v ∈ V : 0 ≤ d(v) ≤ p-1 .

Notazione:

δ(G) = min{ d(v) | v∈V(G) }

∆(G) = max{ d(v) | v∈V(G) }

GRADO DI UN GRAFO

DEF. : Un grafo G si dice regolare di grado r

(oppure grafo r-regolare) se tutti i punti di G

hanno lo stesso grado r; in tal caso si ha che:

δ(g) = ∆(g) = r

e si scrive d(G) = r.

Se d(G) = 0 il grafo è regolare di grado 0 (grafo

senza lati). Il grafo banale è un grafo 0-regolare.

NOMENCLATURA

Si introducono nomi particolari per i punti di

grado più basso:

DEF. : Si chiama punto isolato (isolated point)

un punto v∈V t.c. d(v) = 0 .

DEF. : Si chiama punto terminale (end point) un

punto v∈V t.c. d(v) = 1 .

CAMMINI – WALK

DEF. : Sia G = (V,E) un grafo; si dice cammino

(walk) del grafo G una successione (finita) che

alterna punti e lati di G

w = vo e1 v1 e2 … vk-1 ek vk (1)

che inizia e termina con punti e nella quale ciascun

lato è incidente tanto il punto che lo procede,

quanto quello che lo segue (es.: e1 = {v0 , v1} ).

CAMMINI – WALK

Il cammino (1) verifica le proprietà seguenti:

i. v0 , v1 , … , vk ∈V(G) ;

ii. e1 , e2 , … , ek ∈E(G) ;

iii. ogni lato ei è incidente con vi-1 e con vi .

CAMMINI – WALK

OSS.: Se il grafo G è semplice, i punti

vi-1 e vi determinano in modo univoco il

lato ei ; pertanto nella descrizione di un

cammino solitamente si scrive:

w = vo v1 v2 … vkomettendo i lati.

CAMMINI – WALK

Spesso si dice che il cammino

w = vo v1 v2 … vkunisce i punti v0 e vk e lo si chiama

v0-vk cammino .

DEF.: Un cammino v0v1…vk si dice chiuso

se v0 = vk ; in caso contrario si dice aperto .

TRAIL E PATH

In generale, in un cammino possono ripetersi

tanto i punti, quanto i lati.

DEF. : Un cammino senza lati ripetuti si dice

TRAIL (tracciato).

DEF. : Un cammino senza vertici ripetuti di dice

PATH (percorso)

OSSERVAZIONI

OSS.: Un path è sempre un trail ma non viceversa:PATH ⇒TRAIL , ma non è vero che TRAIL ⇒ PATH

OSS.: Da un WALK si può sempre ottenere un PATH avente lo stesso punto iniziale e lo stesso punto finale; se in un WALK un punto è ripetuto, per avere un PATH con gli stessi estremi basta eliminare i punti ripetuti tranne uno e tutti i lati frapposti.

CICLI IN UN GRAFO

DEF.: Si chiama CICLO (cycle) un WALK chiuso

senza lati ripetuti (ma con almeno un lato) e

senza punti ripetuti eccetto il punto iniziale e

quello finale.

OSS.: un CICLO (cycle) è un PATH chiuso.

LUNGHEZZA DI UN WALK

DEF.: Sia w un walk; si chiama

lunghezza di w

il numero l(w) dei lati del walk w .

Esempio: sia w = vo e1 v1 e2… vk-1 ek vkun walk; allora si ha che l(w) = k .

LUNGHEZZA DI UN WALK

Se la lunghezza di un walk è k = 0 , si ha

che w = v0 , cioè in questo caso il walk è

costituito da un solo punto.

NOTAZIONE:

Cn denota un ciclo di n punti ;

Pn denota un path di n punti .

QUALCHE ESEMPIO

v1

v3

v2v4

G :G è un (4,4)-grafo semplice

w1 = v1 v2 v1 v4 è un walk, ma non un trail

w2 = v1 v2 v3 v4 v1 è un path chiuso, cioè è un ciclo C4

w3 = v1 v2 v3 v4 è un path (non ha vertici ripetuti)

v1 v2 v3

v4 v5

G’ :G’ è un (5,6)-grafo semplice

w = v1 v2 v5 v4 v2 v3 è un trail ma non è un path

k-CICLO

DEF.: Si dice k-ciclo un ciclo di lunghezza k.

3-ciclo, spesso chiamato triangoloC3

C6 6-ciclo

GRAFO CONNESSO

DEF. : Un grafo si dice connesso se due punti

qualsiasi del grafo sono sempre congiungibili

mediante un path.

DEF. : Si dice componente connessa (o soltanto

componente) di un grafo G ogni sottografo

connesso di G che sia massimale.

DEF. : Un grafo che non è connesso si dice

disconnesso.

GRAFO CONNESSO

Ovviamente un grafo disconnesso ha

almeno due componenti connesse;

ciascuna componente connessa

costituisce, a sua volta un grafo connesso.

Se il grafo è connesso ha una sola

componente connessa che è il grafo

stesso.

Esempi

G Il grafo G ha 5 componenti connesse.

HIl grafo H ha 2 componenti connesse.

DISTANZA

DEF. : Siano u e v due punti di un grafo G ;

se esistono path che uniscono il punto u con il

punto v si chiama distanza tra u e v la

lunghezza del path più corto tra u e v e la

si denota con d(u,v) ; se non esiste alcun path

che congiunge u e v si pone d(u,v) = ∞ .

DISTANZA

TEOREMA: Se G è un grafo connesso,

allora la distanza è una metrica, cioè

d : G × G → R tale che

∀ u, v, w ∈ V(G) si ha:

1. d(u,v) ≥ 0 ;

2. d(u,v) = 0 ⇔ u = v ;

3. d(u,v) = d(v,u) ;

4. d(u,w) ≤ d(u,v) + d(v,w) .

COMMENTO

Tutti noi siamo abituati a considerare la usuale distanza euclidea, ma spesso si deve utilizzare il concetto di distanza in ambienti particolari come quello attuale.Il fatto di ricorrere alla definizione astratta di distanza come funzione che a due oggetti di qualsiasi natura associa un numero reale non negativo, verificante le proprietà dette sopra, consente di applicare tutta una serie di nozioni (per esempio il concetto di sfera) e di risultati che discendono da queste proprietà e non dalla natura degli oggetti. Si può osservare che nel caso attuale la distanza assume solo valori interi.

MATRICI DI UN GRAFO

Il disegno che rappresenta un grafo fornisce molti spunti per ledefinizioni e per le dimostrazioni, ma non è utile nella comunicazione con i computer. Esistono altre rappresentazioni di un grafo e sono le rappresentazioni matriciali.LA MATRICE DI ADIACENZADEF. : Sia G = (V,E) un grafo semplice con V = {v1, …, vn} . Si chiamamatrice di adiacenza la matrice A avente n righe ed n colonne, i cui elementi aij appartengono all’insieme {0,1}. L’elemento

1 se vi e vj sono adiacentiaij =

0 se vi e vj non sono adiacenti

MATRICE DI ADIACENZA

La nozione di matrice di adiacenza di un grafo può

essere estesa anche a grafi che non siano semplici,

come pseudografi, multigrafi, ecc.

In generale si definisce matrice di adiacenza una

matrice A = (aij) dove ciascun aij è il numero dei

lati che uniscono i punti vi e vj .

La matrice di adiacenza di un grafo non è unica

perché dipende dall’ordine in cui si prendono in

considerazione i punti del grafo stesso.

OSSERVAZIONE

Dalla definizione, la matrice di adiacenza di un grafo

è sempre quadrata di ordine n = |V| .

Tale matrice è simmetrica se il grafo non è diretto.

Una matrice di adiacenza di un grafo semplice ha

sempre tutti nulli gli elementi della diagonale

principale.

ESEMPIO

01101

10100

11011

00101

10110

5

4

3

2

1

54321

v

v

v

v

v

vvvvv

v1 v3

v2

v5 v4

G

La matrice A di adiacenza di G è:

OSS.: Per ogni singola riga i di A si ha: )(1

i

n

j

ij vda =∑=

MATRICI DI PERMUTAZIONE

DEF.: Si chiama matrice di permutazione

una matrice quadrata non singolare che

abbia un solo elemento uguale a 1 su

ciascuna riga e su ciascuna colonna,

mentre tutti gli altri elementi sono nulli.

MATRICI DI PERMUTAZIONE

Le matrici di permutazione di ordine n

formano un gruppo di matrici (non abeliano

se n>2).

Questo gruppo è isomorfo al gruppo

simmetrico Sn delle permutazioni su n

oggetti (che in questa situazione sono le

righe oppure le colonne della matrice A ).

MATRICI DI PERMUTAZIONE

Moltiplicare una matrice di permutazione P

per una matrice A vuol dire permutare le

righe oppure le colonne di A . Precisamente:

P⋅A presenta una permutazione sulle righe

della matrice A , mentre

A⋅P presenta una permutazione sulle

colonne della matrice A .