Cos’è un grafo

(1)

Università di L’Aquila

Ricerca Operativa

www.oil.univaq.it Grafi: Concetti fondamentali

Cos’è un grafo

Un grafo è un formalismo che definisce una relazione binaria su una collezione di oggetti.

Ad esempio:

città connesse da strade

calcolatori connessi in una rete telematica

persone legate da relazioni di parentela

persone che condividono una stanza

collegamenti tra componenti elettronici

operazioni che devono essere eseguite da una certa macchina

eventi causalmente legati nello spazio e/o nel tempo (inizio/fine di un’operazione, un trasporto, una giacenza in magazzino)

(2)

Corso di Ricerca Operativa 3

Grafi non orientati

Def.Un grafo non orientato(o simmetrico) G = (N , E) è una coppia di insiemi finiti dove:

N = {v₁,..., v_n} è l’insieme dei nodio vertici (| N | = n)

E = {e₁,.., e_m} ⊆ N × N è l’insieme degli archio spigoli non orienati (|E| = m)

Un arco non orientato è una coppia non ordinata di nodi distinti e_k= {v_i, v_j}

(oppure e_k= {i , j})

e_kindica che il nodo v_iè in relazione con il nodo v_j

Esempio

G = (N , E)

N = {v₁, v₂, v₃, v₄, v₅} E = {e₁, e₂, e₃, e₄, e₅, e₆}

e₁= {v₁, v₂} e₂= {v₁, v₃} e₃= {v₂, v₃} e₄= {v₂, v₅} e₅= {v₃, v₅} e₆= {v₃, v₄} v₁

e₁ v₂

v₃

v₅

v₄ e₂

e₃ e₄

e₅ e₆

(3)

Definizioni di base

Un arco {v,v} è detto loop

I nodi u,v ∈ N sono detti adiacenti⇔ {u,v} ∈ E. L’arco {u,v} si dice incidentesu u e su v

Gli archi e, f∈ E sono detti adiacenti⇔ e = {w,v} ed f = {v,u}

L’insieme di nodi N(v) = {z ∈ N: z adiacente a v} è detto intornodi v in G

L’insieme di archi d(v) = {e∈ E: e incide su v} è detto stelladi v in G

|d(v)| è detto gradodel nodo v

Esempio

v₁

e₁ v₂

v₃

v₅

v₄ e₂

e₃

e₄

e₅

e₆

v₁e v₂sono nodi adiacenti e e₁è l’arco incidente su v₁e v₂. e₁e e₄sono archi adiacenti.

N(v₂) = {v₁,v₃,v₅} è l’intorno del nodo v₂.

d(v₂) = {e₁, e₃, e₄} è la stella di v₂. Il grado di v₂è 3.

(4)

Isomorfismi

Def. Due grafi H = (W , F) e G = (N , E) sono detti isomorfise esiste una bijezione f: W ÆN tale che {u,v} ∈ F ⇔ {f(u),f(v)} ∈ E

Oss due grafi isomorfi rappresentano la stessa relazione.

v₁ v₂

v₃

v₅

v₄

v₁

v₂

v₃

v₅ v₄

Complemento,

Grafo completo e Grafo vuoto

Def. Sia G = (N , E) un grafo qualsiasi. Il grafo G = (N , (N × N) \ E) si dice grafo complementodi G.

Def.Il grafo K = (N , (N × N)) si dice grafo completoe il suo complemento K = (N , ∅) si dice grafo vuoto

(5)

Sottografi

Def. H = (W , F) è detto sottografodi G = (N , E) se e solo se W⊆ N e F ⊆ E

Def. H = (W , F) è detto sottografo indottoda W in G = (N , E) se e solo se W⊆ N e {u,v}∈F per ogni {u,v}∈E tale che u,v ∈W

Sottografo Sottografo indotto

Grafi orientati

Def.G = (N , E) è un grafo orientato(o diretto) se gli archi sono coppie ordinate di nodi (archi diretti).

e_k= {v_i, v_j} ≠ e_h= {v_j, v_i} e_k, e_h∈ E

v₂

v₁

v₃

v₄

v₅

(6)

Definizioni di base

Un arco diretto {v, u} si dice uscenteda v e entrantein u. v è detto nodo di partenza(o coda) e unodo di arrivo(o testa)

d⁺(v) = {e∈ E | e uscente da v} stella uscenteda v

d^–(v) = {e∈ E | e entrante in v} stella entrantein v

I(v) = {u∈ N | (u , v) ∈ E}nodi di partenzaper v

O(v) = {u∈ N | (v , u) ∈ E}nodi di arrivoda v

Cammini, percorsi, cicli

Dato un grafo non orientato G = (N , E)

Un camminoW_1kin G è una sequenza finita di nodi v₁, v₂,…, v_ktali che {v_i, v_i+1} ∈E. La lunghezzadel cammino è il numero di archi che lo compongono

La distanzatra i nodi u e v è la lunghezza minima di un cammino tra u e v

Un percorsoP_uvè un cammino W_uvche tocca ogni nodo una sola volta

Un cicloè un percorso v₁, v₂,…, v_kin cui v₁= v_k

(7)

Connessione

Def. Dato un grafo G = (N , E), un nodo v ∈ N si dice connessoa un nodo u ∈ N se esiste un cammino tra v e u in G

La relazione di connessione è di equivalenza, pertanto induce una partizione di N nei sottoinsiemi:

C_i= {v∈ N | v è connesso a u, ∀u ∈C_i} C_i∩ C_j= ∅ ∀i ≠ j ∪_iC_i= N Il sottografo indotto da C_iè detto componente connessadi G

