Glossario di teoria dei grafi

Da Wikipedia, l'enciclopedia libera.
Se riscontri problemi nella visualizzazione dei caratteri, clicca qui.

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.


Indice
0 - 9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ?

A[modifica | modifica sorgente]

Adiacenza[modifica | modifica sorgente]

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

Albero[modifica | modifica sorgente]

Un albero è una foresta connessa. Può essere definito anche come un grafo connesso ed aciclico. Oppure: nella teoria dei grafi un albero è un grafo non orientato nel quale due vertici qualsiasi sono connessi da un solo cammino.

Albero libero[modifica | modifica sorgente]

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

C[modifica | modifica sorgente]

Cappio[modifica | modifica sorgente]

Un arco che ha due estremi coincidenti si dice cappio.

Catena[modifica | modifica sorgente]

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:

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

Una catena (v0, ..., vm, v0) si dice ciclica. Un grafo a-ciclico può contenere catene cicliche, nel qual caso non è singolarmente connesso.

Ciclo[modifica | modifica sorgente]

In un grafo si dice ciclo (o circuito) di lunghezza m una catena (v0, ..., vm-1, v0); si dice ciclo semplice un ciclo (v0, ..., vm-1, v0) per il quale:

\forall i,k=1,...,m-1, (i \ne k \Rightarrow v_i \ne v_k)

cioè un ciclo che non passa due volte dallo stesso nodo.

Cricca (o clique)[modifica | modifica sorgente]

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 | modifica sorgente]

  • 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 | modifica sorgente]

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

\mathrm{Bl}(N)=\{X \in V t.c. (N,X) \in E \lor (X,N) \in E \lor ((N,K) \in E \land (X,K) \in E)\}

Corda[modifica | modifica sorgente]

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[modifica | modifica sorgente]

Eccentricità[modifica | modifica sorgente]

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[modifica | modifica sorgente]

Foresta[modifica | modifica sorgente]

Una foresta è un grafo 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

Figlio, nodo[modifica | modifica sorgente]

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[modifica | modifica sorgente]

Genitore, nodo[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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

Grafo triangolato[modifica | modifica sorgente]

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

Grafo planare[modifica | modifica sorgente]

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

O[modifica | modifica sorgente]

Ordine perfetto[modifica | modifica sorgente]

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[modifica | modifica sorgente]

Percorso[modifica | modifica sorgente]

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:

\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.

R[modifica | modifica sorgente]

Radice, nodo[modifica | modifica sorgente]

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

S[modifica | modifica sorgente]

Sottografo[modifica | modifica sorgente]

A 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[modifica | modifica sorgente]

Tour di un grafo[modifica | modifica sorgente]

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[modifica | modifica sorgente]

  • 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 completa.]

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

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