Un grafo con n vertici si dice connesso quando presi due nodi qualsiasi, esiste un cammino che li collega.
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.
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
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:
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.
è 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.
è un cammino il cui vertice di arrivo coincide col vertice di partenza.
Un grafo si dice cordale se non contiene circuiti di lunghezza >= 4 che non hanno corde.
è un cammino che non passa mai per lo stesso arco.
è un cammino ciclico che percorre ogni arco una e una sola volta.
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:
Un grafo connesso con i gradi locali pari ha una linea di Eulero.
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ì:
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.
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.
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.
è un cammino che non passa mai dallo stesso vertice.
è 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).
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.
Un grafo G si dice k-connesso se fra i suoi nodi ve ne sono almeno k che sono punti di articolazioni.
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.
è l'insieme I(v) di tutti gli archi connessi a v.
è l'insieme A(v) dei vertici connessi a v.
sono tutti quegli archi aventi un vertice in comune.
in un grafo c'è un arco multiplo (a,b) quando i vertici a e b sono collegati da più archi.
è il numero di archi incidenti nel verice v, e si indica con r(v).
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.
è un vertice avente grado locale pari/dispari.
è un grafo in cui tutti i gradi locali dei suoi nodi sono uguali ad r.
è 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).
è 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.
| 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).
è un grafo connesso privo di cicli.
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.
è la dimensione di una delle clique massimali del grafo
è il minimo numero di colori necessario per colorare il grafo.
(Il numero cromatico di un grafo è sempre
al clique number).
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'.
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.
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.
contr(G,e) = G \ e: operazione che consiste nel far coincidere gli estremi dell'arco e; dopo la contrazione l'arco viene eliminato.
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.
Due grafi si dicono cromaticamente equivalenti se hanno lo stesso polinomio cromatico.
Due grafi si dicono cromomorfi se sono cromaticamente equivalenti ma non isomorfi.
è un grafo che ha gli stessi vertici di G e un sottoinsieme di archi.
è un grafo i cui vertici sono un sottoinsieme dei vertici di G e gli archi sono quelli che collegano i suoi vertici.
è 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).
Il lato e di un grafo connesso G si dice ponte di G se G-e non è connesso.
Un lato è un istmo se e solo se non appartiene a nessun circuito del grafo connesso G.
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