Apri il menu principale

Glossario di teoria dei grafi

lista di un progetto Wikimedia
(Reindirizzamento da Arco (teoria dei grafi))

Un grafo G è una coppia (V, E) dove V è un insieme e EV × V è un sottoinsieme del prodotto cartesiano di V per se stesso. Gli elementi di V sono detti nodi e quelli di E sono detti archi. I nodi sono spesso chiamati anche "vertici". Gli archi sono detti anche "lati" o "spigoli".

Si distinguono due tipi di grafi:

  • i grafi non orientati, dove la relazione E è simmetrica, quindi (a,b) ∈ E → (b,a) ∈ E. In questo tipo di grafo, gli archi sono sovente denominati spigoli e i nodi vertici.
  • i grafi orientati, dove la relazione E non è simmetrica ed esiste una relazione d'ordine tra i nodi.
Indice
0 - 9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ?

AModifica

AdiacenzaModifica

Per un nodo x di un grafo G = (V, E), si chiama adiacenza Adj(x) l'insieme dei nodi connessi.

AlberoModifica

 Lo stesso argomento in dettaglio: Albero (grafo).

Un albero è una foresta connessa. Può essere definito anche come un grafo connesso ed aciclico. Oppure: nella teoria dei grafi un albero è un grafo non orientato nel quale due vertici qualsiasi sono connessi da un solo cammino.

Albero liberoModifica

Un albero libero è un grafo non orientato connesso ed aciclico.

ArcoModifica

Un arco (o spigolo), assieme al vertice, è uno dei due elementi costitutivi fondamentali di un grafo. In un grafo   ciascun arco   individua una coppia di vertici  .

CModifica

CappioModifica

Un arco che ha due estremi coincidenti si dice cappio.

CatenaModifica

Sia G = (V, E) un grafo orientato o non orientato: una n-upla di nodi (v0, ..., vm) si dice catena di lunghezza m tra v0 e vm se:

 

Una catena (v0, ..., vm, v0) si dice ciclica. Un grafo a-ciclico può contenere catene cicliche, nel qual caso non è singolarmente connesso.

CicloModifica

In un grafo si dice ciclo (o circuito) di lunghezza m una catena (v0, ..., vm-1, v0); si dice ciclo semplice un ciclo che non passa due volte dallo stesso nodo, o formalmente un ciclo (v0, ..., vm-1, v0) per il quale:

 

Cricca (o clique)Modifica

Se G = (V,E) è un grafo non orientato, una cricca (o clique) C di G è un sottografo completo massimale, cioè tale che tutti i nodi di C sono a due a due adiacenti e che nessun altro sottografo completo di G contiene C.

ConnessioneModifica

  • Il vertice v si dice connesso a w se esiste un percorso da v a w.
  • Un grafo si dice connesso se i vertici v e w sono connessi per ogni v,wV.
  • Un grafo orientato si dice fortemente connesso se esiste un cammino da v a w per ogni coppia v,wV

Copertura markovianaModifica

Dato un nodo N di un grafo orientato G = (V,E), la copertura markoviana Bl(N) è definita come:

 

CordaModifica

In un grafo non orientato, un percorso o un ciclo semplice possiede una corda se esiste un arco tra due nodi non consecutivi del ciclo.

EModifica

EccentricitàModifica

Dato un grafo connesso G, si definisce eccentricità e(v) di un punto v il massimo delle d(u,v) per ogni punto u del grafo.

FModifica

ForestaModifica

Una foresta è un grafo nel quale ogni nodo ha al più un genitore. I nodi privi di genitori si dicono radici, quelli privi di figli si dicono foglie. In questo contesto, le sequenze di archi si dicono anche rami.

Una foresta è inerentemente priva di cicli

Figlio, nodoModifica

Sia G = (V, E) un grafo orientato; si dicono figli di un nodo v di G tutti i nodi p0, ..., pn tali che (v, pi) appartiene ad E. Se G è un albero, i nodi figli sono anche detti successori.

GModifica

Genitore, nodoModifica

Sia G = (V, E) un grafo orientato; si dicono genitori di un nodo v di G tutti i nodi p0, ..., pn tali che (p0, v) ∈ E. Se G è un albero, i nodi genitori sono anche detti predecessori.

Grado di un verticeModifica

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. Un arco che si connette al vertice ad entrambe le estremità (un cappio) è contato due volte.

Grafo completoModifica

Sia G = (V,E) un grafo non orientato; G si dice completo se

 

Se N è il numero dei nodi, il numero di archi di un grafo completo è N(N - 1)/2

Grafo connessoModifica

