Nozioni, Ricerca operativa

Ricerca operativa – grafi

Problemi affrontati nel corso

I problemi che affronteremo in questo corso sono i seguenti:

• Come collegare a costo minimo i nodi di un grafo
• Come trovare in un grafo il cammino più breve o a minor costo
• Come massimizzare il flusso che scorre all'interno di una rete
• Come trovare il flusso di costo minimo che scorre nella rete

Definizioni di grafo

Un grafo non orientato G = (V, E) è una coppia formato da due insiemi: V sono i vertici (nodi) ed E sono i lati (archi) non orientati.

• Un lato di un grafo (i, j) è una coppia non ordinata di vertici.
• Si dice che un lato (i, j) ha due vertici terminali: i e j.
• Un lato (i, j) è incidente sui vertici terminali e li collega.
• Due lati si dicono adiacenti se hanno un vertice in comune (e.g. lati (A, B) e (A, C)).
• Due vertici si dicono adiacenti se esiste un lato che li collega, ovvero un lato incidente ad entrambi (e.g. vertici A e B).

In un grafo pesato ha i lati/vertici con associati ad esempio costi, lunghezze, capacità o altro. Per un grafo pesato sugli archi, il peso del generico arco (i, j) si scrive c_ij.

Grado d(i) di ogni nodo i = numero di archi ad esso adiacenti.

Stella δ(i) = archi adiacenti al nodo i esplicitati.

Cammino = sequenza di lati adiacenti.

Cammino semplice = se non visita mai due volte lo stesso vertice.

Cammino elementare = se non attraversa mai due volte lo stesso lato.

Lunghezza del cammino = numero di archi attraversati dal cammino.

Un ciclo è un cammino i cui nodi iniziali e terminali coincidono.

Un grafo che non contiene cicli è detto aciclico.

Grafi connessi e disconnessi

• Due nodi i e j sono connessi se nel grafo esiste almeno un cammino che inizia nel nodo i e termina nel nodo j.
• Un grafo si dice connesso se ogni coppia di nodi è connessa, altrimenti si dice che il grafo è disconnesso.
• Una componente di un grafo è un sottografo massimale connesso.
• Un arco che se rimosso genera un grafo disconnesso si chiama ponte.
• Un nodo che se rimosso genera un grafo disconnesso si chiama cutvertex.

Tagli

• Taglio in un grafo = partizione dell’insieme dei nodi in due insiemi S e S' = V – S che non hanno vertici in comune.
• Ogni taglio definisce un insieme di archi [S, S'] con estremità in S ed S'.
• Un taglio s–t definisce un taglio che ha il nodo s in S ed il nodo t in S'.
• In figura si ha S = {1, 2, 3} ed S' = {4, 5, 6}. Gli archi [S, S'] sono gli archi (2,6), (2,4) e (3,5).

Grafo orientato: notazioni

Grafo orientato = tutti i lati sono coppie orientate => arco (i, j) è diverso da arco (j, i).

• Nodo testa di un arco (i,j) = i.
• Nodo coda di un arco (i,j) = j.
• Arco entrante il nodo j = (i,j).
• Arco uscente il nodo i = (i,j).
• Grado degli archi uscenti d⁺(i). Esempio: d⁺(1) = 1, d⁺(2) = 2.
• Grado degli archi entranti d^-(i). Esempio: d^-(1) = 1, d^-(2) = 2.

Proprietà: per ogni i in V vale d(i) = d⁺(i) + d^-(i). Esempio: d(1) = 2, d(2) = 4.

Cammino orientato

• Cammino orientato: Cammino composto da tutti archi aventi la stessa direzione.
• Grafo fortemente connesso: per ogni coppia di nodi esiste un cammino orientato in entrambe le direzioni.
• [S, S']⁺ sono tutti gli archi uscenti dall’insieme S ed entranti nell’insieme S'.
• [S, S']^- sono tutti gli archi entranti nell’insieme S (testa in S) ed uscenti dall’insieme S' (coda in S').
• [S, S]⁺ equivale a δ⁺(S) ovvero stella di nodi uscenti da S.
• Grafo in figura sopra: non è un multigrafo e non è fortemente connesso.

Grafo orientato: esercizio

Calcolare le componenti connesse e fortemente connesse per il grafo:

Le componenti connesse sono {1,2,3,4,5,6,7} e {8,9} dato che esiste un cammino non orientato tra ogni coppia di nodi in ciascuna componente mentre non esiste un cammino tra nodi di componenti diverse.

Le componenti fortemente connesse sono {1}, {3}, {2,4,5,6,7}, {8}, {9} dato che due nodi i e j sono fortemente connessi se esiste un cammino orientato da i a j ed esiste un cammino orientato da j a i.

Matrice di incidenza di un grafo orientato

Matrice di incidenza nodo – arco

• La matrice di incidenza nodo-arco è una matrice n × m che contiene una riga per ogni nodo del grafo ed una colonna per ogni arco.
• La colonna per l’arco (i, j) ha solo due valori non nulli per la riga i e la riga j.
• Esempio: La prima colonna si riferisce all’arco (1, 2) tra il nodo 1 ed il nodo 2.
• In generale è una struttura efficiente in quanto ha 2m elementi non nulli su mn elementi totali. Ma è considerevole lo spreco di memoria...

Matrice di adiacenza nodo – nodo

• La matrice di adiacenza nodo-nodo è composta da n righe ed n colonne.
• Se un elemento vale 1 vuol dire che è presente un arco tra il nodo i e il nodo j.
• Esempio: L’elemento non nullo dell’ultima riga si riferisce all’arco (2, 6).
• La matrice di adiacenza contiene m elementi non nulli su n² elementi totali.
• Grafi sufficientemente densi: è una struttura dati efficiente.
• Grafi non orientati: è una struttura simmetrica, per cui si dimezza la memoria.

Liste di adiacenza

Lista di adiacenza = per ogni nodo contiene una lista di archi adiacenti. Ogni elemento contiene l’altra estremità dell’arco e i suoi eventuali valori associati (peso, costo, capacità).

Esempio: La prima riga riguarda il nodo 1 e gli archi (1, 2) e (1, 3). Le liste di adiacenza sono implementate usando liste e puntatori, e sono strutture dati efficienti anche per grafi sparsi.

Grafo completo

Un grafo G è detto un grafo completo (detto anche clique) se esiste un arco per ogni coppia di nodi.