Grafo

Related Topics:
Graford

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.

Definizioni fondamentali

In 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. 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 eliminando tutti i cappi e multiarchi di G.

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.

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

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 è un grafo che non contiene archi orientati.

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

Grafo denso, grafo sparso

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

$E = \omega(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)

Percorsi, cammini e cicli

Un percorso (walk) di lunghezza n di G è una sequenza di vertici alternati (non necessariamente tutti distinti) con estremi v₀ e v_n che descrive un tragitto all'interno di G.

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

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

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 semplicemente 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).

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).

Tipi di grafi

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.

Teoria dei grafi

Gourt Home::Gourt :: Grafo