Топ-100
Indietro

ⓘ Grafo. I grafi sono strutture matematiche discrete che rivestono interesse sia per la matematica che per unampia gamma di campi applicativi. In ambito matematic ..




Grafo
                                     

ⓘ Grafo

I grafi sono strutture matematiche discrete che rivestono interesse sia per la matematica che per unampia gamma di campi applicativi. In ambito matematico il loro studio, la teoria dei grafi, costituisce unimportante parte della combinatoria; i grafi inoltre sono utilizzati in aree come topologia, teoria degli automi, funzioni speciali, geometria dei poliedri, algebra di Lie. I grafi si incontrano in vari capitoli dellinformatica. Essi inoltre sono alla base di modelli di sistemi e processi studiati nellingegneria, nella chimica, nella biologia molecolare, nella ricerca operativa, nella organizzazione aziendale, nella geografia, nella linguistica strutturale, nella storia.

                                     

1. 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 ⊆ V × V {\displaystyle E\subseteq V\times V} segue in particolare che | E | ≤ | V | 2 {\displaystyle |E|\leq |V|^{2}}. Se invece E {\displaystyle E} è un multiinsieme, allora si parla di multigrafo.

Due vertici u, v connessi da un arco e prendono il nome di estremi dellarco; larco e viene anche identificato con la coppia formata dai suoi estremi u, v. Se E {\displaystyle 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 skG 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 dellarco. 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. Lordine di un grafo è | V | {\displaystyle |V|} il numero dei vertici. La dimensione di un grafo è | E | {\displaystyle |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 { u, v }, 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 linsieme dei nodi è vuoto.

                                     

1.1. Definizioni fondamentali 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.

                                     

1.2. Definizioni fondamentali Percorsi, cammini e circuiti cicli

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

Un cammino chiuso v 0 = 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.

                                     

1.3. Definizioni fondamentali Connettività

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 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à dellinsieme 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à dellinsieme 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 dellarcoconnettività, mentre i multiarchi vanno contati per il numero di archi che comprendono.

Siano la connettività di G indicata da κG, larcoconnettività 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.



                                     

1.4. Definizioni fondamentali 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 archi di A.

Un cammino m-alternante è "m-aumentante" se il primo e lultimo 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.

                                     

2. Tipi di grafi

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

3. 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 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à dellinsieme dei vertici del grafo e con E la cardinalità dellinsieme degli archi del grafo, le due rappresentazioni, quella mediante liste e quella mediante matrice delle adiacenze, richiedono rispettivamente ΘV+e ΘV 2 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 lesistenza 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.



                                     

4. 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, ed altre testuali, come DOT, Graph Modelling Language GML, LCF e Trivial Graph Format.

                                     

5. 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 ladozione 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 lapplicabilità del modello alle singole reti. Tale tipo di rete è nato per modellare e spiegare la diversa crescita economica tra Paesi, ovvero la tendenza alla concentrazione delle 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-semiperferia-periferia.

                                     
  • In informatica una base di dati a grafo o database a grafo è una tipologia di database che utilizza nodi e archi per rappresentare e archiviare l informazione
  • grafi, un grafo molecolare o grafo chimico è la rappresentazione della formula di struttura di un composto chimico mediante l utilizzo di un grafo La sua
  • In teoria dei grafi un grafo aleatorio è un grafo generato da un procedimento aleatorio, ovvero è una variabile aleatoria le cui realizzazioni sono dei
  • Il grafo di Turán T n, r è un grafo formato suddividendo un insieme di n vertici in r sottoinsiemi, con dimensioni più uguali possibili, e connettendo
  • Nella teoria dei grafi, un grafo regolare è un grafo in cui ogni vertice ha lo stesso numero di vicini, cioè ogni vertice ha lo stesso grado. Nel caso
  • In informatica, il grafo delle attese anche detto grafo di Holt è un grafo orientato diretto. Introdotto a partire dal 1972, è usato per rappresentare
  • superficie S è un piano si parla di raffigurazione piana del grafo Due raffigurazioni di un grafo sopra una superficie si dicono topologicamente equivalenti
  • Un grafo G è una coppia V, E dove V è un insieme e E V V è un sottoinsieme del prodotto cartesiano di V per se stesso. Gli elementi di V sono detti
  • Nella teoria dei grafi, un grafo ciclo o grafo circolare è un grafo che consiste di un unico ciclo o, in altre parole, di un certo numero di vertici connessi
  • compresi il grafo dei servizi, il grafo di Petersen, il grafo di Heawood, il grafo di Möbius - Kantor, il grafo di Pappus, il grafo di Desargues, il grafo di Nauru