Glossario di teoria dei grafi

lista di un progetto Wikimedia

Un grafo G è una coppia (V, E) dove V è un insieme e EV × 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.

Adiacenza

modifica

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

  Lo stesso argomento in dettaglio: Albero (grafo).

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

modifica

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

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  .

Un arco che ha due estremi coincidenti si dice cappio.

Cammino

modifica

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.

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)

modifica

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

modifica
  • 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,wV.
  • Un grafo orientato si dice fortemente connesso se esiste un cammino da v a w per ogni coppia v,wV

Copertura markoviana

modifica

Dato un nodo N di un grafo orientato G = (V,E), la copertura markoviana Bl(N) è definita come:

 

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.

Eccentricità

modifica

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.

Foresta

modifica

Una foresta è un grafo privo di cicli.[1] Il nome deriva dal fatto che le componenti connesse di una foresta sono alberi.

Figlio, nodo

modifica

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.

Genitore, nodo

modifica

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

modifica

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

modifica

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

modifica

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

Grafo triangolato

modifica

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

Grafo planare

modifica

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

Una maglia è un sottografo connesso in cui tutti i nodi sono di ordine due.

Ordine perfetto

modifica

Sia G = (V,E) un grafo non orientato con card(V) = n; un ordinamento dei nodi

 

si dice perfetto se

 

è un sottografo completo di G.

Percorso

modifica

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.

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.

In un grafo orientato, un nodo si dice pozzo se ha grado uscente uguale a 0.

Pozzo universale

modifica

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.

Radice, nodo

modifica

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

Sottografo

modifica

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.

Tour di un grafo

modifica

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.

  1. ^ a b West, p.68.
  2. ^ Cammino, in Enciclopedia della Matematica, Roma, Istituto dell'Enciclopedia Italiana, 2013. URL consultato il 4 giugno 2022.

Bibliografia

modifica

Voci correlate

modifica
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica