Grafo

Da Wikipedia, l'enciclopedia libera.

I grafi sono l'oggetto di studio della teoria dei grafi e trovano applicazioni in diversi ambiti che vanno dalla topologia all'informatica.

Possiamo immaginare geometricamente un grafo come un insieme di punti nello spazio e di curve continue che connettono coppie di punti senza intersecarsi tra loro.

[modifica] Definizioni fondamentali

Nella teoria dei grafi si dice grafo (da non confondere con grafico) una figura costituita da punti, detti vertici o nodi, e da linee che li uniscono, dette lati o spigoli o archi. Più formalmente, dati un insieme V di nodi e un insieme E di archi un grafo G è un insieme G = (V, E).

Ogni arco e ∈ E connette due vertici u ∈ V e v ∈ V, che prendono nome di estremi dell'arco; per questo motivo spesso un arco e viene identificato con la coppia formata dai suoi estremi (u,v). Un grafo può quindi essere pensato come un insieme di vertici V ed un insieme di coppie E, dove gli elementi di ciascuna coppia appartengono a V.

Un arco che ha due estremi coincidenti si dice cappio, mentre più archi che connettono gli stessi due estremi danno origine ad un multiarco.

Un grafo sprovvisto di cappi e di multiarchi si dice grafo semplice. In caso contrario si parla di multigrafo.

Lo scheletro sk(G) di G è il grafo che si ottiene da G eliminandone tutti i cappi e sostituendone ogni multiarco con un solo arco avente gli stessi estremi.

Il numero di archi incidenti in un vertice v ∈ V prende nome grado di v. Si considerano il grado massimo e il grado minimo di G come, rispettivamente, il grado del vertice di G con il maggior numero di archi incidenti e il grado del vertice di G che ha meno archi incidenti.

Quando il grado massimo ed il grado minimo coincidono con un numero k, si è in presenza di un grafo k-regolare (o più semplicemente grafo regolare).

Un caso estremo di grafo è un grafo costituito da un solo nodo, detto grafo nullo.

[modifica] Grafi orientati e grafi semplici

Si distinguono due tipi basilari di grafi, i grafi orientati e i grafi non orientati.

Un grafo orientato D (o digrafo, grafo diretto) è un insieme D = (V, A), dove V è l'insieme dei vertici di D e A è l'insieme degli archi orientati di D. Un arco orientato è un arco caratterizzato da una direzione. In particolare, è composto da una testa (rappresentata solitamente dalla punta di una freccia), che si dice raggiunge un vertice in entrata, e una coda, che lo lascia in uscita. Un grafo non orientato D è un'insieme di vertici e archi dove la connessione i - j ha lo stesso significato della connessione j - i.

Un grafo semplice non contiene archi orientati.

Vi sono inoltre varie specie di grafi arricchiti. Si studiano anche grafi con un insieme numerabile di nodi o vertici.

[modifica] Grafo denso, grafo sparso

Un grafo D è definito denso quando il numero di lati è pari a:

$E = ω(V 2)$ dalla quale si ricava $E \geq {1 \over k}\omega(V^2)$

Un grafo D è definito sparso quando il numero di lati è pari a:

$E = O (V)$ dalla quale si ricava $E \,<\, cV$

Queste due definizioni sono utili per comprendere quale tipo di rapprensentazione del grafo implementare (se tramite liste o tramite matrice di adiacenza)

[modifica] Percorsi, cammini e cicli

Un percorso (walk) di lunghezza n in G è dato da una sequenza di vertici v₀,v₁,..., v_n (non necessariamente tutti distinti) e da una sequenza di archi che li collegano (v₀,v₁),(v₁,v₂),...,(v_n-1,v_n). I vertici v₀ e v_n si dicono estremi del percorso.

Un percorso con nodi tutti distinti prende il nome di cammino (path).

Un cammino chiuso (v₀ = v_n) si chiama ciclo (cycle).

[modifica] Connettività

Dato un grafo G = (V, E) due vertici v ∈ V e u ∈ V diconsi connessi se esiste un cammino con estremi v e u. Se tale cammino non esiste, v e u sono detti sconnessi. Per i = 1..k (k classi di equivalenza) sono definibili i sottografi G_i = (V_i, E_i), che prendono il nome di componenti connesse di G, la cui cardinalità spesso si indica con γ(G).

Se γ(G) = 1, G si dice connesso.

Un nodo isolato è un vertice che non è connesso a nessun altro vertice.

Un ponte e uno snodo sono, rispettivamente, un arco ed un vertice che se soppressi sconnettono il grafo.

La connettività di un grafo G = (V, E) è definita come la cardinalità dell'insieme non vuoto S ⊂ V tale che G \ S (G dal quale sono stati eliminati tutti i nodi di S) risulta sconnesso o è un nodo isolato.

Allo stesso modo, l'arcoconnettività viene definita come la cardinalità dell'insieme non vuoto A ⊂ E tale che G \ A (G dal quale sono stati eliminati tutti gli archi di A) risulta sconnesso. I cappi risultano ininfluenti nel computo dell'arcoconnettività, mentre i multiarchi vanno contati per il numero di archi che comprendono.

Siano la connettività di G indicata da κ(G), l'arcoconnettività di G indicata da κ'(G) e il grado minimo di G indicato da δ_min(G).

Il teorema di Whiteny afferma che per ogni grafo G vale la relazione κ(G) ≤ κ'(G) ≤ δ_min(G).

[modifica] Matching e ricoprimenti

Dato un grafo semplice G = (V, E), un insieme M = (S, A) composto da coppie di vertici presi due a due e dagli archi che connettono tali vertici è un matching se ogni vertice di S ha grado 0 o 1.

In particolare, ogni nodo con grado 1 è detto m-saturato ed ogni nodo con grado 0 è detto m-esposto.

Dato un matching M = (S, A) su G = (V, E), un cammino P ⊆ E è m-alternante se P contiene alternativamente archi di E e archi di A.

Un cammino m-alternante è m-aumentante se il primo e l'ultimo vertice di tale cammino sono m-esposti.

Secondo il teorema di Berge, un matching M di G è massimo se e solo se G non contiene cammini m-aumentanti.

Un ricoprimento di un grafo G = (V, E) è un insieme non vuoto S ⊆ V tale che ogni arco in E è incidente in almeno un vertice di S. Per ogni grafo la massima cardinalità di un ricoprimento è maggiore o uguale alla cardinalità del matching massimo.

Siano ν(G) la cardinalità del matching massimo di G e τ(G) la massima cardinalità dei ricoprimenti di G.

König dimostrò che se G è un grafo bipartito allora ν(G) = τ(G).

Invece più in generale, per qualunque grafo vale ν(G) >= τ(G).

[modifica] Tipi di grafi

[modifica] Implementazioni dei grafi

Ci sono due modi generali per rappresentare un grafo con una struttura di dati utilizzabile da un programma: la lista delle adiacenze e la matrice delle adiacenze. In una lista di adiacenze, una lista mantiene un elenco di nodi, ed ad ogni nodo è collegata una lista di puntatori ai nodi collegati da un arco. In una matrice di adiacenze, una matrice N per N, dove N è il numero dei nodi, mantiene un valore vero in una cella (a,b) se il nodo a è collegato al nodo b. La matrice è simmetrica solo se il grafo non è orientato.

Indicati con V la cardinalità dell'insieme dei vertici del grafo e con E la cardinalità dell'insieme degli archi del grafo, le due rappresentazioni, quella mediante liste e quella mediante matrice delle adiacenze, richiedono rispettivamente Θ(V+E) e Θ(V²) spazio di memoria.

Ognuna delle due rappresentazioni ha alcuni vantaggi: una lista di adiacenze risulta più adatta a rappresentare grafi sparsi o con pochi archi, perciò è facile trovare tutti i nodi adiacenti ad un nodo dato e verificare l'esistenza di connessioni tra nodi; una matrice di adiacenze è invece più indicata per descrivere grafi densi e con molti archi, inoltre rende più facile invertire i grafi e individuarne sottografi.