Glossario di teoria dei grafi

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

Adiacenza

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

Albero

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

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

C

Catena

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

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

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

Ciclo

In un grafo si dice ciclo di lunghezza m una catena (v₀, ..., v_m-1, v₀); si dice ciclo semplice un ciclo (v₀, ..., v_m-1, v₀) per il quale:

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

cioè un ciclo che non passa due volte dallo stesso nodo.

Clique

Se G = (V,E) è un grafo non orientato, una 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

• 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,w ∈ V.
• Un grafo orientato si dice fortemente connesso se esiste un cammino da v a w per ogni coppia v,w ∈ V

Copertura markoviana

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

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

Eccentricità

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

Foresta

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

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

G

Genitore, nodo

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

Grafo completo

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

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

Grafo triangolato

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

Grafo planare

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

O

Ordine perfetto

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

Percorso

Sia G = (V, E) un grafo orientato o non orientato: una n-upla di nodi (v₀, ..., v_m) si dice percorso di lunghezza m tra v₀ e v_m 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.

R

Radice, nodo

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

S

Sottografo indotto

Sia G = (V, E) un grafo; sia W un sottoinsieme di V. Il grafo G_W determinato da

$E_W=\{(v,w)\vert (v,w)\in E \land v \in W \land w \in W\}$

è detto sottografo indotto da W.

T

Tour di un grafo

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.

Voci correlate

• Indici per la matematica
• Grafo
• Teoria dei grafi

Bibliografia

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

Collegamenti esterni

• (EN) Eric W. Weisstein, Grafo su MathWorld.

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