Grafo

I grafi sono strutture matematiche discrete che rivestono interesse sia per la matematica che per un'ampia gamma di campi applicativi. In ambito matematico il loro studio, la teoria dei grafi, costituisce un'importante parte della combinatoria; i grafi inoltre sono utilizzati in aree come topologia, teoria degli automi, funzioni speciali, geometria dei poliedri, algebre di Lie. I grafi si incontrano in vari capitoli dell'informatica (ad esempio per schematizzare programmi, circuiti, reti di computer, mappe di siti). Essi inoltre sono alla base di modelli di sistemi e processi studiati nell'ingegneria, nella chimica, nella biologia molecolare, nella ricerca operativa, nella organizzazione aziendale, nella geografia (sistemi fluviali, reti stradali, trasporti), nella linguistica strutturale, nella storia (alberi genealogici, filologia dei testi).

Definizioni fondamentali

Un grafo è un insieme di elementi detti nodi o vertici che possono essere collegati fra loro da linee chiamate archi o lati o spigoli. Più formalmente, si dice grafo una coppia ordinata $G=(V,E)$ di insiemi, con $V$ insieme dei nodi ed $E$ insieme degli archi, tali che gli elementi di $E$ siano coppie di elementi di $V$ (da $E\subseteq V\times V$ segue in particolare che $|E|\leq |V|^{2}$ ). Ancora più formalmente, un grafo è una tripla $(V,E,f)$ , dove $V$ è detto insieme dei nodi, $E$ è detto insieme degli archi e $f$ è una funzione che associa ad ogni arco $e$ in $E$ due vertici $u,v$ in $V$ (in tal caso il grafo verrà detto ben specificato). Se invece $E$ è un multiinsieme, allora si parla di multigrafo.

Due vertici $u,v$ connessi da un arco $e$ prendono il nome di estremi dell'arco; l'arco $e$ viene anche identificato con la coppia formata dai suoi estremi $(u,v)$ . Se $E$ è una relazione simmetrica, allora si dice che il grafo è non orientato (o indiretto), altrimenti si dice che è orientato (o diretto).

Un arco che ha due estremi coincidenti si dice cappio. Un grafo non orientato, sprovvisto di cappi si dice grafo semplice. Lo scheletro $\mathrm {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.

I vertici appartenenti a un arco o spigolo sono chiamati estremi, punti estremi o vertici estremi dell'arco. Un vertice può esistere in un grafo e non appartenere a un arco.

Il codice sorgente della pagina principale di Wikipedia, visualizzato sotto forma di albero, un caso particolare di grafo

Gli insiemi $V$ ed $E$ sono di solito assunti come finiti, e molti dei risultati più noti non sono veri (o sono piuttosto diversi) per i grafi infiniti perché molti degli argomenti vengono meno nel caso infinito. L'ordine di un grafo è $|V|$ (il numero dei vertici). La dimensione di un grafo è $|E|$ . Il numero di archi incidenti in un vertice $v\in V$ (cioè il numero di archi che si connettono ad esso) prende il nome di grado del vertice $v$ , dove un arco che si connette al vertice ad entrambe le estremità (un cappio) è contato due volte.

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

Per un arco $\{u,v\}$ , i teorici dei grafi usano solitamente la notazione più sintetica $uv$ .

Un grafo $G=(V,\emptyset )$ privo di archi è detto grafo nullo. Un caso estremo di grafo nullo è quello del grafo $G=(\varnothing ,\varnothing )$ , per il quale anche l'insieme dei nodi è vuoto.^[1]

Grafo completo, densità di un grafo

Un grafo è definito completo se due qualsiasi dei suoi vertici sono adiacenti (esiste un arco che li connette). La massima cardinalità di un sottografo completo del grafo si chiama densità del grafo.

Percorsi, cammini, circuiti e cicli

Un "percorso" 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 i lati a due a due distinti tra loro prende il nome di cammino.

Un cammino chiuso (v₀ = v_n) senza archi ripetuti viene detto circuito.

Un cammino chiuso (v₀ = v_n) senza archi né nodi ripetuti viene detto ciclo.

Il percorso da seguire per inviare pacchetti da un nodo ad un altro è un percorso minimo.

Connettività

Esempi di grafo connesso (a sinistra) e non connesso (a destra).

Dato un grafo G = (V, E) due vertici v, u ∈ V si dicono "connessi" se esiste un cammino con estremi v e u. Se tale cammino non esiste, v e u sono detti "sconnessi". La relazione di connessione tra vertici è una relazione di equivalenza.

Per i = 1, ..., k (k classi di equivalenza) sono definibili i sottografi G_i = (V_i, E_i) come i sottografi massimali che contengono tutti gli elementi connessi tra loro, 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 nodo isolato ha grado 0.

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

Accoppiamento 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 accoppiamento (o abbinamento o 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 abbinamento 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

Realizzazione 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, e a ogni nodo è collegata una lista di puntatori ai nodi collegati da un arco. In una matrice di adiacenze, una matrice $N\times 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 a 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.

Sintassi per la rappresentazione dei grafi

Esistono svariate sintassi per la rappresentazione di grafi, alcune basate sul linguaggio XML, come DGML, DotML, GEXF, GraphML, GXL e XGMML, e altre testuali, come DOT, Graph Modelling Language (GML), LCF e Trivial Graph Format.

Applicazioni

La teoria dei grafi trova numerose applicazioni per la modellazione di reti di telecomunicazioni, reti neurali, in biologia, nelle scienze economiche e sociali.

Dalle scienze economiche e sociali negli anni '80 ha preso a diffondersi fra i ricercatori e gli accademici l'adozione di un particolare tipo di rete (core-periphery network), formato da un blocco centrale, più "denso" di collegamenti fra i nodi, e da un blocco periferico insieme di nodi con collegamenti sparsi. Contestualmente furono proposti diversi metodi di partizione (e vincoli sulle connessioni), e di misure della centralità dei nodi per testare l'applicabilità del modello alle singole reti^[2].

Tale tipo di rete è nato per modellizzare e spiegare la diversa crescita economica tra Paesi, ossia la tendenza alla concentrazione della ricchezza economica e finanziaria rilevata in sistemi-Paese a partire dal secondo dopoguerra. Il modello fu poi esteso ad altri campi di ricerca.

Esiste una variante "a tre blocchi" della rete "centro-periferia": centro-semiperiferia-periferia.

Note

^ Alcuni definiscono vuoto il grafo G = (V, ∅), con V ≠ ∅, e nullo il grafo G = (∅, ∅).
^ (EN) Fabio Della Rossa, Fabio Dercole & Carlo Piccardi, Profiling core-periphery network structure by random walkers, su nature.com, 19 marzo 2013. URL consultato il 4 aprile 2018.