Homomorfismo gráfico

Un grafo G es una colección de un conjunto de vértices y un conjunto de aristas que conecta esos vértices. Consta de dos conjuntos:

• Conjunto de Vértices: V = {v1, v2, …, vn}
• Conjunto de aristas: E = {e1, e2, …, en}

El gráfico G se denota como G = (V, E).

Homomorfismo de Grafos: Un grafo El homomorfismo es un mapeo entre dos gráficos que respeta su estructura, es decir, mapea los vértices adyacentes de un gráfico con los vértices adyacentes del otro. Un homomorfismo del gráfico G al gráfico H es un mapa de V _G a V _H que lleva aristas a aristas.

Definición: Un homomorfismo de gráfico F de un gráfico G = (V, E) a un gráfico G’ = (V’, E’) se escribe como:

f : G –> G’
Es una aplicación f: V –> V’ del conjunto de vértices de G al conjunto de vértices de G’ tal que {u, v} ∈ E ⇒ {f(u), f(v ) ∈ E’

La definición anterior se extiende a los grafos dirigidos. Entonces, para un homomorfismo f: G –> G’ es; {f(u), f(v)} es un arco de G’ sólo si (u, v) es un arco de G . Si existe un homomorfismo; f: G –> G’ , entonces se escribe como G–>G’ Se dice que G es homomórfico a G’ .

Isomorfismo:  Si el homomorfismo f: G –> G’ es una biyección (uno a uno y sobre aplicación) cuya inversa también es un homomorfismo de grafo, entonces f es un isomorfismo de grafo .

Ejemplo 1: A continuación se muestran los 2 gráficos G = (V, E) con V = {a, b, c, d, e} y E = {(a, b), (b, c), (c, d) , (d, e), (e, a)} y G’ = (V’, E’) con V’ = {x, y, z} y E’ = {(x, y), (y, z ), (z, x)}.

Existe una aplicación f: G –> G’ tal que {u, v} ∈ E ⇒ {f(u), f(v)} ∈ E’.

Solución :

Digamos que f(a) = x, f(b) = y, f(c) = z, f(d) = x y f(e) = z.

• Si (a, b) es una arista en G, entonces (f(a), f(b)) debe ser una arista en E’.

f(a) = x and f(b) = y  ⇒  (f(a), f(b)) = (x, y) ∈ E'

• Si (b, c) es una arista en G, entonces (f(b), f(c)) debe ser una arista en E’.

f(b) = y and f(c) = z  ⇒  (f(b), f(c)) = (y, z) ∈ E'

• Si (c, d) es una arista en G, entonces (f(c), f(d)) debe ser una arista en E’.

f(c) = z and f(d) = x  ⇒  (f(c), f(d)) = (z, x) ∈ E'

• Si (d, e) es una arista en G, entonces (f(d), f(e)) debe ser una arista en E’

f(d) = x and f(e) = z  ⇒  (f(d), f(e)) = (x, z) ∈ E'

• Si (e, a) es una arista en G, entonces (f(e), f(a)) debe ser una arista en E’

f(e) = z and f(a) = x  ⇒  (f(c), f(d)) = (z, x) ∈ E'

Por lo tanto, se puede ver que ∀{u, v} ∈ E ⇒ ∃{f(u), f(v)} ∈ E’. Entonces f es un homomorfismo.

Ejemplo 2: A continuación se muestran los 2 gráficos G = (V, E) con V = {a, b, c, d, e, h} y E = {(a, b), (b, c), (c, d), (d, e), (e, h), (f, a) } y G’ = (V’, E’) con V’ = {1, 2, 3, 4} y 
E’ = { (1, 2), (2, 3), (3, 4), (4, 1), (4, 2)}.

Existe una función : G–> G’ tal que {u, v} ∈ E ⇒ {f(u), f(v)} ∈ E’.

Solución :

Digamos que f(a) = 1, f(b) = 4, f(c) = 2, f(d) = 4, f(e) = 2 y f(h) = 4.

• Si (a, b) es una arista en G, entonces (f(a), f(b)) debe ser una arista en E’.

f(a) = 1 and f(b) = 4  ⇒  (f(a), f(b)) = (1, 4) ∈ E'

• Si (b, c) es una arista en G, entonces (f(b), f(c)) debe ser una arista en E’.

f(b) = 4 and f(c) = 2  ⇒  (f(b), f(c)) = (4, 2) ∈ E'

• Si (c, d) es una arista en G, entonces (f(c), f(d)) debe ser una arista en E’.

f(c) = 2 and f(d) = 4  ⇒  (f(c), f(d)) = (2, 4) ∈ E'. 
Note- (2, 4) is the same as (4, 2).

• Si (d, e) es una arista en G, entonces (f(d), f(e)) debe ser una arista en E’.

f(d) = 4 and f(e) = 2  ⇒  (f(d), f(e)) = (4, 2) ∈ E'

• Si (e, h) es una arista en G, entonces (f(e), f(h)) debe ser una arista en E’.

f(e) = 2 and f(a) = 4 ⇒  (f(c), f(d)) = (2, 4) ∈ E'

• Si (h, a) es una arista en G, entonces (f(h), f(a)) debe ser una arista en E’.

f(h) = 4 and f(a) = 1 ⇒  (f(c), f(d)) = (4, 1) ∈ E'

Por lo tanto, se puede ver que ∀{u, v} ∈ E ⇒ ∃{f(u), f(v)} ∈ E’. Entonces f es un homomorfismo.

Un homomorfismo de un gráfico G a un gráfico H es un mapa de V _G a V _H que mapea:

• Bordes a Bordes.
• No bordes a vértice, borde o no borde.

Ejemplo 3: A continuación se muestran los 2 gráficos G = (V, E) con V = {a, b, c, d, e} y E = {(a, b), (b, c), (d, e) , (e, h)} y G’ = (V’, E’) con V’ = {1, 2} y E’ = {(1, 2)}.

Solución :

Digamos que f(a) = 1, f(b) = 2, f(c) = 1, f(d) = 2, f(e) = 1

• Si (a, b) es una arista en G, entonces (f(a), f(b)) debe ser una arista en E’.

f(a) = 1 and f(b) = 2 ⇒  (f(a), f(b)) = (1, 2) ∈ E'

• Si (b, c) es una arista en G, entonces (f(b), f(c)) debe ser una arista en E’.

f(b) = 2 and f(c) = 1  ⇒  (f(b), f(c)) = (2, 1) ∈ E'

• Si (d, e) es una arista en G, entonces (f(d), f(e)) debe ser una arista en E’.

f(d) = 2 and f(e) = 1  ⇒  (f(d), f(e)) = (2, 1) ∈ E'

Aquí se puede ver que (b, e) no es una arista en G, pero (fb), f(e) ) = (2, 1) es una arista en el grafo G’.