Teoria dei grafi

TEORIA DEI GRAFI

Un GRAFO è un modo per rappresentare visivamente una relazione tra diversi oggetti o elementi.

È composto da due componenti principali: i nodi (o vertici) e gli archi.

I nodi rappresentano gli elementi della collezione di cui si sta studiando la relazione.

Gli archi rappresentano le connessioni o le relazioni tra i nodi.

Un GRAFO ci permete di comprendere e studiare la complessità e la strutura matema�ca

di un problema.

TEORIA DEI GRAFI

La teoria dei grafi si occupa dello studio degli ogge� chiama� grafi. Ques� grafi rappresentano

relazioni tra elemen� e sono u�lizza� per risolvere problemi di o�mizzazione in diverse situazioni

reali. Analizzare le proprietà dei grafi ci aiuta a comprendere quanto sia complesso un problema e

a valutare l'efficacia degli algoritmi per risolverlo in casi specifici. In sintesi, la teoria dei grafi è uno

strumento per comprendere e risolvere problemi complessi u�lizzando un'astrazione grafica.

GRAFI NON ORIENTATI

GRAFI NON ORIENTATI (O SIMMETRICI)

Un grafo G=(V,E) è una coppia di insiemi fini�.

Dove: V = nodi o (ver�ci) V = {1, 2, ...}

• E = archi o (spigoli) E = {a, b, …} V V

• ⊆ ×

ESEMPIO:

ADIACENZA E INCIDENZA (DEFINIZIONE)

NODI

• ARCHI

•

INTORNO E STELLA (DEFINIZIONE)

PROPRIETÀ ELEMENTARI n m

Sia G = (V , E) un grafo simmetrico con nodi e archi.

GRAFI DIVERSI O UGUALI? Stesso grafo ma

disegnato

differentemente

Grafi diversi

(insieme di

vertici diversi)

ma stessa

struttura

ISOMORFISMI

(Una biiezione è una corrispondenza uno a uno tra due insiemi, in cui ogni elemento del primo insieme è

associato esattamente a un elemento del secondo insieme, e viceversa).

QUINDI:

Due grafi sono isomorfi quando hanno la stessa strutura, cioè gli stessi nodi e gli stessi archi.

ESEMPIO:

GRAFO COMPLETO

QUINDI:

Un grafo completo è un �po di grafo in cui ogni coppia di nodi è collegata da un arco.

ESEMPIO:

GRAFO COMPLEMENTO

QUINDI:

Un grafo complemento è un conceto che riguarda due grafi. Il grafo complemento di un grafo dato

ha gli stessi nodi, ma gli archi sono collega� in modo inverso rispeto all'originale. Se due nodi non

sono collega� nel grafo originale, saranno collega� nel grafo complemento e viceversa. In sostanza,

il grafo complemento rappresenta le relazioni mancan� nel grafo originale.

ESEMPIO: H è il grafo complemento di G

GRAFO VUOTO

QUINDI:

Un grafo vuoto è un grafo che non ha né nodi né archi. È come una pagina bianca senza disegni o

connessioni. Non c'è nessuna informazione o relazione rappresentata nel grafo vuoto.

PERCORSO

QUINDI:

Un percorso in un grafo è una sequenza di nodi collega� tra loro tramite gli archi.

ESEMPIO:

CICLO

QUINDI:

Un ciclo in un grafo è una sequenza di nodi collega� in modo tale che si possa tornare al nodo di

partenza atraverso gli archi.

ESEMPIO:

GRAFO PARZIALE

ESEMPIO: Stessi NODI

• Alcuni ARCHI

•

SOTTOGRAFO

QUINDI:

Un sotografo è un grafo più piccolo che viene otenuto prendendo solo alcuni nodi e archi da un

grafo più grande.

ESEMPIO: Alcuni NODI

• Alcuni ARCHI

•

(Non è INDOTTO perche il nodo 1 non è collegato con il nodo 4)

SOTTOGRAFO INDOTTO

QUINDI:

Un sotografo indoto è un sotoinsieme di nodi e archi di un grafo più grande, in cui vengono

preservate tute le connessioni tra i nodi del sotoinsieme. È come prendere una parte del grafo

originale e vedere solo gli elemen� e le relazioni che esistono in quel sotoinsieme.

ESEMPIO:

CAMMINI DI UN GRAFO

QUINDI:

Un cammino di un grafo è una sequenza di nodi o archi adiacen�.

I nodi estremi, anche conosciu� come "nodi terminali" o "nodi di estremità", sono i nodi in un

cammino di un grafo che rappresentano il punto di partenza e il punto di arrivo del cammino

