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 |
[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 orientato 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 (v0, ..., vm) si dice catena di lunghezza m tra v0 e vm se:
∀i = 1, ..., m, (vi-1, vi) ∈ E ∨ (vi, vi-1) ∈ E
Una catena (v0, ..., vm, v0) 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 (v0, ..., vm-1, v0); si dice ciclo semplice un ciclo (v0, ..., vm-1, v0) per il quale
∀i, k = 1, ..., m-1, (i ≠ k → vi ≠ vk)
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
Se esiste un percorso da V a W, si dice che V è connesso a W.
[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 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
[modifica] Figlio, nodo
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) ∈ 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 p0, ..., pn tali che (p0, 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 α = [v1, ..., vn] si dice perfetto se
∀i , Adj(vi) ∩ {v1, ..., vi-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 (v0, ..., vm) si dice percorso di lunghezza m tra v0 e vm se:
∀i = 1, ..., m, (vi-1, vi) ∈ ===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 GW determinato da
EW = {(v, w) t.c. (v, w) ∈ E ∧ v ∈ E ∧ w ∈ E E}
è detto sottografo indotto da W.
[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
[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.]
Portale Matematica: accedi alle voci di Wikipedia che parlano di matematica
