MATEMATICA DEL DISCRETO -...

MATEMATICA DEL DISCRETOelementi di teoria dei grafi

anno acc. 2009/2010

Cristina Turrini MATEMATICA DEL DISCRETO

Grafi semplici

Un grafo semplice G è una coppia ordinata (V(G), L(G)), ove V(G) èun insieme finito e non vuoto di elementi detti vertici o nodi di G,mentre L(G) è un insieme finito di coppie non ordinate di elementi diV(G) distinti tra loro. Tali coppie vengono dette lati o spigoli di G. Idue vertici di un lato vengono detti estremi del lato stesso.Il numero dei vertici viene talora detto ordine del grafo; il numero deilati viene talora detto grandezza del grafo.

Ad esempio G1 = (V(G1) = {a, b, c}, L(G1) = {{a, c}, {b, c}}),G2 = (V(G2) = {x, y, z, u, w}, L(G2) = {{x, z}, {x, w}, {y, w}}),sono grafi semplici.

Un grafo semplice può essere rappresentato tramite un diagramma incui i vertici siano rappresentati come punti (ad esempio del piano) edin cui due vertici v1 e v2 sono collegati da segmento (o da un arco dicurva) se e solo se la coppia {v1, v2} appartiene a L(G).


In figura sono rappresentati i grafi G1 e G2 definiti prima:G1 = (V(G1) = {a, b, c}, L(G1) = {{a, c}, {b, c}}),G2 = (V(G2) = {x, y, z, u, w}, L(G2) = {{x, z}, {x, w}, {y, w}}),

Viceversa dalla rappresentazione grafica si risale facilmente al grafo.


Due lati aventi un vertice in comune vengono detti incidenti e duevertici di uno stesso lato vengono detti adiacenti.

Ad esempio in G2, x e z sono adiacenti,mentre x e y non lo sono, {x, z} e {x, w}sono incidenti, mentre {x, z} e {y, w}non lo sono.

Fissato un vertice v di un grafo semplice si dice valenza o grado di vil numero dei lati aventi v come estremo. Ad esempio, in G2, x havalenza 2.

Un vertice di valenza 0 (come u per G2) viene detto isolato; unvertice di valenza 1 (come z e y per G2) viene detto terminale.


GrafiAmmettendo, tra i lati, la presenza di coppie di vertici coincidenti, edanche di coppie di vertici ripetute, si ottine la nozione di grafo.Un grafo G quindi è una coppia ordinata (V(G), L(G)), ove V(G) èun insieme finito e non vuoto di elementi detti vertici o nodi di G,mentre L(G) è una lista (multinsieme) finita di coppie non ordinate(eventualmente ripetute) di elementi di V(G) (eventualmentecoincidenti tra loro).

Ad esempio G3 = ({a, b, c}, {{a, a}, {a, c}, {a, c}, {b, c}}), è ungrafo (non semplice) (si veda la figura).


Un lato del tipo {v, v} viene detto cappio

Le definizioni date sopra per i grafi semplici si estendono in modoovvio ai grafi, tenendo presente che per convenzione un cappio {v, v}conta per 2 nel calcolo della valenza di v.

LEMMA - La somma delle valenze dei vertici di un grafo è uguale aldoppio del numero dei lati (in particolare quindi è un numero pari).

Idea della dimostrazione - Sommando i gradi dei vertici si ottiene ilnumero dei lati moltiplicato per due, perchè ogni lato congiunge duevertici e quindi viene contato due volte in tale somma.

COROLLARIO 1- Il numero dei vertici di un grafo di valenza dispariè pari.

Idea della dimostrazione - La somma dei gradi di tutti i vertici è pari,per il lemma. La somma dei gradi dei vertici di valenza pari è pari,perchè somma di numeri pari. Per differenza allora la somma deigradi dei vertici di valenza dispari è pure pari (e quindi anche ilnumero dei vertici di valenza dispari lo è).


Un grafo viene detto regolare di grado d se tutti i suoi vertici hanno lastessa valenza d.

I grafi R1, R2 (ma anche R′2), R3 e R4 in figura sono esempi di grafi

regolari di grado 1, 2, 3 e 4 rispettivamente.

COROLLARIO 2- Un grafo regolare di grado d con n vertici ha dn/2lati.


Un grafo viene detto completo se è semplice e ogni coppia di verticidi G è una coppia di vertici adiacenti. Un grafo completo con n verticiviene indicato con Kn.

In figura sono rappresentati i grafi K2, K3 e K4.


Grafi isomorfiDue grafi G e Γ si dicono isomorfi se esiste una applicazionebiunivoca (detta isomorifismo tra i grafi) tra i gli insiemi dei vertici diG e di Γ

F : V(G) → V(Γ)tale che ∀v, w ∈ V(G) il numero dei lati di G aventi per estremi v e wsia lo stesso di quello dei lati di Γ congiungenti F(v) e F(w).

Un isomorfismo di grafi induce anche una corrispondenza biunivocatra le liste dei lati.Ad esempio i grafi G e Γ in figura sono isomorfi (esercizio: trovare unisomorfismo).


Cammini in un grafo

In un grafo semplice G, un percorso da v0 a vh è una successionefinita di lati (non necessariamente distinti) di G della forma {v0, v1},{v1, v2}, . . . , {vh−2, vh−1}, {vh−1, vh} (i lati consecutivi sonoincidenti, cioè hanno un vertice in comune).

v0 viene detto vertice o estremo iniziale del percorso, vh vertice oestremo finale. Se v0 6= vh, il percorso viene detto aperto, se v0 = vh,il percorso viene detto chiuso.

Il numero h dei lati che costituiscono il percorso viene dettolunghezza del percorso.

Talora si usa indicare un percorso elencando la sequenza dei verticiv0v1v2 . . . vh−1vh.

Le definizioni date sopra si estendono al caso di grafi (nonnecessariamente semplici) con l’accortezza di dover "etichettare" i latiper distinguerli (ad esempio scrivendo {u, v}1, {u, v}2) , nel caso incui vi siano più lati con gli stessi estremi.


Consideriamo un percorso in un grafo.Se i lati del percorso sono a due a due distinti tra loro, il percorsoviene anche detto cammino (da v0 a vh).Un cammino chiuso (cioè con v0 = vh) viene detto circuito o ciclo.Un cammino in cui anche tutti i nodi della sequenza v0v1v2 . . . vh−1vh,sono distinti tranne al più v0 = vh, si dice semplice.

Ad esempio, in figura, il cammino a sinistra non è semplice, mentrequello a destra lo è.

Per convenzione, tra i cammini chiusi si considerano anche i cammininulli: il cammino nullo da v a v è un cammino senza lati di estremoiniziale v e estremo finale v. Il cammino nullo non è un cappio.


Grafi connessi

Un grafo G viene detto connesso se per ogni coppia di vertici v, w diG esiste un cammino da v e w.

Ad esempio, in figura, i grafi G1 e G3 sono connessi, mentre i grafi G2e G4 non lo sono.

OSSERVAZIONE - La richiesta di esistenza di un cammino da v e w èequivalente a quella di esistenza di un percorso da v e w ed anche aquella di esistenza di un cammino semplice da v e w.


Un grafo G = (V(G), L(G)) può essere suddiviso in sottografi (graficostituiti da vertici e lati di G) disgiunti connessi, detti componenticonnesse del grafo, nel seguente modo.Si introduce una relazione ρ in V(G) ponendo uρv se e solo se esisteun cammino con estremo iniziale u ed estremo finale v.Si dimostra che ρ è una relazione di equivalenza e pertanto ρdetermina una partizione in V(G).I vertici che stanno in uno stesso sottoinsieme della partizione,insieme ai lati di G che li hanno per estremi, determinano un grafoconnesso che è una delle componenti connesse del grafo G.

Ad esempio nel grafo G2 si ha xρy ma non xρu. Il grafo G2 ha duecomponenti connesse (individuate dai vertici {x, y, z, w} e {u}rispettivamente). Anche il grafo G4 in figura ha due componenticonnesse (individuate dai vertici {a, c, e} e {b, d, f} rispettivamente).


Grafi euleriani

Un circuito euleriano è un circuito che contiene tutti i lati del grafo.Un grafo G viene detto euleriano se contiene un circuito euleriano.

Il grafo GC in figura non è euleriano, ma ha un cammino aperto checontiene tutti i lati (cammino euleriano).


PROBLEMA DEI PONTI DI KOENIGSBERG - È possibile partireda un punto della città e tornare al punto di partenza avendoattraversato una ed una sola volta ciascuno dei sette ponti illustrati infigura?

Problema equivalente: il grafo a destra in figura è euleriano?

La risposta è negativa (Eulero, 1736).

TEOREMA - Un grafo privo di nodi isolati è euleriano se e solo se èconnesso e tutti i suoi vertici hanno valenza pari.


Grafi planari

Un grafo si dice piano se i suoi vertici sono punti di un piano π e isuoi lati corrispondono ad archi di curve del piano π che congiungonogli estremi del lato e che si intersecano a coppie solo negli eventualiestremi comuni.Un grafo si dice planare se è isomorfo ad un grafo piano.

Il grafo G5 in figura è un esempio di grafo planare, ma non piano


PROBLEMA DELLE TRE CASE - È possibile allacciare ciascunadelle tre case X, Y e Z a ciascuno dei tre servizi A, G e L concondutture (di superficie) che non si intersechino?

Problema equivalente: il grafo G3C in figura è planare?

La risposta è negativa.TEOREMA (Kuratowkski, 1930) - Un grafo è non planare se e solose ha un sottografo isomorfo al grafo G3C o al grafo completo K5.


Da una cartina geografica si ricava facilmente, come in figura, ungrafo (i vertici corrispondono alle regioni e i lati alle regioniconfinanti). Si vuole colorare la cartina in modo che regioniconfinanti non abbiano lo stesso colore. Equivalentemente si vuoleassegnare un colore ai vertici del grafo in modo che vertici adiacentinon abbiano lo stesso colore.

PROBLEMA (dei quattro colori): Quanti colori sono necessari percolorare una qualsiasi cartina? La figura mostra una cartina (e ilcorrispondente grafo) per la quale sono necessari almeno 4 colori.


Alberi

Un grafo connesso si dice albero se non contiene cicli. Un grafo chesia unione di alberi due a due disgiunti (ovvero le cui componenticonnesse siano alberi) si dice foresta.

Dei tre grafi A, B, C in figura solo A è un albero.


OSSERVAZIONE - Un albero non ha cappi (sono cicli) e non hacoppie di lati distinti per gli stessi estremi (individuano un ciclo),quindi è semplice.

OSSERVAZIONE - In un albero per ogni coppia di vertici esiste unoed un solo cammino che li ha per estremi (una coppia di cammini congli stessi estremi individua un ciclo).

TEOREMA - Per un grafo G con n vertici sono equivalentii G è un albero;

ii G è connesso ed ha n− 1 lati.


Gli alberi possono essere utilizzati per rappresentare espressionicontenenti parentesi, quali, ad esempio, le espressioni del calcoloalgebrico, e per dedurne rappresentazioni che non utilizzino parentesi.Ci limitiamo a fare un esempio (che riguarda solo operazioni binarie).L’espressione algebrica

{[(a + 2)× (b− 2)] + c} × (d + 1),può essere rappresentata dall’albero T in figura, da cui si deduce lascrittura con operatore postposto e senza parentesi

a2 + b2−×c + d1 +×.


Diagrammi di Hasse

Consideriamo un insieme finito X = {x1, · · · , xn} e una relazioned’ordine � in X.

C’è un modo semplice di rappresentare tramite un grafo, dettodiagramma di Hasse la relazione � .

I nodi del grafo sono gli elementi di X e, per convenzione, se xi � xjsul piano si disegna il nodo xi più in basso del nodo xj.

Inoltre, nel caso i 6= j, se xi � xj e non esiste alcun xk tale chexi � xk � xj allora si disegna un lato del grafo tra il nodo xi e il nodoxj.


Ad esempio, in figura è disegnato il diagramma di Hasse dellarelazione "essere divisore di" nell’insieme {1, 3, 5, 6, 9, 15}.

Gli alberi genealogici possono essere interpretati come diagrammi diHasse relativi alla relazione "essere discendente di" (o "essere ugualea").Si noti però che gli "alberi genealogici" non sono necessariamente"alberi" anche nel senso della teoria dei grafi.


Matrici di adiacenza

Dato un grafo G = (V(G), L(G)) con n nodi, ovvero conV(G) = {x1, . . . , xn}, si definisce matrice di adiacenza di G lamatrice quadrata MG, di tipo n× n, che al posto ai,j di riga i e colonnaj ha il numero di lati della lista L(G) di estremi xi e xj.

