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

Un albero è una foresta connessa, ossia un grafo connesso ed aciclico. 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 $G=\langle V,E\rangle$ ciascun arco $e\in E$ individua una coppia di vertici $(v,u)\in V^{2}$.

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 (v₀, ..., v_m) si dice cammino, o catena di lunghezza m tra v₀ e v_m se:

$\forall i=1,...,m\quad (v_{i-1},v_{i})\in E\lor (v_{i},v_{i-1})\in E$

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.

Un cammino (v₀, ..., v_m, v₀) 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 (v₀, ..., v_m-1, v₀); si dice ciclo semplice un ciclo che non passa due volte dallo stesso nodo, o formalmente un ciclo (v₀, ..., v_m-1, v₀) per il quale:

$\forall i,k=1,...,m-1,(i\neq k\Rightarrow v_{i}\neq v_{k})$

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:

$\mathrm {Bl} (N)=\{X\in Vt.c.(N,X)\in E\lor (X,N)\in E\lor ((N,K)\in E\land (X,K)\in 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.

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. 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 p₀, ..., p_n tali che (v, p_i) 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 p₀, ..., p_n tali che (p₀, 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

$\forall x\in V,\forall y\in V,y\in Adj(x)$

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

$\alpha =[V_{1},...,V_{n}]$

si dice perfetto se

$\forall i,Adj(v_{i})\cap \{v_{1},...,v_{i-1}\}$

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

$(\forall i=1,...,m)(v_{i-1},v_{i})\in E$

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 ${\mathcal {F}}$ è una famiglia di grafi, allora i grafi che non contengono alcun sottografo indotto isomorfo a un membro di ${\mathcal {F}}$ sono chiamati senza ${\mathcal {F}}$. 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.

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