Grafo

rappresentazione di un insieme di oggetti in cui alcune coppie di oggetti sono collegate
Disambiguazione – Se stai cercando la rappresentazione cartesiana di una funzione, vedi Grafico di una funzione.
Disambiguazione – Se stai cercando la realizzazione concreta di un grafema in un sistema di scrittura, vedi Allografo.
Disambiguazione – Se stai cercando il tipo di dato astratto dell'ambito informatico, vedi Grafo (tipo di dato astratto).

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

Grafo non orientato con sei nodi e cinque archi

Definizioni fondamentali

modifica
 
Un grafo

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   di insiemi, con   insieme dei nodi ed   insieme degli archi, tali che gli elementi di   siano coppie di elementi di   (da   segue in particolare che  ). Ancora più formalmente, un grafo è una tripla  , dove   è detto insieme dei nodi,   è detto insieme degli archi e   è una funzione che associa ad ogni arco   in   due vertici   in   (in tal caso il grafo verrà detto ben specificato). Se invece   è un multiinsieme, allora si parla di multigrafo.

Due vertici   connessi da un arco   prendono il nome di estremi dell'arco; l'arco   viene anche identificato con la coppia formata dai suoi estremi  . Se   è 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   di   è il grafo che si ottiene da   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   ed   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 è   (il numero dei vertici). La dimensione di un grafo è  . Il numero di archi incidenti in un vertice   (cioè il numero di archi che si connettono ad esso) prende il nome di grado del vertice  , 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   come, rispettivamente, il grado del vertice di   con il maggior numero di archi incidenti e il grado del vertice di   che ha meno archi incidenti. Quando il grado massimo ed il grado minimo coincidono con un numero  , si è in presenza di un grafo  -regolare (o più semplicemente grafo regolare).

Per un arco  , i teorici dei grafi usano solitamente la notazione più sintetica  .

Un grafo   privo di archi è detto grafo nullo. Un caso estremo di grafo nullo è quello del grafo  , per il quale anche l'insieme dei nodi è vuoto.[1]

Grafo completo, densità di un grafo

modifica

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

modifica

Un "percorso" di lunghezza n in G è dato da una sequenza di vertici v0,v1,..., vn (non necessariamente tutti distinti) e da una sequenza di archi che li collegano (v0,v1),(v1,v2),...,(vn-1,vn). I vertici v0 e vn 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 (v0 = vn) senza archi ripetuti viene detto circuito.

Un cammino chiuso (v0 = vn) 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à

modifica
 
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 Gi = (Vi, Ei) 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 SV 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 AE 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

modifica

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 PE è "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 SV 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

modifica

Realizzazione dei grafi

modifica

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  , dove   è il numero dei nodi, mantiene un valore "vero" in una cella   se il nodo   è collegato al nodo  . 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 Θ(V2) 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

modifica

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

modifica

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.

  1. ^ Alcuni definiscono vuoto il grafo G = (V, ∅), con V ≠ ∅, e nullo il grafo G = (∅, ∅).
  2. ^ (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.

Voci correlate

modifica

Altri progetti

modifica

Collegamenti esterni

modifica
Controllo di autoritàThesaurus BNCF 6138
  NODES
Note 2
os 16
visual 2