Topologia dei grafi



Grafo connesso

Un grafo con n vertici si dice connesso quando presi due nodi qualsiasi, esiste un cammino che li collega.

Grafo completo

Un grafo con n vertici si dice completo (totalmente connesso, cricca di ordine n, clique) quando ogni vertice è collegato a tutti gli altri n-1 vertici; si indica con Kn.

Grafo totalmente sconnesso (o grafo nullo)

Un grafo si dice totalmente sconnesso quando non ci sono archi.

Grafo planare

Un grafo si dice planare se può essere disegnato su un piano senza che i suoi archi si intersechino.
Osservazione: un grafo è non planare se contiene un sottografo isomorfo ad uno dei grafi K5 o K33

Esempio di applicazione dei grafi planari

Problema dei servizi

Tre case sono state costruite su un appezzamento di terreno e tre pozzi sono stati scavati per i bisogni dei loro abitanti.
La natura del clima e del terreno sono tali che l'uno o l'altro dei tre pozzi è spesso asciutto: quindi è necessario che le persone che abitano in ognuna delle tre case possano accedere a ciascuno dei tre pozzi.
Tuttavia gli abitanti delle tre case A,B e C si odiano, e quindi decidono di costruire i sentieri verso i tre pozzi X,Y e Z in modo tale da non doversi mai incontrare andando o tornando dai pozzi.
Il problema consiste nel tracciare i sentieri in modo che il grafo corrispondente sia planare, cioè senza alcuna intersezione fra i lati.
Il problema non ha soluzione, com'è dimostrato dal seguente teorema:

Teorema delle curve di Jordan

Sia K una curva piana continua chiusa; allora K divide il piano in una parte interna ed una parte esterna in modo tale che ogni qual volta si congiunga un punto P della parte interna con un punto Q della parte esterna mediante una curva continua L questa interseca la curva K.

Dal teorema segue che se 2 punti qualsiasi della curva chiusa K, come A ed Y, sono collegati da una curva (A,Y) che non abbia altri punti in comune con K, allora la curva (A,Y) è tutta all'interno o tutta all'esterno di K, ad eccezione dei suoi punti estremi A,Y.

Supponiamo ora che vi siano 4 punti su K posti nell'ordine ABYZ e che vi siano due curve (A,Y) e (B,Z) che non si intersechino: ciò è possibile solo quando una delle due curve giace internamente a K e l'altra esternamente.
Supponiamo infine che vi siano 6 punti su K posti nell'ordine AXBYCZ. In questo caso è impossibile che vi siano tre curve di collegamento (A,Y), (B,Z), (C,X) prive di intersezioni.
Le tre curve infatti devono trovarsi in due regioni, una interna a K e una esterna a K; quindi almeno una di quelle curve saranno nella stessa regione e, per quanto detto prima, questo porterebbe alla presenza di intersezioni.

(a,b)-cammino

è una sequenza ordinata di vertici e lati tale che a=a0,e1,a1, ...,en,an = b dove con ai abbiamo indicato i vertici e con ei gli archi.

Cammino chiuso (o ciclo)

è un cammino il cui vertice di arrivo coincide col vertice di partenza.

Grafo cordale

Un grafo si dice cordale se non contiene circuiti di lunghezza >= 4 che non hanno corde.

Cammino euleriano

è un cammino che non passa mai per lo stesso arco.

Linea di Eulero

è un cammino ciclico che percorre ogni arco una e una sola volta.

Esempio di applicazione delle linee di Eulero

Problema dei ponti di Koningsberg (Eulero)

La città di Koningsberg nella Prussia Orientale è situata sulle rive e su due isole del fiume Pregel.Le varie parti della città erano collegate da sette ponti.

La domenica i cittadini facevano la loro passeggiata per la città.
Ci si domandava allora se era possibile progettare questa passeggiata in modo tale che partendo da casa si potesse farvi ritorno dopo aver attraversato ciascun ponte una e una sola volta.
Le parti della città risultano 4,diciamo A,B,C e D, e siccome ci interessa soltanto l'attraversamento dei ponti, possiamo pensare ad A,B,C,D come ai vertici di un grafo collegati da archi corrispondenti ai ponti.

Eulero dimostrò che quel grafo non può essere percorso completamente in un solo cammino ciclico; cioè da qualsiasi vertice si incominci non si potrà esaurire il grafo e ritornare al punto di partenza senza attraversare più di una volta almeno uno dei 7 archi.
Un tale cammino dovrebbe infatti entrare in ciascun nodo tante volte quante vi esce; quindi richiede che in ciascun vertice vi sia un numero pari di archi incidenti (aventi cioè quel nodo come estremo), ma questa condizione non è soddifatta nel grafo che rappresenta la città.

