Grafo

Da Wikipedia, l'enciclopedia libera.
Se riscontri problemi nella visualizzazione dei caratteri, clicca qui.
bussola Disambiguazione – Se stai cercando la rappresentazione cartesiana di una funzione, vedi Grafico di una funzione.
Grafo (non orientato) con 6 nodi e 5 archi

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[modifica | modifica wikitesto]

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

Due vertici u, v connessi da un arco e prendono nome di "'estremi dell'arco'"; l'arco e viene anche identificato con la coppia formata dai suoi estremi (u, v).

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

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 ∈ 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 {uv}, i teorici dei grafi usano solitamente la notazione più sintetica uv.

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

Grafi orientati e grafi semplici[modifica | modifica wikitesto]

Il codice sorgente della pagina principale di Wikipedia, visualizzato sotto forma di grafo.

Si distinguono due tipi basilari di grafi, i grafi orientati (o grafi diretti) e i grafi non orientati (o grafi indiretti).

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 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 completo, densità di un grafo[modifica | modifica wikitesto]

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 e circuiti (cicli)[modifica | modifica wikitesto]

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) si chiama circuito o ciclo.

Connettività[modifica | modifica wikitesto]

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 | modifica wikitesto]

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 | modifica wikitesto]

Implementazioni dei grafi[modifica | modifica wikitesto]

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 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 Θ(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 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.

Note[modifica | modifica wikitesto]

  1. ^ Alcuni definiscono vuoto il grafo G = (V, ∅), con V ≠ ∅, e nullo il grafo G = (∅, ∅)

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica