Comments
Description
Transcript
elementi di teoria dei grafi
MATEMATICA DEL DISCRETO elementi 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 di V(G) distinti tra loro. Tali coppie vengono dette lati o spigoli di G. I due vertici di un lato vengono detti estremi del lato stesso. Il numero dei vertici viene talora detto ordine del grafo; il numero dei lati 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 in cui i vertici siano rappresentati come punti (ad esempio del piano) ed in cui due vertici v1 e v2 sono collegati da segmento (o da un arco di curva) se e solo se la coppia {v1 , v2 } appartiene a L(G). Cristina Turrini MATEMATICA DEL DISCRETO 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. Cristina Turrini MATEMATICA DEL DISCRETO Due lati aventi un vertice in comune vengono detti incidenti e due vertici 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 v il numero dei lati aventi v come estremo. Ad esempio, in G2 , x ha valenza 2. Un vertice di valenza 0 (come u per G2 ) viene detto isolato; un vertice di valenza 1 (come z e y per G2 ) viene detto terminale. Cristina Turrini MATEMATICA DEL DISCRETO Grafi Ammettendo, tra i lati, la presenza di coppie di vertici coincidenti, ed anche 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) (eventualmente coincidenti tra loro). Ad esempio G3 = ({a, b, c}, {{a, a}, {a, c}, {a, c}, {b, c}}), è un grafo (non semplice) (si veda la figura). Cristina Turrini MATEMATICA DEL DISCRETO Un lato del tipo {v, v} viene detto cappio Le definizioni date sopra per i grafi semplici si estendono in modo ovvio 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 al doppio del numero dei lati (in particolare quindi è un numero pari). Idea della dimostrazione - Sommando i gradi dei vertici si ottiene il numero dei lati moltiplicato per due, perchè ogni lato congiunge due vertici 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 dei gradi dei vertici di valenza dispari è pure pari (e quindi anche il numero dei vertici di valenza dispari lo è). Cristina Turrini MATEMATICA DEL DISCRETO Un grafo viene detto regolare di grado d se tutti i suoi vertici hanno la stessa valenza d. I grafi R1 , R2 (ma anche R02 ), 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/2 lati. Cristina Turrini MATEMATICA DEL DISCRETO Un grafo viene detto completo se è semplice e ogni coppia di vertici di G è una coppia di vertici adiacenti. Un grafo completo con n vertici viene indicato con Kn . In figura sono rappresentati i grafi K2 , K3 e K4 . Cristina Turrini MATEMATICA DEL DISCRETO Grafi isomorfi Due grafi G e Γ si dicono isomorfi se esiste una applicazione biunivoca (detta isomorifismo tra i grafi) tra i gli insiemi dei vertici di G e di Γ F : V(G) → V(Γ) tale che ∀v, w ∈ V(G) il numero dei lati di G aventi per estremi v e w sia lo stesso di quello dei lati di Γ congiungenti F(v) e F(w). Un isomorfismo di grafi induce anche una corrispondenza biunivoca tra le liste dei lati. Ad esempio i grafi G e Γ in figura sono isomorfi (esercizio: trovare un isomorfismo). Cristina Turrini MATEMATICA DEL DISCRETO Cammini in un grafo In un grafo semplice G, un percorso da v0 a vh è una successione finita di lati (non necessariamente distinti) di G della forma {v0 , v1 }, {v1 , v2 }, . . . , {vh−2 , vh−1 }, {vh−1 , vh } (i lati consecutivi sono incidenti, cioè hanno un vertice in comune). v0 viene detto vertice o estremo iniziale del percorso, vh vertice o estremo 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 detto lunghezza del percorso. Talora si usa indicare un percorso elencando la sequenza dei vertici v0 v1 v2 . . . vh−1 vh . Le definizioni date sopra si estendono al caso di grafi (non necessariamente semplici) con l’accortezza di dover "etichettare" i lati per distinguerli (ad esempio scrivendo {u, v}1 , {u, v}2 ) , nel caso in cui vi siano più lati con gli stessi estremi. Cristina Turrini MATEMATICA DEL DISCRETO Consideriamo un percorso in un grafo. Se i lati del percorso sono a due a due distinti tra loro, il percorso viene 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 v0 v1 v2 . . . vh−1 vh , sono distinti tranne al più v0 = vh , si dice semplice. Ad esempio, in figura, il cammino a sinistra non è semplice, mentre quello a destra lo è. Per convenzione, tra i cammini chiusi si considerano anche i cammini nulli: il cammino nullo da v a v è un cammino senza lati di estremo iniziale v e estremo finale v. Il cammino nullo non è un cappio. Cristina Turrini MATEMATICA DEL DISCRETO Grafi connessi Un grafo G viene detto connesso se per ogni coppia di vertici v, w di G esiste un cammino da v e w. Ad esempio, in figura, i grafi G1 e G3 sono connessi, mentre i grafi G2 e 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 a quella di esistenza di un cammino semplice da v e w. Cristina Turrini MATEMATICA DEL DISCRETO Un grafo G = (V(G), L(G)) può essere suddiviso in sottografi (grafi costituiti da vertici e lati di G) disgiunti connessi, detti componenti connesse del grafo, nel seguente modo. Si introduce una relazione ρ in V(G) ponendo uρv se e solo se esiste un 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 grafo connesso 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 due componenti connesse (individuate dai vertici {x, y, z, w} e {u} rispettivamente). Anche il grafo G4 in figura ha due componenti connesse (individuate dai vertici {a, c, e} e {b, d, f } rispettivamente). Cristina Turrini MATEMATICA DEL DISCRETO 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 che contiene tutti i lati (cammino euleriano). Cristina Turrini MATEMATICA DEL DISCRETO PROBLEMA DEI PONTI DI KOENIGSBERG - È possibile partire da un punto della città e tornare al punto di partenza avendo attraversato una ed una sola volta ciascuno dei sette ponti illustrati in figura? 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. Cristina Turrini MATEMATICA DEL DISCRETO Grafi planari Un grafo si dice piano se i suoi vertici sono punti di un piano π e i suoi lati corrispondono ad archi di curve del piano π che congiungono gli estremi del lato e che si intersecano a coppie solo negli eventuali estremi 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 Cristina Turrini MATEMATICA DEL DISCRETO PROBLEMA DELLE TRE CASE - È possibile allacciare ciascuna delle tre case X, Y e Z a ciascuno dei tre servizi A, G e L con condutture (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 solo se ha un sottografo isomorfo al grafo G3C o al grafo completo K5 . Cristina Turrini MATEMATICA DEL DISCRETO Da una cartina geografica si ricava facilmente, come in figura, un grafo (i vertici corrispondono alle regioni e i lati alle regioni confinanti). Si vuole colorare la cartina in modo che regioni confinanti non abbiano lo stesso colore. Equivalentemente si vuole assegnare un colore ai vertici del grafo in modo che vertici adiacenti non abbiano lo stesso colore. PROBLEMA (dei quattro colori): Quanti colori sono necessari per colorare una qualsiasi cartina? La figura mostra una cartina (e il corrispondente grafo) per la quale sono necessari almeno 4 colori. Cristina Turrini MATEMATICA DEL DISCRETO Alberi Un grafo connesso si dice albero se non contiene cicli. Un grafo che sia unione di alberi due a due disgiunti (ovvero le cui componenti connesse siano alberi) si dice foresta. Dei tre grafi A, B, C in figura solo A è un albero. Cristina Turrini MATEMATICA DEL DISCRETO OSSERVAZIONE - Un albero non ha cappi (sono cicli) e non ha coppie di lati distinti per gli stessi estremi (individuano un ciclo), quindi è semplice. OSSERVAZIONE - In un albero per ogni coppia di vertici esiste uno ed un solo cammino che li ha per estremi (una coppia di cammini con gli stessi estremi individua un ciclo). TEOREMA - Per un grafo G con n vertici sono equivalenti i G è un albero; ii G è connesso ed ha n − 1 lati. Cristina Turrini MATEMATICA DEL DISCRETO Gli alberi possono essere utilizzati per rappresentare espressioni contenenti parentesi, quali, ad esempio, le espressioni del calcolo algebrico, 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 la scrittura con operatore postposto e senza parentesi a2 + b2 − ×c + d1 + ×. Cristina Turrini MATEMATICA DEL DISCRETO Diagrammi di Hasse Consideriamo un insieme finito X = {x1 , · · · , xn } e una relazione d’ordine in X. C’è un modo semplice di rappresentare tramite un grafo, detto diagramma di Hasse la relazione . I nodi del grafo sono gli elementi di X e, per convenzione, se xi xj sul 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 che xi xk xj allora si disegna un lato del grafo tra il nodo xi e il nodo xj . Cristina Turrini MATEMATICA DEL DISCRETO Ad esempio, in figura è disegnato il diagramma di Hasse della relazione "essere divisore di" nell’insieme {1, 3, 5, 6, 9, 15}. Gli alberi genealogici possono essere interpretati come diagrammi di Hasse relativi alla relazione "essere discendente di" (o "essere uguale a"). Si noti però che gli "alberi genealogici" non sono necessariamente "alberi" anche nel senso della teoria dei grafi. Cristina Turrini MATEMATICA DEL DISCRETO Matrici di adiacenza Dato un grafo G = (V(G), L(G)) con n nodi, ovvero con V(G) = {x1 , . . . , xn }, si definisce matrice di adiacenza di G la matrice quadrata MG , di tipo n × n, che al posto ai,j di riga i e colonna j 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 } e L(G) = {{x1 , x1 }, {x1 , x3 }, {x2 , x3 }1 , {x2 , x3 }2 , {x1 , x4 }}, la matrice di adiacenza risulta 1 0 1 1 0 0 2 0 M = 1 2 0 0 . 1 0 0 0 OSSERVAZIONE - La matrice di adiacenza dipende dall’ordine in cui vengono indicati i vertici. OSSERVAZIONE - La matrice di adiacenza è simmetrica ovvero si ha ai,j = aj,i , ∀i, j. Cristina Turrini MATEMATICA DEL DISCRETO Viceversa, data una matrice quadrata simmetrica di numeri interi non negativi, si può costruire un grafo (di cui la matrice risulterà essere la matrice di adiacenza) con tanti vertici quante sono le righe (e le colonne) della matrice. OSSERVAZIONE - Dalla matrice di adiacenza del grafo G = (V(G), L(G)) si ricavano facilmente le seguenti proprietà del grafo: il numero dei vertici: è il numero di righe (o colonne) della matrice; 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 vertice j−esimo: è l’elemento di posto (i, j) della matrice; il grado del vertice i−esimo: è la somma degli elementi della riga (o colonna) i con la convenzione di contare per due il contributo dell’elemento di posto (i, i); se il grafo è semplice: la diagonale deve essere nulla e gli elementi della matrice devono essere solo 0 o 1. Cristina Turrini MATEMATICA DEL DISCRETO Sia MG = {mhk } la matrice di adiacenza di un grafo G = (V(G), L(G)) con V(G) = {v1 , . . . , vn }. Denotiamo con MGm la matrice ottenuta come potenza m−esima della matrice MG secondo l’operazione data dal prodotto riga per colonna. LEMMA - L’elemento di posto (i, j) della matrice MGm è 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 MG2 è mi1 m1j + mi2 m2j + . . . min mnj . mi1 è il numero di lati da vi a v1 ; m1j è il numero di lati da v1 a vj , quindi mi1 m1j è il numero di percorsi di lunghezza 2 da vi a vj che passano per v1 . Analogamente mi2 m2j è il numero di percorsi di lunghezza 2 da vi a vj che passano per v2 , e . . . min mnj è il numero di percorsi di lunghezza 2 da vi a vj che passano per vn . In conclusione mi1 m1j + mi2 m2j + . . . min mnj è il numero complessivo dei percorsi di lunghezza 2 da vi a vj . Cristina Turrini MATEMATICA DEL DISCRETO Sia M la matrice di adiacenza di un grafo G = (V(G), L(G)) con V(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 + M 2 + · · · + M n−1 non ha alcun elemento nullo. Idea della dimostrazione Implicazione ⇐ - 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 stanno nella 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 ripetuti e quindi cicli eliminabili; pertanto un tale percorso potrebbe essere "accorciato"). Cristina Turrini MATEMATICA DEL DISCRETO 1 0 0 0 Ad esempio M = 1 0 0 1 connesso dal momento che 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 + 1 0 0 0 0 1 è la matrice di un grafo non 0 0 C = I4 + M + M 2 + M 3 = 1 0 1 0 2 + 0 0 0 1 + 0 1 0 0 0 1 0 1 0 0 0 3 0 2 0 7 0 4 0 0 0 1 0 2 0 = 2 0 1 0 4 0 3 0 1 0 0 0 2 0 Cristina Turrini 0 1 1 0 0 1 0 0 0 2 0 2 MATEMATICA DEL DISCRETO 0 0 0 + 1