Visualizza wikitesto di Grafo

{{nota disambigua|la rappresentazione cartesiana di una funzione|Grafico di una funzione}}
{{nota disambigua|la realizzazione concreta di un [[grafema]] in un sistema di scrittura|Allografo}}
{{nd|il tipo di dato astratto dell'ambito informatico|Grafo (tipo di dato astratto)}}
{{F|informatica|maggio 2023}}
[[File:6v-color-graph.svg|thumb|Grafo non orientato con sei nodi e cinque archi]]

I '''grafi''' sono strutture [[matematica discreta|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]], [[algebra di Lie|algebre di Lie]]. I grafi si incontrano in vari capitoli dell'[[informatica]] (ad esempio per schematizzare programmi, circuiti, [[Rete di computer|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 ==
[[File:Grafo-esempio-1.png|left|thumb|upright=1.6|Un grafo]]
Un grafo è un insieme di elementi detti nodi o [[vertice (teoria dei grafi)|vertici]] che possono essere collegati fra loro da linee chiamate archi o lati o spigoli. Più formalmente, si dice grafo una coppia ordinata <math>G=(V,E)</math> di [[Insieme|insiemi]], con <math>V</math> insieme dei nodi ed <math>E</math> insieme degli archi, tali che gli elementi di <math>E</math> siano coppie di elementi di <math>V</math> (da <math>E \subseteq V \times V</math> segue in particolare che <math>|E| \leq |V|^2</math>). Ancora più formalmente, un grafo è una tripla <math>(V, E, f)</math>, dove <math>V</math> è detto insieme dei nodi, <math>E</math> è detto insieme degli archi e <math>f</math> è una funzione che associa ad ogni arco <math>e</math> in <math>E</math> due vertici <math>u, v</math> in <math>V</math> (in tal caso il grafo verrà detto ''ben specificato''). Se invece <math>E</math> è un [[multiinsieme]], allora si parla di [[multigrafo]].

Due vertici <math>u,v</math> connessi da un arco <math>e</math> prendono il nome di estremi dell'arco; l'arco <math>e</math> viene anche identificato con la coppia formata dai suoi estremi <math>(u,v)</math>. Se <math>E</math> è 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 [[Glossario di teoria dei grafi#Cappio|cappio]]. Un grafo non orientato, sprovvisto di cappi si dice [[grafo semplice]]. Lo [[Scheletro (Grafi)|scheletro]] <math>\mathrm{sk}(G)</math> di <math>G</math> è il grafo che si ottiene da <math>G</math> 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.[[File:It.wp grafo.jpg|thumb|upright=1.4|Il [[codice sorgente]] della [[pagina principale|pagina principale di Wikipedia]], visualizzato sotto forma di [[Albero (grafo)|albero]], un caso particolare di grafo]]

Gli insiemi <math>V</math> ed <math>E</math> 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 [[Grado infinito|caso infinito]]. L{{'}}ordine di un grafo è <math>|V|</math> (il numero dei vertici). La dimensione di un grafo è <math>|E|</math>. Il numero di archi incidenti in un vertice <math>v \in V</math> (cioè il numero di archi che si connettono ad esso) prende il nome di grado del vertice <math>v</math>, 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 <math>G</math> come, rispettivamente, il grado del vertice di <math>G</math> con il maggior numero di archi incidenti e il grado del vertice di <math>G</math> che ha meno archi incidenti. Quando il grado massimo ed il grado minimo coincidono con un numero <math>k</math>, si è in presenza di un grafo <math>k</math>-regolare (o più semplicemente grafo regolare).

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

Un grafo <math>G=(V,\emptyset)</math> privo di archi è detto [[grafo nullo]]. Un caso estremo di grafo nullo è quello del grafo <math>G=(\varnothing, \varnothing)</math>, per il quale anche l'insieme dei nodi è vuoto.<ref>Alcuni definiscono ''vuoto'' il grafo ''G'' = (''V'', ∅), con ''V'' ≠ ∅, e ''nullo'' il grafo ''G'' = (∅, ∅).</ref>

=== 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à di un grafo|densità del grafo]].

=== Percorsi, cammini, circuiti e cicli ===
Un "percorso" di lunghezza ''n'' in ''G'' è dato da una sequenza di vertici ''v<sub>0</sub>,v<sub>1</sub>,..., v<sub>n</sub>'' (non necessariamente tutti distinti) e da una sequenza di archi che li collegano ''(v<sub>0</sub>,v<sub>1</sub>),(v<sub>1</sub>,v<sub>2</sub>),...,(v<sub>n-1</sub>,v<sub>n</sub>)''. I vertici ''v<sub>0</sub>'' e ''v<sub>n</sub>'' 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<sub>0</sub> = v<sub>n</sub>'') senza archi ripetuti viene detto ''circuito''.

Un cammino chiuso (''v<sub>0</sub> = v<sub>n</sub>'') 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à ===
[[File:Connexe et pas connexe.svg|thumb|upright=1.4|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'' [[classe di equivalenza|classi di equivalenza]]) sono definibili i sottografi ''G<sub>i</sub> = (V<sub>i</sub>, E<sub>i</sub>)'' 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 "[[Grafo connesso|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 δ<sub>min</sub>(''G'').

Il "teorema di Whiteny" afferma che per ogni grafo ''G'' vale la relazione κ(''G'') ≤ κ'(''G'') ≤ δ<sub>min</sub>(''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 ==
*[[Grafo arricchito]]
*[[Grafo bipartito]]
*[[Grafo convesso]]
*[[Grafo biconvesso]]
*[[Grafo cubico]]
*[[Grafo duale]]
*[[Grafo regolare]]
*[[Grafo planare]]
*[[Grafo temporale]]
*[[Rete casuale]]
*[[Rete dinamica]]
*[[Rete a invarianza di scala]]
*[[Poligrafo (matematica)|Poligrafo]]
*[[n-grafo]]

== Realizzazione dei grafi ==
Ci sono due modi generali per rappresentare un grafo con una struttura di dati utilizzabile da un [[Programma (informatica)|programma]]: la [[lista di adiacenza|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 <math>N \times N</math>, dove <math>N</math> è il numero dei nodi, mantiene un valore "vero" in una cella <math>(a,b)</math> se il nodo <math>a</math> è collegato al nodo <math>b</math>. 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 [[Lista di adiacenza|liste]] e quella mediante [[matrice delle adiacenze]], richiedono rispettivamente ''Θ(V+E)'' e ''Θ(V<sup>2</sup>)'' 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 [[Graphviz|DOT]], [[Graph Modelling Language]] (GML), LCF e [[Trivial Graph Format]].

== Applicazioni ==
La teoria dei grafi trova numerose applicazioni per la modellazione di [[Rete di telecomunicazioni|reti di telecomunicazioni]], [[rete neurale|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 (matematica)|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 [[Taglio (teoria dei grafi)|partizione]] (e vincoli sulle connessioni), e di misure della centralità dei nodi per testare l'applicabilità del modello alle singole reti<ref>{{cita pubblicazione|url= https://www.nature.com/articles/srep01467|titolo= Profiling core-periphery network structure by random walkers|autore= Fabio Della Rossa, Fabio Dercole & Carlo Piccardi|doi:10.1038/srep01467|data= 19 marzo 2013|accesso= 4 aprile 2018|lingua= en|sito =nature.com}}</ref>.

Tale tipo di rete è nato per [[Modello matematico|modellizzare]] e spiegare la diversa crescita economica tra Paesi, ossia la tendenza alla [[Indice di concentrazione|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==
<references/>

== Voci correlate ==
* [[Glossario di teoria dei grafi]]
* [[Raffigurazione di un grafo]]
* [[Matrice di adiacenza]]
* [[Lista di adiacenza]]
* [[Ricerca in ampiezza]]
* [[Ricerca in profondità]]
* [[Ordinamento topologico]]
* [[Base di dati a grafo]]
* [[Modularità (reti)]]
* [[Ponte (teoria dei grafi)]]
* [[Grafo molecolare]]
* [[Diagramma di Dynkin]]

== Altri progetti ==
{{interprogetto|wikt|preposizione=sul}}

==Collegamenti esterni==
* [https://setticarraro.edu.it/wp-content/uploads/2025/01/Grafi.pdf Appunti di teoria dei grafi dell'università di Catania]{{Collegamenti esterni}}
* {{PlanetMath|graph|graph}}
* {{Cita web|url=http://wpage.unina.it/benerece/ASD/Benerecetti/Modulo-II-2008/02-Grafi-I.pdf|titolo=Definizioni sui grafi}} 
* [https://web.archive.org/web/20130310082528/http://gianlucacosta.info/software/graphsj/ 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.
* {{cita web|http://www.bioemulation.altervista.org/software/graphNview.html|GraphNview :  Software open source per creare,visualizzare ed animare grafi orientati}}
* {{cita web|http://science4fun.org/it/shottini-scienitifici/quanto-e-sicuro-il-tuo-smartphone/|Un ''grafo ''utilizzato per calcolare tutti i possibili pattern del blocco schermo di Android}}
* Video tutorial: [https://www.youtube.com/watch?v=1xT8F0tMbJE come creare un grafo con PostGIS e QGis]

{{Controllo di autorità}}
{{Portale|matematica|informatica}}

[[Categoria:Teoria dei grafi]]