Гомоморфизм графов
Граф 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 VG to VH 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'.