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.
A
Adiacenza
Per un nodo x di un grafo G = (V, E), si chiama adiacenza Adj(x) l'insieme dei nodi connessi.
Albero
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/87/Magnifying_glass_icon_mgx2.svg/18px-Magnifying_glass_icon_mgx2.svg.png)
Un albero è una foresta connessa, ossia un grafo connesso ed aciclico.[1] Può essere definito anche come 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.
Arco
Un arco (o spigolo), assieme al vertice, è uno dei due elementi costitutivi fondamentali di un grafo. In un grafo ciascun arco individua una coppia di vertici .
C
Cappio
Un arco che ha due estremi coincidenti si dice cappio.
Cammino
Sia G = (V, E) un grafo orientato o non orientato: una n-upla di nodi (v0, ..., vm) si dice cammino, o catena di lunghezza m tra v0 e vm se:
Un cammino si dice semplice se ogni arco viene percorso una sola volta, elementare se ogni nodo viene toccato una sola volta. Se un cammino elementare attraversa tutti i nodi del grafo, esso si dice cammino hamiltoniano.[2]
Un cammino (v0, ..., vm, v0) si dice chiuso o ciclico. Un grafo a-ciclico può comunque contenere cammini ciclici, nel qual caso non è singolarmente connesso.
Ciclo
In un grafo si dice ciclo (o circuito) di lunghezza m un cammino (v0, ..., vm-1, v0); si dice ciclo semplice un ciclo che non passa due volte dallo stesso nodo, o formalmente un ciclo (v0, ..., vm-1, v0) per il quale:
Cricca (o clique)
Se G = (V,E) è un grafo non orientato, una cricca (o 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:
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 privo di cicli.[1] Il nome deriva dal fatto che le componenti connesse di una foresta sono alberi.
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) 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 p0, ..., pn tali che (p0, v) ∈ E. Se G è un albero, i nodi genitori sono anche detti predecessori.
Grado di un vertice
Il numero di archi incidenti in un vertice v ∈ V (cioè il numero di archi che si connettono ad esso) prende il nome di grado del vertice v. Un arco che si connette al vertice ad entrambe le estremità (un cappio) è contato due volte.
Grafo completo
Sia G = (V,E) un grafo non orientato; G si dice completo se
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.
M
Maglia
Una maglia è un sottografo connesso in cui tutti i nodi sono di ordine due.
O
Ordine perfetto
Sia G = (V,E) un grafo non orientato con card(V) = n; un ordinamento dei nodi
si dice perfetto se
è un sottoparagrafo completo di G.
P
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:
Ovviamente, se G non è orientato, ogni catena di G è anche un percorso di G e viceversa.
Peso
Un grafo pesato associa un'etichetta (peso) ad ogni suo arco. I pesi sono espressi generalmente tramite numeri reali, ma possono essere ristretti all'insieme dei razionali o degli interi. Alcuni algoritmi necessitano di maggiori restrizioni sui pesi. Ad esempio, l'algoritmo di Dijkstra funziona propriamente solo con pesi positivi. Talvolta il peso fra due vertici non connessi da un arco è indicato con il valore infinito.
Pozzo
In un grafo orientato, un nodo si dice pozzo se ha grado uscente uguale a 0.
Pozzo universale
In un grafo orientato, un nodo si dice pozzo universale se ha grado entrante uguale a n − 1 e grado uscente uguale a 0. Se in un grafo è presente un pozzo universale, questo è unico.
R
Radice, nodo
In un grafo orientato, un nodo che non ha genitori.
S
Sottografo
Il sottografo di un grafo G è un grafo il cui insieme dei vertici è un sottoinsieme di quello di G, e la cui relazione delle adiacenze è un sottoinsieme di quella di G ristretta a questo sottoinsieme. Nel senso inverso, un supergrafo di un grafo G è un grafo di cui G è un sottografo. Noi diciamo che un grafo G contiene un altro grafo H se un qualche sottografo di G è H o è isomorfo ad H.
Un sottografo H è un sottografo ricoprente (spanning subgraph in inglese), o fattore, di un grafo G se ha lo stesso insieme di vertici di G. Diciamo che H ricopre G.
Un sottografo H di un grafo G si dice indotto (o pieno) se, per qualsiasi coppia di vertici x e y di H, xy è uno spigolo di H se e solo se xy è uno spigolo di G. In altre parole, H è un sottografo indotto di G se ha esattamente gli spigoli che appaiono in G sullo stesso insieme di vertici. Se l'insieme dei vertici di H è il sottoinsieme S di V(G), allora H può essere scritto come G[S] e si dice indotto da S.
Un grafo G è minimale rispetto a una certa proprietà P a condizione che G abbia la proprietà P e nessun sottografo proprio di G abbia la proprietà P. In questa definizione, il termine sottografo di solito è inteso significare "sottografo indotto". La nozione di massimalità è definita dualmente: G è massimale rispetto a P a condizione che P(G) e G non abbia alcun supergrafo proprio H tale che P(H).
Un grafo A che non contiene H come sottografo indotto è detto senza H, e più generalmente se è una famiglia di grafi, allora i grafi che non contengono alcun sottografo indotto isomorfo a un membro di sono chiamati senza . Ad esempio i grafi senza triangoli sono i grafi che non hanno un grafo triangolo come sottografo indotto.
Un grafo universale in una classe K di grafi è un grafo semplice in cui ogni elemento in K può essere incorporato come sottografo.
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.
Note
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.]
- (EN) Douglas B. West, Introduction to graph theory, 2001, ISBN 8178088304.
Voci correlate
- Grafo
- Teoria dei grafi
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)