Come si è visto una linea di Eulero deve entrare e poi uscire lo stesso numero di volte da ciascun vertice, cioè tutti i gradi locali devono essere pari.
Inoltre per avere una linea di Eulero il grafo deve essere connesso.
Quindi 2 condizioni necessarie perchè un grafo contenga una linea di Eulero sono: il grafo deve essere connesso e tutti i gradi locali devono essere pari.
Eulero dimostrò che queste condizioni sono anche sufficienti:

Teorema.

Un grafo connesso con i gradi locali pari ha una linea di Eulero.

Dim.

Supponiamo di iniziare un cammino Q da un vertice A e di proseguire finchè sia possibile, uscendo sempre da un vertice saguendo un arco non percorso prima.
Tale procedimento ha sicuramente termine poichè prima o poi mancheranno archi con una tale caratteristica. Ma dato che in ogni vertice gli archi incidenti sono in numero pari, c'è sempre un arco da cui uscire tranne che per il vertice iniziale A. Pertanto Q dovrà terminare in A.
Se Q passa per tutti gli archi, si è già ottenuta una linea di Eulero. In caso contrario ci sarà qualche vertice B appartenente a Q nel quale sono incidenti archi non percorsi da Q. E dato che Q ha un numero pari di archi incidenti in B, dovrà esservi anche un numero pari di archi incidenti in B che non appartengono a Q; lo stesso si può dire per tutti i vertici nei quali vi siano archi non percorsi.
Iniziamo ora un cammino R, partendo da B e usando solo archi che non appartengono a Q. Anche qui il cammino dovrà terminare in B. Ma avremo in questo caso ottenuto un cammino ciclico più ampio che parte da A, segue Q percorrendo un cammino da A a B, poi segue il cammino ciclico R fino a ritornare a B e finalmente segue ancora Q nella parte rimanente da B ad A.
Se l'intero grafo non è ancora stato esaurito potremo ampliare ulteriormente il cammino come fatto prima, fino ad ottenere una linea di Eulero.

Quando esiste un cammino Q che partendo da A termina in un altro vertice B percorrendo una e una sola volta tutti gli archi, allora Q deve partire da A secondo un certo arco ed eventualmente rientrarvi e ripartirne un certo numero di volte. Se quel cammino non termina in A, allora il verice A deve essere dispari. Per lo stesso motivo, B deve essere dispari e tutti gli altri nodi devono essere pari.
Si ha così:

Teorema.

Un grafo connesso possiede un cammino Q da A a B che ricopre tutti gli archi una e una sola volta se e solo se A e B sono i soli vertici dispari.

Dim.

Si può aggiungere un nuovo arco (A,B) in modo che tutti i vertici diventino pari.
Il nuovo grafo ha una linea di Eulero P in base al teorema precedente e se si elimina l'arco (A,B) dal cammino ciclico P il rimanente cammino è proprio Q.

Teorema.

Un grafo connesso avente 2K vertici dispari contiene una famiglia di K cammini distinti che tutti insieme percorrono ogni arco del grafo una ed una sola volta.

Cammino Hamiltoniano

è un cammino che non passa mai dallo stesso vertice.

Linea di Hamilton

è un cammino ciclico che percorre ogni vertice una e una sola volta.
(in generale non ricopre tutti gli archi; in realtà ricopre solo 2 archi per ogni vertice).

Punto di articolazione

Se in un grafo G esiste un nodo v che se rimosso fa in modo che G non sia più connesso, v si dice punto di articolazione.

Grafo k-connesso

Un grafo G si dice k-connesso se fra i suoi nodi ve ne sono almeno k che sono punti di articolazioni.

Esempio di applicazione delle linee di Hamilton

Nel 1859 il matematico Sir William Hamilton mise in circolazione uno strano rompicapo, il cui elemento principale era un dodecaedro regolare di legno.
Si trattava di uno dei cosiddetti poliedri regolari platonici, un poliedro che ha 12 facce pentagonali regolari; 3 lati di quei pentagoni si incontrano in ciascuno dei 20 vertici.
Ciascun vertice del dodecaedro di Hamilton era contrassegnato col nome di una città.
Il problema consisteva nel trovare un itinerario lungo gli spigoli che toccasse ciascuna città una e una sola volta; per rendere il gioco più difficile si potevano fissare in anticipo alcune delle città da toccare per prime.
Per poter poi ricordare quali città erano già state toccate, ogni vertice del dodecaedro era munito di un chiodo in modo che si poteva avvolgervi attorno uno spago man mano che il viaggio proseguiva.
Tuttavia essendo il dodecaedro poco agevole da maneggiare, Hamilton ne produsse una versione variata, in cui il poliedro era sostituito da un grafo planare isomorfo col grafo costituito dagli spigoli del dodecaedro.

