Utente:SilsisScalaZarli/Glossario

Un grafo G è una coppia (V, E) dove V è un insieme e E ⊆ V×V è un sottoinsieme del prodotto cartesiano di V. Gli elementi di V sono detti nodi e quelli di E sono detti archi.

Si distinguono due tipi di grafi:

• i grafi non orientati, dove la relazione E è simmetrica, quindi (a, b) ∈ V → (b, a) ∈ V. 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.

---

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

∀i = 1, ..., m, (v_i-1, v_i) ∈ E ∨ (v_i, v_i-1) ∈ 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

∀i, k = 1, ..., m-1, (i ≠ k → v_i ≠ 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 Se esiste un percorso da V a W, si dice che V è connesso a W.

Copertura markoviana Dato un nodo N di un grafo orientato G = (V, E), la copertura markoviana Bl(N) = {X ∈ V t.c. (N, X) ∈ E ∨ (X, N) ∈ E ∨ ( (N, K) ∈ E ∧ (X, K) ∈ 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.

D

Distanza

La distanza d_G(u, v) tra due vertici u e v (non necessariamente distinti) in un grafo G è la lunghezza del cammino più corto tra loro. La denominazione G di solito è omessa quando non c'è possibilità di equivoco. Quando u e v coincidono, la loro distanza è 0. Quando u e v non sono raggiungibili a vicenda, la loro distanza è definita ∞. L'eccentricità ε_G(v) di un vertice v in un grafo G è la distanza massima da v a qualunque altro vertice. Il diametro diam(G) di un grafo G è la massima eccentricità su tutti i vertici del grafo; e il raggio è la minima eccentricità. Quando ci sono due componenti in G, diam(G) e rad(G) sono definiti infiniti ∞. Banalmente, diam(G) ≤ 2 rad(G). I vertici con eccentricità massima sono chiamati vertici periferici. I vertici di eccentricità minima formano il centro. Un albero ha al più due vertici centrali. L'indice di Wiener di un vertice v in un grafo G denotato con W_G(v) è la somma delle distanze tra v e tutti gli altri. L'indice di Wiener di un grafo G, denotato con W(G), è la somma delle distanze sulle coppie di vertici. Un grafo polinomiale di Wiener è definito da Σ q ^{d (u,v)}, su tutte le coppie non ordinate dei vertici u and v. L'indice di Wiener e il polinomio di Wiener sono di particolare interesse ai chimici matematici.--SilsisScalaZarli 16:13, Mar 30, 2005 (UTC)

F

Foresta Una foresta è un grafo orientato 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) ∈ E. Se G è un albero, i nodi figli sono anche detti successori.

G

Genere

Un incrocio è una coppia di bordi che si intersecano. Un grafo legato su una superficie se i suoi vertici e i suoi bordi possono disporsi senza incrociarsi. Il genere di un grafo è il più basso genere di qualsiasi superficie sulla quale il grafo può essere collocato. Un grafo planare è quello che può essere disegnato in un piano (Euclideo)senza alcun intersezione; e un grafo piano quello che è disegnato con queste caratteristiche. In altre parole, un grafo planare è un grafo di genere 0.

Il grafico di esempio descritto alla destra è un grafico semplice con l'insieme di vertici V = {1, 2, 3, 4, 5, 6} e con il bordo l'insieme E = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6}}. Il grafo dell'esempio è planare; il grafo completo su n vertici, per n>4, non è planare. Un albero, anche, è necessariamente un grafo planare.--SilsisScalaZarli 14:23, Apr 2, 2005 (UTC)

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

∀x ∈ V, ∀y ∈ V, y ∈ Adj(x).

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

Grafo Connesso Un grafo G si dice connesso se:

∀ V,W ∈ E ∃ V è connesso a W.

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

O

Ordine perfetto Sia G = (V, E) un grafo non orientato con card(V) = n; un ordinamento dei nodi α = [v₁, ..., v_n] si dice perfetto se

∀i , Adj(v_i) ∩ {v₁, ..., v_i-1}

è un sottografo 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:

∀i = 1, ..., m, (v_i-1, v_i) ∈ 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 ⊆ V; il grafo G_W determinato da

E_W = {(v, w) t.c. (v, w) ∈ E ∧ v ∈ E ∧ w ∈ E E}

è detto sottografo indotto da W.

Voci correlate

• Grafo (matematica)
• Teoria dei grafi

Collegamenti esterni

• Graph in MathWorld

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