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. 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.
| Table of contents |
|
|
∀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.
∀i, k = 1, ..., m-1, (i ≠ k → vi ≠ vk)
cioè un ciclo che non passa due volte dallo stesso nodo.
∀x ∈ V, ∀y ∈ V, y ∈ Adj(x).
∀i , Adj(vi) ∩ {v1, ..., vi-1}
è un sottografo completo di G.Terminologia
Adiacenza
Per un nodo x di un grafo G = (V, E), si chiama adiacenza Adj(x) l'insieme dei nodi connessi.Albero
Un albero è 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. Ovviamente, in un grafo ad albero, le sequenze di archi si dicono anche rami.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: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 qualeClique
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.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.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.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.Grafo completo
Sia G = (V, E) un grafo non orientato; G si dice completo seGrafo triangolato
Un grafo non orientato si dice triangolato se ogni ciclo di lunghezza maggiore di 4 possiede una corda.Radice, nodo
In un grafo orientato, un nodo che non ha genitori.Ordine perfetto
Sia G = (V, E) un grafo non orientato con card(V) = n; un ordinamento dei nodi
α = [v1, ..., vn] si dice perfetto se
