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

Cenni sulla teoria dei grafi

Grafi

Definizione di grafo: Un grafo è una struttura che si caratterizza per essere una coppia di insiemi (V, E) dove:

• V (|V| = n) è l’insieme dei nodi
• E (|E| = m) ⊆ V × V è l’insieme degli spigoli

Uno spigolo è una coppia non ordinata di vertici: (u, v) ∈ E, u ∈ V (u, v) ≡ (v, u). La notazione per la rappresentazione di uno spigolo sarà la seguente:

Esempio

Si consideri il seguente grafo: {1, 2, 3, 4}, con spigoli {(1, 3), (1, 4), (2, 3), (4, 3)}.

Percorso

Dato un grafo, un percorso è una sequenza ordinata di vertici tali che tra ogni coppia consecutiva di vertici nella sequenza esiste un arco nel grafo. Un percorso può contenere anche vertici ripetuti.

Esempio: {v₁, v₂, …, v_k} con v_i ∈ V e i = 1, 2, …, k-1.

Nell’esempio precedente, un possibile percorso è {1, 2, 3}.

Cammino

Dato un grafo, un cammino è un percorso che non contiene vertici ripetuti.

{v₁, v₂, …, v_k} con v_i ∈ V e i = 1, 2, …, k-1, v_i ≠ v_j ∀ i ≠ j.

Circuito

Un circuito è un percorso per il quale il vertice origine coincide con il vertice destinazione.

Esempio: {1, 2, 3, 4, 2, 1}.

Ciclo

Un ciclo è un cammino per il quale il vertice origine coincide con il vertice destinazione.

Esempio: {1, 2, 3, 1}.

In un percorso ci possono essere uno o più cicli.

Grafo connesso

Dati due vertici u e v, si dice che u è connesso a v se esiste un cammino tra u e v. 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 incidenza di un grafo è una matrice con numero di vertici e numero di spigoli.