Grafi

Grafi

Un grafo è costituito da una coppia G = <V, E> dove V è un insieme di nodi ed E è un insieme di archi. Ogni arco è associato ad una coppia ordinata di nodi una funzione a 2 componenti

F = (g₁, g₂) : E V x V

Tale che per ogni arco e I E, se  F(e) = (V₁, V₂) allora V₁ = g₁(e) I E è detto nodo di partenza e   V₂ = g₂(e) I E è detto nodo di arrivo

Dimensione: numero di elementi dell'insieme dei nodi

NB: un arco non può comparire più volte nello stesso grafo.

Un sottografo di G avente lo stesso insieme V, si dice sottografo di spamming di G.

Grado di un nodo: numero di archi che incidono su di esso.

La somma dei gradi di un grafo di m archi è pari a 2m.

Grafo completo:grafo elementare nel quale la coppia di nodi è collegata da un arco ! grafo completo di dimensione n.

Numero di archi di un grafo completo di n nodi: n (n - 1)/2

Grafo omesso: un grafo si dice omesso se presi 2 nodi qualunque vi è un percorso che li collega.

Componente omesso: sottografo con il massimo numero di omessi possibili.

Ne consegue che ogni grafo è l'unione di un insieme di componenti omessi.

Percorso chiuso: è un percorso in cui il primo e l'ultimo nodo sono uguali. Un percorso chiuso è detto loop (anello)

Ciclo: cammino chiuso <e₁, e₂, ., e_n> in cui i nodi <V₁, V₂, ., V_n> sono distinti (tranne il primo o l'ultimo) lunghezza almeno pari a 3.

Grafo ciclico: grafo che contiene cicli.

Cammino ciclico: cammino che contiene cicli. Se G contiene un percorso che ammette 2 nodi a e b allora G contiene un cammino ciclico che omette gli stessi 2 nodi.

Sottografo: un gruppo H = <V_H, E_H> è detto sottografo di un grafo G = <V_G, E_G> se e solo se H = V_H V_G e se E_H E_G

Grafi isomorfi: se esiste una funzione f che assegna ad ogni nodo x di U un nodo y = f(x) di U', soddisfando le 3 condizioni:

1. f è una relazione 1 a 1;
2. ogni y di U' corrisponde a un x di U;
3. f mantiene la struttura degli archi;

Verifica dell'isomorfismo x, i profili devono avere:

1. lo stesso numero di nodi;
2. lo stesso numero di archi;
3. lo stesso numero di componenti omessi;
4. lo stesso numero di nodi con lo stesso grado;
5. lo stesso numero di cicli della stessa lunghezza;

PS: l'isomorfismo è una relazione d'equivalenza (vale la proprietà riflessiva, simmetrica e transitiva)