Un grafo si dice connesso se per ogni coppia di nodi (v,w) esiste un percorso che li unisce.

Grafo triangolatoModifica

Un grafo non orientato si dice triangolato se ogni ciclo di lunghezza maggiore o uguale a 4 possiede una corda.

Grafo planareModifica

Un grafo si dice planare se è possibile rappresentarlo nel piano in modo che gli archi si intersechino solo nei vertici.

MModifica

MagliaModifica

Una maglia è un sottografo connesso in cui tutti i nodi sono di ordine due.

OModifica

Ordine perfettoModifica

Sia G = (V,E) un grafo non orientato con card(V) = n; un ordinamento dei nodi

 

si dice perfetto se

 

è un sottoparagrafo completo di G.

PModifica

PercorsoModifica

Sia G = (V, E) un grafo orientato o non orientato: una n-upla di nodi (v0, ..., vm) si dice percorso di lunghezza m tra v0 e vm se:

 

Ovviamente, se G non è orientato, ogni catena di G è anche un percorso di G e viceversa.

PesoModifica

Un grafo pesato associa un'etichetta (peso) ad ogni suo arco. I pesi sono espressi generalmente tramite numeri reali, ma possono essere ristretti all'insieme dei razionali o degli interi. Alcuni algoritmi necessitano di maggiori restrizioni sui pesi. Ad esempio, l'algoritmo di Dijkstra funziona propriamente solo con pesi positivi. Talvolta il peso fra due vertici non connessi da un arco è indicato con il valore infinito.

PozzoModifica

In un grafo orientato, un nodo si dice pozzo se ha grado uscente uguale a 0.

Pozzo universaleModifica

In un grafo orientato, un nodo si dice pozzo universale se ha grado entrante uguale a n − 1 e grado uscente uguale a 0. Se in un grafo è presente un pozzo universale, questo è unico.

RModifica

Radice, nodoModifica

In un grafo orientato, un nodo che non ha genitori.

SModifica

SottografoModifica

Il sottografo di un grafo G è un grafo il cui insieme dei vertici è un sottoinsieme di quello di G, e la cui relazione delle adiacenze è un sottoinsieme di quella di G ristretta a questo sottoinsieme. Nel senso inverso, un supergrafo di un grafo G è un grafo di cui G è un sottografo. Noi diciamo che un grafo G contiene un altro grafo H se un qualche sottografo di G è H o è isomorfo ad H.

Un sottografo H è un sottografo ricoprente (spanning subgraph in inglese), o fattore, di un grafo G se ha lo stesso insieme di vertici di G. Diciamo che H ricopre G.

Un sottografo H di un grafo G si dice indotto (o pieno) se, per qualsiasi coppia di vertici x e y di H, xy è uno spigolo di H se e solo se xy è uno spigolo di G. In altre parole, H è un sottografo indotto di G se ha esattamente gli spigoli che appaiono in G sullo stesso insieme di vertici. Se l'insieme dei vertici di H è il sottoinsieme S di V(G), allora H può essere scritto come G[S] e si dice indotto da S.

Un grafo G è minimale rispetto a una certa proprietà P a condizione che G abbia la proprietà P e nessun sottografo proprio di G abbia la proprietà P. In questa definizione, il termine sottografo di solito è inteso significare "sottografo indotto". La nozione di massimalità è definita dualmente: G è massimale rispetto a P a condizione che P(G) e G non abbia alcun supergrafo proprio H tale che P(H).

Un grafo A che non contiene H come sottografo indotto è detto senza H, e più generalmente se   è una famiglia di grafi, allora i grafi che non contengono alcun sottografo indotto isomorfo a un membro di   sono chiamati senza  . Ad esempio i grafi senza triangoli sono i grafi che non hanno un grafo triangolo come sottografo indotto.

Un grafo universale in una classe K di grafi è un grafo semplice in cui ogni elemento in K può essere incorporato come sottografo.

TModifica

Tour di un grafoModifica

Dato un grafo non orientato G, un tour in G è un ciclo che passa esattamente una volta per ogni nodo di G. Il costo di un tour è la somma dei costi dei suoi archi.

BibliografiaModifica

  • Béla Bollobás (1998): Modern graph theory. New York: Springer-Verlag. ISBN 0-387-98488-7 [Trattazione avanzata; panoramiche storiche alle conclusioni dei capitoli.]
  • West, Douglas B. (2001). Introduction to graph theory (2ed). Upper Saddle River: Prentice Hall. ISBN 0-13-014400-2. [Ricco di illustrazioni, riferimenti ed esercizi: una guida introduttiva ai grafi notevolmente completa.]

Voci correlateModifica

Collegamenti esterniModifica

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