Grafi

Grafi non sono altro che un insieme di entità collegato da un insieme di relazioni.

In quelli non pesati: problemi come ricerca del cammino minimo, componenti fortemente connesse, verifica ciclicità, ordinamento topologico

In quelli pesati: problemi come cammini di peso minimo, alberi di copertura, flusso massimo

Grafi orientati

Una coppia G = (V, E) dove:

• V è un insieme di nodi o vertici
• E è un insieme di coppie ordinate dette archi (edge)

Definizioni adiacente e incidente

• Adiacente: connesso
• Incidente: “dove va a finire”
  • in un grafo indiretto la relazione di adiacenza è simmetricaù

Usiamo questa notazione: n = | V | = vertici m = | E | = edges ⇒ archi

Ed è bene tener presente ciò:

• In un grafo non orientato: m ⇐ n(n-1) / 2 = O(n^2)
• In un grafo orientato: m ⇐ n^2 - n = O(n^2)

La complessità è espressa sia in termini di n che di m. SEMPRE!!!

Grado di un nodo

• Non orientati Numero di archi incidenti su di esso ⇒ ossia quanti collegamenti ha
• Orientati
  • in-degree: archi incidenti su di esso ⇒ quante frecce in entrata
  • out-degree: archi incidenti da esso ⇒ quante frecce in uscita

Cammino

Insieme di nodi connessi da una serie di archi.

Semplice: una volta sola

Memorizzare grafi

• Matrici di adiacenza
  • Grafi orientati
  • Grafi non orientati: spazio n^2
• Liste di adiacenza
  • orientato
  • non orientato: spazio = an + 2* bm

Perché n^2? Perché non so quali archi ci sono e devo scorrere tutte le righe per sapere chi c’è e chi non c’è…

Terminologia base

Concetti fondamentali:

• cammino (path): è una passeggiata dove non si passa mai più di una volta su un vertice
• passeggiata (walk): sequenza vertice, arco, verti, arco… che indica uno spostamento all’interno di un grafo da v1 a vN usando gli archi del grafo
• ciclo (cycle): cammino dove il primo vertice coincide con l’ultimo
• concetto di connessione: U → V significa V è raggiungibile da U
• componenti connesse: sottoinsieme di vertici che sono connessi tra loro
• albero: un grafo con num. archi = num. nodi - 1
• albero radicato: da un albero prendo un vertice e lo scelgo come radice
• foresta: un insieme di alberi

Visite dei grafi

Vogliamo visitare una e una sola volta tutti i nodi del grafo che possono essere raggiunti da un certo nodo.

Le visite più usate e conosciute sono:

• DFS: Depth First Search, visita in profondità

  • per ogni nodo adiacente si visita ricorsivamente tale nodo visitando i nodi adiacenti ecc…

• BFS: Breadth First Search, visita in ampiezza / per livello

  • prima si visita la radice, poi i nodi a distanza 1 dalla radice ecc…

• DFS

• BFS

Componenti connesse e fortemente

Le connesse e basta su grafi non orientati, le fortemente connesse su grafi orientati.

• Un grafo non orientato è connesso, se e solo se ogni suo nodo è raggiungibile da ogni altro suo nodo
• Un grafo non orientato è una componente connessa, se e solo se un suo sottografo è connesso e massimale

Applicazione DFS: componente connessa → trovare quante componenti connesse ci sono nel grafo

Applicazione DFS: trovare un ciclo

Aciclicità

Un grafo orientato è aciclico se e solo se non esistono archi all’indietro nel grafo.

Ordinamento topologico

• Ci sono archi solo da sinistra a destra.
• Se il grafo contiene un ciclo non esiste un ordinamento topologico.

Problema del topologico:

• Approccio naive: rimuovo man mano che vedo i nodi e sputo in out
• Basato su DFS: visita post order (topSort)
  • arrivo alle foglie incrementando un discovery time (contatore)
  • ogni volta che non posso fare più nulla, pusho in testa a una lista la foglia

Problema del strongly connected Grafo trasposto: archi al contrario

Usiamo Kosaraju:

• DFS di G
• G trasposto (Gt)
  • Copi i nodi
  • Copi gli archi avendo l’accortezza di cambiare v con u e viceversa
• DFS su Gt utilizzando cc, esaminando i nodi nell’ordine inverso di tempo di fine della prima visita