Def. Un grafo G = (N , E) si dice connessose è composto da una sola componente connessa

Forte Connessione

Def. Dato un grafo orientato D = (N , E), un nodo v ∈ N si dice fortemente connessoa un nodo u ∈ N se esiste un cammino orientato tra v e u e un cammino orientato tra u e v

Le definizioni di componente fortemente connessae di grafo orientato fortemente connessosono analoghe alle definizioni date in precedenza

(8)

Grafi Bipartiti

Def.G = (N , E) è un grafo bipartitose

N = N₁∪ N₂

∀e = {u , v} ∈ E se u ∈ N₁allora v ∈ N₂oppure se v ∈ N₁allora u ∈ N₂

I grafi bipartiti sono spesso utilizzati nelle situazioni in cui il problema da modellare ha due classi diverse di elementi (fornitori, clienti oppure macchine, pezzi)

Alberi

Def.

Un grafo non orientato G = (N , E) è una foresta(o grafo aciclico) se non contiene cicli

Una grafo non orientato T = (N , E) è un alberose è una foresta connessa

Dato un albero T = (N , E), un nodo v∈ N è una fogliase |d(v)| = 1

Def. Dato un grafo connesso e non orientato G = (N , E), un albero ricoprenteè un albero T = (N , E₁) con E₁⊆ E

(9)

Proprietà degli alberi

Teorema:

a. Ogni albero con più di un nodo ha almeno una foglia.

b. Un grafo non orientato G = (N , E) è un albero se e solo se è connesso e ha | N | – 1 archi.

c. Per ogni coppia di nodi distinti u, v di un albero esiste un unico cammino da u a v.

d. Se aggiungiamo un arco ad un albero, il grafo risultante ha esattamente un ciclo.

Rappresentazioni

Matrici di adiacenza

Matrici di incidenza

Liste di adiacenza

(10)

Matrici di Adiacenza (1)

v₁ e₁

v₂

v₃

v₅

v₄ e₂

e₃ e₄

e₅ e₆

v1 v₂v₃v₄v₅

0 1 1 0 0 v₁ 1 0 1 0 1 v₂ 1 1 0 1 1 v₃ 0 0 1 0 0 v₄ 0 1 1 0 0 v₅ A_G=

Dato un grafo non orientato G = (N , E), la matrice di adiacenza nodi-nodi A_G(n × n) è A_G= [a_ij] con i, j = 1,…, n = |N|

e tale che a_ij= 1 se {v_i, v_j} ∈ E (v_i, v_jsono adiacenti) 0 altrimenti

Matrici di Adiacenza (2)

v₁ e₁

v₂

v₃

v₅

v₄ e₂

e₃ e₄

e₅ e₆

e1 e₂e₃e₄e₅e₆

1 1 1 1 0 0 e₁ 1 1 1 0 1 1 e₂ 1 1 1 1 1 1 e₃ 1 0 1 1 1 0 e₄ 0 1 1 1 1 1 e₅ 0 1 1 0 1 1 e₆ A_G=

Dato un grafo non orientato G = (N , E), la matrice di adiacenza archi-archi A_G(m × m) è A_G= [a_ij] con i, j = 1,…, m = |E|

e tale che a_ij= 1 se e_ie e_jsono adiacenti 0 altrimenti

(11)

Matrici di Incidenza (1)

v₁ e₁

v₂

v₃

v₅

v₄ e₂

e₃ e₄

e₅ e₆

1 1 0 0 0 0 v₁ 1 0 1 1 0 0 v₂ 0 1 1 0 1 1 v₃ 0 0 0 0 0 1 v₄ 0 0 0 1 1 0 v₅ E_G=

Dato un grafo non orientato G = (N , E), la matrice di incidenza nodi-archi E_G(n × m) è E_G= [a_ij] con i = 1,…, n = |N|, j = 1,…, m = |E|

e tale che a_ij= 1 se e_jè incidente su v_i 0 altrimenti

Matrici di Incidenza (2)

v₂

v₁ e₁

v₃

v₅

v₄ e₂

e₃ e₄

e₅ e₆

–1 1 0 0 0 0 v₁ 1 0 –1 –1 0 0 v₂ 0 –1 1 0 –1 –1 v₃ 0 0 0 0 0 1 v₄ 0 0 0 1 1 0 v₅ E_G=

Dato un grafo orientato G = (N , E), la matrice di incidenza nodi-archiè E_G(n × m) è E_G= [a_ij] con i = 1,…, n = |N|, j = 1,…, m = |E|

e tale che a_ij=

1 se v_iè la testa di e_j

0 altrimenti

–1 se v_iè la coda di e_j

Cos’è un grafo

Università di L’Aquila

Ricerca Operativa

www.oil.univaq.it Grafi: Concetti fondamentali

Cos’è un grafo

Un grafo è un formalismo che definisce una relazione binaria su una collezione di oggetti.

Grafi non orientati

Esempio

Definizioni di base

Esempio

Isomorfismi

Complemento,

Grafo completo e Grafo vuoto

Sottografi

Grafi orientati

Definizioni di base

Cammini, percorsi, cicli

Connessione

Forte Connessione

Grafi Bipartiti

Alberi

Proprietà degli alberi

Rappresentazioni

 Matrici di adiacenza

 Matrici di incidenza

 Liste di adiacenza

Matrici di Adiacenza (1)

Matrici di Adiacenza (2)

Matrici di Incidenza (1)

Matrici di Incidenza (2)

Matrici di adiacenza

Matrici di incidenza

Liste di adiacenza