Se riscontri problemi nella visualizzazione dei caratteri, clicca qui

Glossario di teoria dei grafi

Da Wikipedia, l'enciclopedia libera.

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 ?

A[modifica | modifica wikitesto]

Adiacenza[modifica | modifica wikitesto]

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

Albero[modifica | modifica wikitesto]

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

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

C[modifica | modifica wikitesto]

Cappio[modifica | modifica wikitesto]

Un arco che ha due estremi coincidenti si dice cappio.

Catena[modifica | modifica wikitesto]

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:

(\forall i=1,...,m)((v_{i-1},v_i)\in E) \lor ((v_i,v_{i-1})\in E)

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

Ciclo[modifica | modifica wikitesto]

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:

\forall i,k=1,...,m-1, (i \ne k \Rightarrow v_i \ne v_k)

Cricca (o clique)[modifica | modifica wikitesto]

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.

Connessione[modifica | modifica wikitesto]

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

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

\mathrm{Bl}(N)=\{X \in V t.c. (N,X) \in E \lor (X,N) \in E \lor ((N,K) \in E \land (X,K) \in E)\}

Corda[modifica | modifica wikitesto]

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.

E[modifica | modifica wikitesto]

Eccentricità[modifica | modifica wikitesto]

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.

F[modifica | modifica wikitesto]

Foresta[modifica | modifica wikitesto]

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

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.

G[modifica | modifica wikitesto]

Genitore, nodo[modifica | modifica wikitesto]

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

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

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

\forall x \in V, \forall y \in V, y \in Adj(x)

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

Grafo connesso[modifica | modifica wikitesto]

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

Grafo triangolato[modifica | modifica wikitesto]

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

Grafo planare[modifica | modifica wikitesto]

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

O[modifica | modifica wikitesto]

Ordine perfetto[modifica | modifica wikitesto]

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

\alpha=[V_1,...,V_n]

si dice perfetto se

\forall i, Adj(v_i) \cap \{v_1,...,v_{i-1}\}

è un sottoparagrafo completo di G.

P[modifica | modifica wikitesto]

Percorso[modifica | modifica wikitesto]

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:

(\forall i=1,...,m) (v_{i-1},v_i)\in E

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

Peso[modifica | modifica wikitesto]

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.

Pozzo[modifica | modifica wikitesto]

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

Pozzo universale[modifica | modifica wikitesto]

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.

R[modifica | modifica wikitesto]

Radice, nodo[modifica | modifica wikitesto]

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

S[modifica | modifica wikitesto]

Sottografo[modifica | modifica wikitesto]

A 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 \mathcal{F} è una famiglia di grafi, allora i grafi che non contengono alcun sottografo indotto isomorfo a un membro di \mathcal{F} sono chiamati senza \mathcal{F}. 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.

T[modifica | modifica wikitesto]

Tour di un grafo[modifica | modifica wikitesto]

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.

Bibliografia[modifica | modifica wikitesto]

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

Collegamenti esterni[modifica | modifica wikitesto]

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