Ad esempio, nel caso di V(G) = {x1, x2, x3, x4} eL(G) = {{x1, x1}, {x1, x3}, {x2, x3}1, {x2, x3}2, {x1, x4}}, la matricedi adiacenza risulta

M =

1 0 1 10 0 2 01 2 0 01 0 0 0

.

OSSERVAZIONE - La matrice di adiacenza dipende dall’ordine incui vengono indicati i vertici.

OSSERVAZIONE - La matrice di adiacenza è simmetrica ovvero siha ai,j = aj,i,∀i, j.


Viceversa, data una matrice quadrata simmetrica di numeri interi nonnegativi, si può costruire un grafo (di cui la matrice risulterà essere lamatrice di adiacenza) con tanti vertici quante sono le righe (e lecolonne) della matrice.

OSSERVAZIONE - Dalla matrice di adiacenza del grafoG = (V(G), L(G)) si ricavano facilmente le seguenti proprietà delgrafo:

il numero dei vertici: è il numero di righe (o colonne) dellamatrice;i vertici isolati: corrispondono alle righe (o colonne) nulle;i cappi: corrispondono agli elementi non nulli nella diagonale;il numero dei lati di estremi il vertice i−esimo e il verticej−esimo: è l’elemento di posto (i, j) della matrice;il grado del vertice i−esimo: è la somma degli elementi dellariga (o colonna) i con la convenzione di contare per due ilcontributo dell’elemento di posto (i, i);se il grafo è semplice: la diagonale deve essere nulla e glielementi della matrice devono essere solo 0 o 1.


Sia MG = {mhk} la matrice di adiacenza di un grafoG = (V(G), L(G)) con V(G) = {v1, . . . , vn}. Denotiamo con Mm

G lamatrice ottenuta come potenza m−esima della matrice MG secondol’operazione data dal prodotto riga per colonna.

LEMMA - L’elemento di posto (i, j) della matrice MmG è il numero dei

percorsi di lunghezza m di estremi vi e vj.

Idea della dimostrazione nel caso m = 2 - L’elemento di posto (i, j)della matrice M2

G è

mi1m1j + mi2m2j + . . . minmnj.

mi1 è il numero di lati da vi a v1; m1j è il numero di lati da v1 a vj,quindi mi1m1j è il numero di percorsi di lunghezza 2 da vi a vj chepassano per v1.Analogamente mi2m2j è il numero di percorsi di lunghezza 2 da vi a vjche passano per v2, e . . . minmnj è il numero di percorsi di lunghezza2 da vi a vj che passano per vn.In conclusione mi1m1j + mi2m2j + . . . minmnj è il numero complessivodei percorsi di lunghezza 2 da vi a vj.


Sia M la matrice di adiacenza di un grafo G = (V(G), L(G)) conV(G) = {v1, . . . , vn} e si denoti con In la matrice identica di ordine n.

TEOREMA - G è connesso se e solo se la matrice

C = In + M + M2 + · · ·+ Mn−1

non ha alcun elemento nullo.

Idea della dimostrazioneImplicazione ⇐ - Se l’elemento di posto (i, j) della matrice C non ènullo, allora esiste un percorso (di lunghezza al più n− 1) da vi a vj.Quindi, se la matrice C non ha elementi nulli, tutti i vertici stannonella stessa componente connessa.Implicazione ⇒ - Se l’elemento di posto (i, j) della matrice C è nullo,allora non esiste un percorso di lunghezza al più n− 1 da vi a vj.Questo garantisce anche la non esistenza di un percorso di lunghezza≥ n da vi a vj (un percorso con più di n− 1 lati avrebbe vertici ripetutie quindi cicli eliminabili; pertanto un tale percorso potrebbe essere"accorciato").


Ad esempio M =

1 0 1 00 0 0 11 0 0 00 1 0 0

è la matrice di un grafo non

connesso dal momento che

C = I4 + M + M2 + M3 = 1 0 0 00 1 0 00 0 1 00 0 0 1

+

1 0 1 00 0 0 11 0 0 00 1 0 0

+

2 0 1 00 1 0 01 0 1 00 0 0 1

+

+

3 0 2 00 0 0 12 0 1 00 1 0 0

=

7 0 4 00 2 0 24 0 3 00 2 0 2


MATEMATICA DEL DISCRETO -...

Documents

Transcript of MATEMATICA DEL DISCRETO -...