Cenni teorici sui grafi (Teoria dei grafi) - Ricerca Operativa

CICLO

Un Ciclo è un cammino per il quale il vertice origine coincide con il vertice destinazione:

≡

1 {1,2,3,1}

Nell’esempio precedente un ciclo potrebbe essere

In un percorso ci possono essere uno o più cicli

GRAFO CONNESSO

Dati due vertici e si dice che è connesso a se esiste un cammino tra e

(, )

Un Grafo è Connesso se esiste un cammino tra ogni coppia di vertici.

Segue un esempio:

Se un Grafo non è connesso, si possono sempre individuare delle componenti connesse;

nell’esempio che segue si ha un grafo non connesso in cui le componenti connesse sono 3:

MATRICE DI INCIDENZA ×

= (, ) ∈ ℝ

La Matrice di Adiacenza di un Grafo è una matrice con numero di

vertici e numero di spigoli.

Ogni colonna della matrice è un vettore tale che:

+1 −

= {

+1 −

0

ESEMPIO

MATRICE DI ADIACENZA ×

= (, ) ∈ ℝ

La Matrice di Adiacenza di un Grafo è una matrice con numero di

vertici. ℎ

Ogni elemento della matrice è un elemento tale che:

+1 (, ) ∈

= {

0

ESEMPIO

ALBERO

Un Albero è un Grafo che soddisfa due proprietà:

• E’ connesso

• E’ aciclico

Un Albero Ricoprente di un certo grafo è un sottografo del grafo originale, include tutti i

vertici del grafo e ha un sottoinsieme degli archi del grafo, cioè quelli necessari a collegare

tutti i vertici tra di loro formando una struttura ad albero senza cicli.

GRAFO ALBERO RICOPRENTE

Se ad un albero ricoprente aggiungo uno spigolo si forma uno e un solo ciclo.

Se ad un grafo connesso si rimuove uno spigolo il grafo non sarà più connesso ma si

formeranno due alberi e cioè una Foresta.

Un grafo non connesso aciclico è una foresta.

1.1-DIGRAFI

DEFINIZIONE DI DIGRAFO = (, )

Un Digrafo è una struttura che si caratterizza per essere una coppia dove:

• è l’insieme dei nodi

• è l’insieme degli archi

Un arco è una coppia ordinata di nodi:

(, ) ∈ , ∈ (, ) ≠ (, )

ESEMPIO

Si consideri il seguente Digrafo: 2 4

1 6

3 5

In questo caso:

{1,2,3,4,5,6} (2,3), (2,4), (1,4), (3,1), (4,5), (4,1),

= = {(1,2), (4,6)}

PERCORSO ORIENTATO

= (, )

Dato un Digrafo un Percorso Orientato è una sequenza ordinata di nodi tali che

.

tra ogni coppia consecutiva di nodi nella sequenza esiste un arco nel Digrafo

{ }: ( )

= , , … , , ∈ = 1,2, … , − 1

1 2 +1 = {1,2,3,1,2,4,6}

Nell’esempio precedente un possibile percorso orientato è

CAMMINO ORIENTATO

= (, )

Dato un Digrafo un Cammino Orientato è un Percorso orientato che non

contiene vertici ripetuti.

{ }: ( )

= , , … , , ∈ = 1,2, … , − 1 ≠ ≠ ℎ , ℎ = 1, … ,

1 2 +1 ℎ

= {1,2,4,5}

Nell’esempio precedente un possibile cammino orientato è

CIRCUITO ORIENTATO

Un Circuito Orientato è un percorso per il quale il vertice origine coincide con il vertice

destinazione: ≡

1

CICLO ORIENTATO

Un Ciclo Orientato è un cammino per il quale il vertice origine coincide con il vertice

destinazione: ≡

1

GRAFO SOTTOSTANTE AD UN DIGRAFO

Dato un Digrafo possiamo sempre costruire il Grafo Sottostante, che si ottiene rimuovendo

l’orientazione dagli archi del digrafo ed eliminando eventuali archi doppi tra una coppia di

nodi. ⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗

(, (,

= ) = )

(,

≡ = {(, ): ) (, ) ∈

Si propone il grafo sottostante dell’esempio iniziale:

2 4

1 6

3 5

DIGRAFO FORTEMENTE CONNESSO

= (, ),

Dato un Digrafo questo è Fortemente Connesso se esiste un cammino

orientato tra ogni coppia di nodi

DIGRAFO DEBOLMENTE CONNESSO

= (, ),

Dato un Digrafo questo è Debolmente Connesso se il grafo sottostante è

connesso.

ARBORESCENZA (ESTERNA)

= (, ),

Dato un Digrafo questo è un’ Arborescenza Esterna se si verificano due

condizioni:

• Il grafo sottostante è un albero ricoprente

• Non esistono due archi entranti in uno stesso nodo

ARBORESCENZA (ESTERNA)

= (, ),

Dato un Digrafo questo è un’ Arborescenza Esterna se si verificano due

condizioni:

• Il grafo sottostante è un albero ricoprente

• Non esistono due archi entranti in uno stesso nodo

ARBORESCENZA (INTERNA)

= (, ),

Dato un Digrafo questo è un’ Arborescenza Interna se si verificano due

condizioni:

• Il grafo sottostante è un albero ricoprente

• Non esistono due archi uscenti da uno stesso nodo

ARBORESCENZA

= (, ),

Dato un Digrafo questo è genericamente un’ Arborescenza se è sia

un’arborescenza interna che esterna e quindi:

• Il grafo sottostante è un albero ricoprente

• Non esistono due archi incidenti in uno stesso nodo

ESEMPI Digrafo

2 4

1 3 5

Grafo che non è un’arborescenza (è Grafo sottostante

presente un ciclo) 2 4

1 3 5

Digrafo

2 4

1 3 5

Arborescenza Interna Grafo sottostante

2 4

1 3 5