Malgrado la somiglianza dei problemi che determinano se un grafo ha una linea di Eulero o se ha una linea di Hamilton, essi presentano difficoltà totalmente diverse:
per decidere se un grafo è un grafo di Eulero (avente cioè una linea di Eulero) è sufficiente esaminare se tutti i vertici sono pari; per individuare le linee di Hamilton invece non esiste ancora un criterio generale.

Insieme d'incidenza di un vertice v

è l'insieme I(v) di tutti gli archi connessi a v.

Insieme di adiacenza di un vertice v

è l'insieme A(v) dei vertici connessi a v.

Archi incidenti

sono tutti quegli archi aventi un vertice in comune.

Arco multiplo (a,b)

in un grafo c'è un arco multiplo (a,b) quando i vertici a e b sono collegati da più archi.

nota:
Invece di tracciare i vari archi che collegano i nodi a e b, si può anche disegnarne uno solo assegnandogli una molteplicità, che indichi quante volte questo arco va ripetuto.

Grado locale del vertice v

è il numero di archi incidenti nel verice v, e si indica con r(v).

nota:
Il numero N degli archi di un grafo avente i nodi A1, ...,An è dato da:
N = 1/2[r(A1)+...+r(An)].

Come conseguenza della formula precedente si ha che in ogni grafo la somma dei gradi locali di tutti i nodi è un numero pari, e precisamente il doppio del numero degli archi: 2N.

Vertice pari/dispari

è un vertice avente grado locale pari/dispari.

nota:
Un grafo ha sempre un numero pari di vertici dispari.

Grafo regolare di grado r

è un grafo in cui tutti i gradi locali dei suoi nodi sono uguali ad r.

nota:

Matrice di adiacenza

è una matrice V(G) * V(G) di valori booleani,nella quale l'elemento aij vale 1 se e solo se esiste l'arco (i,j).

nota:

Matrice libera delle adiacenze

è una matrice V(G) * V(G) che assegna ad ogni coppia di verici collegati da un arco il nome assegnato all'arco stesso, con la convenzione di mettere 1 sulla diagonale principale.

nota:
In questo caso quando si moltiplica la matrice per se stessa, si ottengono i cammini da un vertice ad un altro sottoforma di stringa di nomi degli archi, così si possono sapere quanti e quali sono i cammini d'interesse.
Calcoliamo il permanente della matrice libera delle adiacenze: cioè il determinante della matrice con tutte le componenti positive.
Indichiamo con path polynomial di G:

PP(G) = -1 + lim PERM(A)
p-> p

Dove p è il lato di porta, cioè un arco particolare che collega i nodi sorgente e terminale del grafo.
Il permanente di A è costituito da monomi sommati fra loro, alcuni di questi contengono p e altri no; tutti i monomi non contenenti p tendono a 0 per p che tende all'infinito.
Ciò che rimane sono i p-circuiti, cioè tutti quei circuiti che collegano la sorgente e il terminale ritornando alla sorgente e passanti per p.

I termini non contenenti la p vengono eliminati, tuttavia è sempre possibile recuperare tali circuiti facendo la somma modulo 2 dei monomi di PP(G).

Albero

è un grafo connesso privo di cicli.

nota:

Esempio di applicazione degli alberi

Supponiamo di avere la pianta di una tenuta agricola dei campi di riso presenti su di un'isola.
I campi sono circondati da argini di terra, e questi sono a loro volta circondati dalle acque di un lago.
Ora vogliamo allagare i campi aprendo alcuni argini.
Per sommergere tutti i campi è chiaro che occorre rompere un argine almeno in ogni circuito della pianta: i rimanenti argini intatti devono formare un grafo privo di circuiti.
Il problema è allora quello di determinare quante pareti è necessario perforare.

Tutto ciò si riconduce ad un problema generale riguardante i grafi: in un grafo connesso, qual'è il minimo numero di archi che occorre togliere affinchè non rimangano cicli?
Supponiamo di eliminare prima un arco E=(A,B) appartenente ad un ciclo del grafo. Allora il grafo rimane connesso perchè invece di andare da A a B passando per E, potremo seguire la parte rimasta del ciclo. Se vi sono altri cicli rimasti dopo aver eliminato E, elimineremo un altro arco nello stesso modo.
Continuando così dovremo arrivare ad un grafo connesso privo di cicli, cioè ad un albero.
Arrivati a questo punto è facile determinare gli archi soppressi. L'albero ottenuto ha lo stesso numero di vertici n che aveva il grafo di partenza e quindi ha n-1 archi. Quindi se il grafo di partenza aveva N archi, ne avremo soppressi esattamente m=N-n+1.
Questo numero si chiama rango dei cicli del grafo o numero ciclomatico.

