Гомоморфизм графов

Граф G — это совокупность множества вершин и множества ребер, соединяющих эти вершины. Он состоит из двух наборов:

• Набор вершин: V = {v1, v2, …, vn}
• Набор ребер: E = {e1, e2, …, en}

Граф G обозначается как G = (V, E).

Гомоморфизм графов: Гомоморфизм графов — это отображение между двумя графами, которое соблюдает их структуру, т. е. отображает соседние вершины одного графа в соседние вершины другого. Гомоморфизмом графа G в граф H называется отображение из V _G в V _H который переводит края в края.

Определение: Гомоморфизм графа F из графа G = (V, E) в граф G' = (V', E') записывается как:

f : G –> G’
It is a mapping f: V –> V’ from the vertex set of G to the vertex set of G’ such that {u, v} ∈ E ⇒ {f(u), f(v) ∈ E’

Приведенное выше определение распространяется на ориентированные графы. Тогда для гомоморфизма f: G -> G' есть; {f(u), f(v)} является дугой G' только тогда, когда (u, v) является дугой G . Если существует гомоморфизм; f: G -> G' , то это записывается как G -> G' G называется гомоморфным G' .

Изоморфизм: Если гомоморфизм f: G -> G 'является биекцией (однозначной и на отображение), обратная которой также является гомоморфизмом графа, то f является изоморфизмом графа.

Пример 1: Ниже приведены 2 графика G = (V, E) с V = {a, b, c, d, e} и E = {(a, b), (b, c), (c, d) , (d, e), (e, a)} и G' = (V', E') с V' = {x, y, z} и E' = {(x, y), (y, z ), (z, x)}.

Существует отображение f: G -> G' такое, что {u, v} ∈ E ⇒ {f(u), f(v)} ∈ E'.

Решение :

Предположим, что f(a) = x, f(b) = y, f(c) = z, f(d) = x и f(e) = z.

• Если (a, b) — ребро в G, то (f(a), f(b)) должно быть ребром в E'.

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

• Если (b, c) — ребро в G, то (f(b), f(c)) должно быть ребром в E'.

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

• Если (c, d) — ребро в G, то (f(c), f(d)) должно быть ребром в E'.

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

• Если (d, e) — ребро в G, то (f(d), f(e)) должно быть ребром в E'

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

• Если (e, a) — ребро в G, то (f(e), f(a)) должно быть ребром в E'

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

Отсюда видно, что ∀{u, v} ∈ E ⇒ ∃{f(u), f(v)} ∈ E'. Итак, f — гомоморфизм.

Пример 2: Ниже приведены 2 графика G = (V, E) с V = {a, b, c, d, e, h} и E = {(a, b), (b, c), (c, г), (г, д), (д, з), (е, а)} и G' = (V', E') с V' = {1, 2, 3, 4} и
Е' = {(1, 2), (2, 3), (3, 4), (4, 1), (4, 2)}.

Существует отображение : G -> G' такое, что {u, v} ∈ E ⇒ {f(u), f(v)} ∈ E'.

Решение :

Предположим, что f(a) = 1, f(b) = 4, f(c) = 2, f(d) = 4, f(e) = 2 и f(h) = 4.

• Если (a, b) — ребро в G, то (f(a), f(b)) должно быть ребром в E'.

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

• Если (b, c) — ребро в G, то (f(b), f(c)) должно быть ребром в E'.

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

• Если (c, d) — ребро в G, то (f(c), f(d)) должно быть ребром в E'.

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

• Если (d, e) — ребро в G, то (f(d), f(e)) должно быть ребром в E'.

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

• Если (e, h) — ребро в G, то (f(e), f(h)) должно быть ребром в E'.

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

• Если (h, a) — ребро в G, то (f(h), f(a)) должно быть ребром в E'.

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

Отсюда видно, что ∀{u, v} ∈ E ⇒ ∃{f(u), f(v)} ∈ E'. Итак, f — гомоморфизм.

A homomorphism from a graph G to a graph H is a map from V_G to V_H which maps:

• Edges to Edges.
• Non-Edges to vertex, edge or non-edge.

Пример 3: Ниже приведены 2 графика G = (V, E) с V = {a, b, c, d, e} и E = {(a, b), (b, c), (d, e) , (e, h)} и G' = (V', E') с V' = {1, 2} и E' = {(1, 2)}.

Решение :

Предположим, что f(a) = 1, f(b) = 2, f(c) = 1, f(d) = 2, f(e) = 1

• Если (a, b) — ребро в G, то (f(a), f(b)) должно быть ребром в E'.

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

• Если (b, c) — ребро в G, то (f(b), f(c)) должно быть ребром в E'.

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

• Если (d, e) — ребро в G, то (f(d), f(e)) должно быть ребром в E'.

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

Здесь видно, что (b, e) не является ребром в G, но (fb), f(e)) = (2, 1) является ребром в графе G'.