(il sottografo corrispondente al cammino in generale non è isomorfo a un percorso)

ESEMPIO: P = [{4,1}, {1,3}, {3,4}, {4,2}, {2,3}]

Estremi: nodi 4 e 3

PASSEGGIATE DI UN GRAFO

QUINDI:

Un cammino in un grafo è chiamato "elementare" o passeggiata se gli archi che atraversa non

sono gli stessi (non ripassa per lo stesso arco), anche se i nodi possono essere visita� più volte

lungo il percorso. Quindi parte dal nodo di inizio e arriva al nodo di fine senza mai passare per un

arco già percorso.

(il sottografo corrispondente alla passeggiata in generale non è isomorfo a un percorso)

ESEMPIO (grafo elementare): P = [{4,1}, {1,3}, {3,4}, {4,2}]

Estremi: nodi 4 e 2

Un esempio di un grafo non elementare

potrebbe essere un grafo in cui un cammino

attraversa più volte lo stesso arco.

PERCORSI DI UN GRAFO

:

QUINDI non

Un cammino in un grafo è chiamato percorso se gli archi e i nodi che atraversa sono gli stessi

(non ripassa per lo stesso arco e per lo stesso nodo). Quindi parte dal nodo di inizio e arriva al

nodo di fine senza mai passare per un arco e nodo già percorso.

(il sottografo corrispondente al percorso è isomorfo a un percorso Pk . Si dice anche che un grafo G

contiene un percorso Pk)

:

ESEMPIO P = [{1,3}, {3,4}, {4,2}]

Estremi: nodi 1 e 2

CHIUSI

CAMMINI, PASSEGGIATE E PERCORSI

:

ESEMPIO C = [{1,3}, {3,4}, {4,2}, {2, 1}]

NOTA:

il sottografo corrispondente a un cammino (o passeggiata) chiuso/a in generale non è isomorfo a

un ciclo.

CICLO DI UN GRAFO

Un grafo G con�ene un ciclo C se ammete un sotografo isomorfo a C

k k

In altre parole, Un ciclo in un grafo è una sequenza di archi che permete di tornare al punto di

partenza.

:

ESEMPIO

GRAFO ACICLICO

CONNESIONE – GRAFI CONNESSI

:

ESEMPIO (GRAFO NON CONNESSO) I nodi 3 e 2 sono connessi

• I nodi 1 e 5 non sono connessi

•

In questo esempio no�amo che la relazione di connessione par�ziona il grafo G in componen�

connesse.

Infa�:

Il grafo G è formato dalle 2 componen� connesse C1 e C2, perciò non è connesso.

QUINDI:

un grafo si dice CONNESSO se è composto da una sola componente connessa.

In altre parole, due grafi sono connessi quando esiste un percorso tra qualsiasi coppia di nodi

all'interno di ciascun sotografo.

CAMMINO E CICLO EULERIANO

:

CAMMINO

ESEMPIO EULERIANO P = [{3, 1}, {1, 5}, {5, 2}, {2, 1} {1, 4}, {4, 2}, {2, 3}, {3, 4}]

(I numeri negli archi rappresenta l’ordine di percorrenza)

CICLO

ESEMPIO EULERIANO: C = [{3, 1}, {1, 5}, {5, 2}, {2, 1} {1, 4}, {4, 2}, {2, 3}, {3, 4}, {4, 6}, {6, 3}]

(I numeri negli archi rappresenta l’ordine di percorrenza)

QUINDI:

Un cammino euleriano è un cammino in un grafo che atraversa tu� gli archi una sola volta,

mentre un ciclo euleriano è un cammino euleriano che inizia e termina nello stesso nodo.

TEOREMA DI EULERO

:

QUINDI

Il Teorema di Eulero fornisce una condizione necessaria e sufficiente per un grafo simmetrico (non

direto) affinché sia euleriano, cioè ammeta un ciclo euleriano.

Secondo il teorema, un grafo simmetrico è euleriano se e solo se soddisfa due condizioni:

1. Il grafo deve essere connesso, il che significa che esiste un cammino tra ogni coppia di nodi

del grafo.

2. Ogni nodo del grafo deve avere un grado pari, ossia il numero di archi adiacen� al nodo. Il

grado pari significa che ogni volta che si entra o si esce da un nodo, si u�lizzano due archi,

mantenendo così il bilancio e permetendo un percorso che atraversa tu� gli archi del

grafo senza ripe�zioni.

Queste due condizioni insieme garan�scono l'esistenza di un ciclo euleriano nel grafo simmetrico.

PERCORSO HAMILTONIANO

QUINDI: atraversa ogni nodo una sola volta,

Un percorso hamiltoniano in un grafo è un percorso che