Un'ulteriore applicazione degli alberi è quello di determinare il cammino in un grafo completo pesato (dove cioè ogni arco ha un determinato costo) in modo tale da collegare tutti i nodi nel modo più economico possibile.
Si ha che tale cammino dovrà necessariamente essere un albero, perchè in caso contrario potremmo togliere un arco da un ciclo e i nodi sarebbero ancora collegati fra loro. Quindi se ci sono n nodi, dovranno esserci n-1 archi.
Non tutti gli alberi estraibili dal grafo avranno però il minimo costo. Si dimostra che l'albero minimo, detto albero di economia, è quello ottenuto nel seguente modo:
dapprima si collegano i due nodi aventi come arco di collegamento quello di costo minimo; poi, in ciascuno dei successivi passi si aggiungerà l'arco di costo minimo possibile che, insieme agli archi già scelti, dia luogo ad un albero; se ci sono più archi di ugual costo non importa quale di essi viene scelto.

Clique number

è la dimensione di una delle clique massimali del grafo

Chromatic number

è il minimo numero di colori necessario per colorare il grafo.
(Il numero cromatico di un grafo è sempre al clique number).

Perfect graph G

sono tutti i grafi in cui il clique number è uguale al chromatic number e tali che per ogni sottografo G' di G si ha che il clique number di G' è uguale al chromatic number di G'.

Circuito spezzato (Broken Circuit)

Dato un grafo G, si fissa arbitrariamente un ordinamento ai suoi lati.
Un circuito spezzato B.C. è un sottoinsieme di lati che costituiscono un circuito di G, da cui tolgo il lato più grande secondo l'ordinamento imposto.

Delezione di un arco e

del(G,e) = G - e: operazione che consiste nell'eliminare da un grafo l'arco e.
Questa operazione equivale ad azzerare un elemento della matrice di adiacenza.

Contrazione di un arco

contr(G,e) = G \ e: operazione che consiste nel far coincidere gli estremi dell'arco e; dopo la contrazione l'arco viene eliminato.

Grafi isomorfi

Due grafi G = (V1,E1) e H = (V2,E2) sono isomorfi se esistono due funzioni biettive
: V1 V2 e : E1 E2 tali che ((a,b)) = ((a), (b)).
I grafi isomorfi hanno cioè la proprietà di mantenere l'incidenza dei lati.
Se due grafi sono isomorfi hanno lo stesso polinomio cromatico.

Grafi cromaticamente equivalenti

Due grafi si dicono cromaticamente equivalenti se hanno lo stesso polinomio cromatico.

Grafi cromomorfi

Due grafi si dicono cromomorfi se sono cromaticamente equivalenti ma non isomorfi.

Grafo parziale di un grafo G

è un grafo che ha gli stessi vertici di G e un sottoinsieme di archi.

Sottografo di un grafo G

è un grafo i cui vertici sono un sottoinsieme dei vertici di G e gli archi sono quelli che collegano i suoi vertici.

Spanning Tree di un grafo non orientato G

è un grafo parziale T=(V,E') di G, formato da tutti i nodi di G e da n-1 archi.
(è un albero; se G non è connesso non esiste lo spanning tree).

Ponte o istmo

Il lato e di un grafo connesso G si dice ponte di G se G-e non è connesso.

Teorema.

Un lato è un istmo se e solo se non appartiene a nessun circuito del grafo connesso G.

Dim.
1) Sia e un istmo di G connesso.
Supponiamo per assurdo che e appartenga ad un circuito di G. Se si sconnette e ed esiste un'altro arco che connette i due vertici estremi di e, allora tutte le coppie di vertici collegati in G lo sono ancora in G-e.
Oppure se eliminato l'arco e i due vertici estremi appartengono ancora ad un circuito, questi risultano ancora collegati; al contrario se i due vertici appartengono a due parti distinte connesse fra loro dall'arco e allora si nega l'ipotesi.

2) Il lato e non appartiene ad alcun circuito in G connesso.
Supponiamo per assurdo che e non sia un istmo. Allora eliminando e esiste ancora almeno un arco che rende connesso il grafo, ma questo implica che l'arco e appartiene ad un circuito (quello costituito da e da uno degli altri possibili archi che connettono le sue estremità).


Torna all'indice