Glossario di teoria dei grafi

Da Wikipedia, l'enciclopedia libera.

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. 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 1 A 1.1 Adiacenza 1.2 Albero 1.3 Albero libero 2 C 2.1 Catena 2.2 Ciclo 2.3 Clique 2.4 Connessione 2.5 Copertura markoviana 2.6 Corda 3 F 3.1 Foresta 3.2 Figlio, nodo 4 G 4.1 Genitore, nodo 4.2 Grafo completo 4.3 Grafo connesso 4.4 Grafo triangolato 4.5 Grafo planare 5 O 5.1 Ordine perfetto 6 P 6.1 Percorso 7 R 7.1 Radice, nodo 8 S 8.1 Sottografo indotto 9 T 9.1 Tour di un grafo 10 Voci correlate 11 Collegamenti esterni 12 Bibliografia

[modifica] A

[modifica] Adiacenza

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

[modifica] Albero

Un albero è una foresta connessa.

Può essere definito anche come un grafo connesso ed aciclico.

[modifica] Albero libero

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

[modifica] C

[modifica] 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.

[modifica] 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.

[modifica] 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.

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

[modifica] 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 ) }.

[modifica] 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.

[modifica] F

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

[modifica] 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.

[modifica] G

[modifica] 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.

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

[modifica] Grafo connesso

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

[modifica] Grafo triangolato

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

[modifica] Grafo planare

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

[modifica] O

[modifica] 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.

[modifica] P

[modifica] 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.

[modifica] R

[modifica] Radice, nodo

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

[modifica] S

[modifica] 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 ∈ W ∧ w ∈ W}

è detto sottografo indotto da W.

[modifica] T

[modifica] 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.

[modifica] Voci correlate

• Indici per la matematica
• Elenco degli articoli di teoria dei grafi
• Elenco di articoli di teoria delle reti
• Grafo (matematica)
• Teoria dei grafi

[modifica] Collegamenti esterni

• Graph in MathWorld

[modifica] 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.]