Isomorfismo

Una funzione $ϕ : V_{1} \to V_{2}$ è un isomorfismo di $G_{1} = (V_{1}, E_{1})$ e $G_{2} = (V_{2}, E_{2})$ se:

$ϕ$ è biunivoca
$(u, v) \in E_{1}$ sse $(ϕ (u), ϕ (v)) \in E_{2}$ , quindi l'adiacenza è preservata

Per esempio, esiste una funzione che può trasformare il primo grafo nel secondo:

Perchè due grafi siano isomorfi, ovvero $G_{1} ≃ G_{2}$ , è necessario che: $∣ V_{1} ∣ = ∣ V_{2} ∣ \land ∣ E_{1} ∣ = ∣ E_{2} ∣ \land deg-seq (G_{1}) = deg-seq (G_{2}) \land NCC (G_{1}) = NCC (G_{2})$ dove $deg-seq (G)$ sono gli $n$ gradi dei nodi di $G$ in ordine crescente.

Per esempio, dati $G_{1}$ e $G_{2}$ come:

si ha che la funzione $ϕ (u) = ⎩ ⎨ ⎧ 24135 se u = 1 se u = 2 se u = 3 se u = 4 se u = 5$ è un valido isomorfismo per $G_{1}$ e $G_{2}$ . Questo è vero perchè $ϕ (u)$ è biunivoca, dato che ogni $v_{2} \in V_{2}$ è assegnato ad un solo $v_{1} \in V_{1}$ e perchè le adiacenze sono preservate:

$(1, 2) \in E_{1}$ e $(ϕ (1), ϕ (2)) = (2, 4) \in E_{2}$
$(2, 3) \in E_{1}$ e $(ϕ (2), ϕ (3)) = (4, 1) \in E_{2}$
...

In questo caso si ha anche che $G_{1} ≃ G_{1}^{C}$ , infatti $G_{2} = G_{1}^{C}$ e $E_{2} = E_{1}^{C}$ .

Computer Science

Isomorfismo