visitando tu� i nodi senza ripe�zioni, partendo da un nodo di inizio fino ad un nodo di fine

ESEMPIO: P = [{3, 1}, {1, 5}, {5, 2}, {2, 4}]

CICLO HAMILTONIANO

QUINDI:

Un ciclo Hamiltoniano in un grafo è un percorso che passa per ogni nodo del grafo esatamente

una volta e ritorna al punto di partenza.

ESEMPIO: C = [{3, 1}, {1, 5}, {5, 2}, {2, 1} {1, 4}, {4, 2}, {2, 3}, {3, 4}, {4, 6}, {6, 3}]

GRAFI HAMILTONIANI

CONDIZIONI NECESSARIE

Se un grafo G = (V, E) è hamiltoniano, allora valgono le seguen� proprietà:

1. Ogni nodo v in V ha un grado maggiore di 2, cioè è connesso ad almeno tre archi. Questo

significa che ogni nodo ha almeno due possibili percorsi da seguire.

2. Il grafo G non ha "cut-edges" (archi che, se rimossi, dividono il grafo in due componen�

connesse separate). La rimozione di un arco non deve creare una separazione nel grafo che

impedisca la visita di tu� i nodi in un unico percorso.

3. Il grafo G non ha "cut-ver�ces" (nodi che, se rimossi insieme ai loro archi adiacen�,

dividono il grafo in due o più componen� connesse separate). La rimozione di un nodo e

dei suoi archi adiacen� non deve impedire la visita di tu� gli altri nodi in un unico percorso.

CONDIZIONI SUFFICIENTI

Questi teoremi forniscono condizioni sufficienti per identificare la presenza di cicli hamiltoniani in

un grafo.

TEOREMA DI ORE

• Il Teorema di Ore, stabilisce che se hai un grafo G = (V, E) con almeno 3 nodi e la somma dei

gradi di due nodi non adiacen� è maggiore del numero totale dei nodi (n), allora il grafo è

hamiltoniano. In altre parole, se per ogni coppia di nodi non collega� u e v, la somma dei

loro gradi supera il numero totale dei nodi, allora il grafo con�ene un ciclo hamiltoniano.

TEOREMA DI DIRAC

• Il Teorema di Dirac, fornisce una condizione più specifica. Afferma che se hai un grafo G =

(V, E) con almeno 3 nodo e il grado di ogni nodo u è maggiore della metà del numero totale

di nodi (n/2), allora il grafo è hamiltoniano. In altre parole, se ogni nodo ha un grado che

supera la metà del numero totale dei nodi, allora il grafo con�ene un ciclo hamiltoniano.

OSSERVAZIONE:

La classe dei grafi hamiltoniani non contiene né è contenuta nella classe dei grafi euleriani.

Ci sono grafi euleriani che non sono hamiltoniani.

Ci sono grafi hamiltoniani che non sono euleriani.

FORESTE

:

QUINDI

Una foresta è un �po par�colare di grafo non orientato che non con�ene cicli. Ciò significa che non

ci sono sequenze di connessioni che ritornano al punto di partenza.

ESEMPIO:

ALBERI

QUINDI:

Un albero è una par�colare strutura di grafo che soddisfa due condizioni:

È connesso, il che significa che esiste un percorso tra qualsiasi coppia di nodi.

• Non con�ene cicli.

•

ESEMPIO: I nodi arancioni

sono foglie

CARATTERIZZAZIONE E PROPRIETÀ

SPIEGAZIONE:

Un grafo simmetrico G = (V, E) è un albero se e solo se soddisfa due condizioni:

È connesso: Ciò significa che esiste un percorso tra ogni coppia di nodi nel grafo, cioè non ci

• sono nodi isolati.

Ha |V| - 1 archi: Il numero di archi nel grafo è esattamente uguale al numero di nodi meno

• uno. Questo implica che ogni nodo, ad eccezione della radice, ha esattamente un arco

entrante, formando una struttura gerarchica.

SPIEGAZIONE:

Consideriamo T=(V,E) un albero

1. T ha almeno una foglia: Un albero T deve avere almeno un nodo foglia, che è un nodo che

non ha nessun arco uscente. In altre parole, è un nodo terminale senza figli.

2. Esiste un unico cammino da u a v, per ogni u,v V: In un albero, c'è un unico percorso tra

∈

due nodi qualsiasi. Questo significa che per ogni coppia di nodi u e v nell'albero, c'è

esattamente un cammino che li collega.

3. Se aggiungiamo un arco a E, il grafo risultante ha esattamente un ciclo: Se prendiamo un

albero T e aggiungiamo un arco tra due nodi diversi, il grafo risultante avrà esattamente un

ciclo. Questo perché l'aggiunta di un arco crea una connessione aggiuntiva che forma un

ciclo.

4. Se rimuoviamo un arco da E, il grafo non è più connesso: Se prendiamo un arco in un albero

T e lo rimuoviamo, il grafo risultante non sarà più connesso. Questo significa che ci saranno

nodi isolati che non possono essere raggiunti da altri nodi.

GRAFO BIPARTITO

QUINDI:

Un grafo bipar�to è un grafo in cui i nodi possono essere divisi in due gruppi dis�n�, chiama� V1 e

V2. L'importante è che gli archi del grafo collegano solo nodi di gruppi diversi, ovvero un estremo

dell'arco è in V1 e l'altro estremo è in V2. Inoltre, l'unione di V1 e V2 deve includere tu� i nodi del

grafo G.

ESEMPIO:

GRAFO BIPARTITO COMPLETO

QUINDI:

Un grafo bipar�to completo è un grafo in cui ogni nodo di un gruppo è collegato a tu� i nodi

dell'altro gruppo e viceversa. Questo significa che non ci sono nodi all'interno dello stesso gruppo

che sono collega� tra di loro. Il grafo bipar�to completo con |V1| = p e |V2| = q viene indicato

come Kp,q.

ESEMPIO: p=2

• q=4

•

TEOREMA

QUINDI:

Il teorema stabilisce che se un grafo ha cicli di lunghezza dispari, allora non può essere bipar�to. Al

contrario, se un grafo non ha cicli di lunghezza dispari, allora può essere suddiviso in due gruppi

dis�n� e quindi è bipar�to. Quindi, osservando i cicli nel grafo, possiamo determinare facilmente

se è bipar�to o no.

GRAFO PLANARE

QUINDI:

Un grafo è planare se può essere disegnato su un piano in modo che gli archi non si intersechino

tra loro.

La carateris�ca dis�n�va di un grafo planare è che può essere visualizzato senza che gli archi si

taglino o si sovrappongano nel disegno sul piano.

ESEMPIO:

CARATTERIZZAZIONE DEI GRAFI PLANARI (TEOREMA DI KURATOWSKI)

QUINDI:

Il teorema di Kuratowski stabilisce che un grafo è planare (può essere disegnato senza intersezioni

degli archi sul piano) se e solo se non con�ene alcun sotografo che sia omeomorfo (simile) a K5

(grafo completo con 5 nodi) o a K3,3 (grafo bipar�to completo con 3 nodi in ogni gruppo).

GRAFI ORIENTATI

ARCO ORIENTATI

QUINDI:

Un arco orientato è un �po di connessione tra due nodi in un grafo in cui c'è una direzione

specifica.

GRAFI ORIENTATI (DIRETTI O ASIMMETRICI)

QUINDI:

Un grafo orientato è un �po di grafo in cui gli archi hanno una direzione specifica.

ESEMPIO:

SUPPORTO SIMMETRICO

QUINDI:

Il supporto simmetrico di un grafo orientato è un nuovo grafo che si o�ene rimuovendo le frecce

dagli archi e combinando gli archi duplica�.

ESEMPIO:

INTORNO DI GRAFI ORIENTATI

QUINDI:

l'intorno di un nodo v include tu� i nodi che sono collega� a v tramite un arco entrante (nodi di

arrivo) e tu� i nodi a cui v è collegato tramite un arco uscente (nodi di partenza).

ESEMPIO:

STELLA DI GRAFI ORIENTATI

QUINDI:

La stella di un nodo in un grafo orientato si riferisce all'insieme dei suoi archi uscen� e entran�. La

notazione δ(v) rappresenta la stella di un nodo v e si o�ene unendo l'insieme dei suoi archi uscen�

δ (v) e l'insieme dei suoi archi entran� δ (v).

+ -

(v) rappresenta la stella uscente da v, ovvero tu� gli archi che partono da v e si

L'insieme δ +

• dirigono verso altri nodi nel grafo.

L'insieme δ (v) rappresenta la stella entrante in v, ovvero tu� gli archi che arrivano a v da

-

• altri nodi nel grafo.

ESEMPIO:

CAMMINI PERCORSI E CICLI DEI GRAFI ORIENTATI

CAMMINI: Un cammino in un grafo orientato è una sequenza di nodi e archi che

• connetono un nodo di partenza a un nodo di des�nazione. Ogni arco nel cammino deve

seguire la direzione specifica del grafo orientato.

PERCORSI: Un percorso in un grafo orientato è un cammino che non con�ene nodi ripetu�.

• Significa che non possiamo visitare lo ste