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

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

Due vertici ${\displaystyle u,v}$ connessi da un arco ${\displaystyle e}$ prendono il nome di estremi dell'arco; l'arco ${\displaystyle e}$ viene anche identificato con la coppia formata dai suoi estremi ${\displaystyle (u,v)}$. Se ${\displaystyle E}$ e una relazione simmetrica, allora si dice che il grafo e non orientato (o indiretto), altrimenti si dice che e 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 ${\displaystyle \mathrm {sk} (G)}$ di ${\displaystyle G}$ e il grafo che si ottiene da ${\displaystyle 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 puo esistere in un grafo e non appartenere a un arco.

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

Si considerano il "grado massimo" e il "grado minimo" di ${\displaystyle G}$ come, rispettivamente, il grado del vertice di ${\displaystyle G}$ con il maggior numero di archi incidenti e il grado del vertice di ${\displaystyle G}$ che ha meno archi incidenti. Quando il grado massimo ed il grado minimo coincidono con un numero ${\displaystyle k}$, si e in presenza di un grafo ${\displaystyle k}$-regolare (o piu semplicemente grafo regolare).

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

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

• Grafo a scala
• Grafo arricchito
• Grafo bipartito
• Grafo convesso
• Grafo biconvesso
• Grafo cubico
• Grafo duale
• Grafo regolare
• Grafo planare
• Rete casuale
• Rete dinamica
• Rete a invarianza di scala
• Poligrafo
• n-grafo

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 e collegata una lista di puntatori ai nodi collegati da un arco. In una matrice di adiacenze, una matrice ${\displaystyle N\times N}$, dove ${\displaystyle N}$ e il numero dei nodi, mantiene un valore "vero" in una cella ${\displaystyle (a,b)}$ se il nodo ${\displaystyle a}$ e collegato al nodo ${\displaystyle b}$. La matrice e simmetrica solo se il grafo non e orientato.

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

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

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.

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, piu "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 centralita dei nodi per testare l'applicabilita del modello alle singole reti^[2].

Tale tipo di rete e 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.

• Glossario di teoria dei grafi
• Raffigurazione di un grafo
• Matrice di adiacenza
• Lista di adiacenza
• Ricerca in ampiezza
• Ricerca in profondita
• Ordinamento topologico
• Base di dati a grafo
• Modularita (reti)
• Ponte (teoria dei grafi)
• Grafo molecolare
• Diagramma di Dynkin

• Wikizionario contiene il lemma di dizionario <<grafo>>
• Wikimedia Commons contiene immagini o altri file sul grafo

• Appunti di teoria dei grafi dell'universita di Catania
• grafo, su Treccani.it - Enciclopedie on line, Istituto dell'Enciclopedia Italiana.
• (EN) Eric W. Weisstein, Graph, su MathWorld, Wolfram Research.
• (EN) Grafo, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) graph, in PlanetMath.
• Definizioni sui grafi (PDF), su wpage.unina.it.
• GraphsJ Software didattico open source in Java, con interfaccia grafica intuitiva, che permette di risolvere passo-passo molti problemi sui grafi. Estendibile grazie al suo SDK scritto in Java.
• GraphNview : Software open source per creare,visualizzare ed animare grafi orientati, su bioemulation.altervista.org.
• Un grafo utilizzato per calcolare tutti i possibili pattern del blocco schermo di Android, su science4fun.org.
• Video tutorial: come creare un grafo con PostGIS e QGis