图的同态Graph Homomorphism与同构Graph Isomorphism
- 图的同态Graph Homomorphism
图的同态（Graph Homomorphism）是图论中的一个重要概念，用于描述图之间的一种映射关系。图的同态描述了一个图如何通过映射保留其边的结构。
### 图的同态定义
设有两个图 \( G = (V_G, E_G) \) 和 \( H = (V_H, E_H) \)。一个从图 \( G \) 到图 \( H \) 的映射 \( f: V_G \to V_H \) 被称为图的同态，如果对于 \( G \) 中的每一条边 \( (u, v) \in E_G \)，在 \( H \) 中对应的边 \( (f(u), f(v)) \) 也在 \( E_H \) 中，即：
\[ \forall (u, v) \in E_G, (f(u), f(v)) \in E_H \]
这个定义意味着，图的同态映射保留了边的存在性，但不要求完全保留顶点间的连接关系。
### 例子
#### 例子 1：简单图的同态
**图 \( G \)（完全图 \( K_3 \)）**：
- 顶点集合 \( V_G = \{a, b, c\} \)
- 边集合 \( E_G = \{(a, b), (b, c), (c, a)\} \)
**图 \( H \)（具有两个顶点和一条边的图）**：
- 顶点集合 \( V_H = \{x, y\} \)
- 边集合 \( E_H = \{(x, y)\} \)
**映射 \( f \)**：
- \( f(a) = x \)
- \( f(b) = x \)
- \( f(c) = y \)
**验证同态**：
- 对于 \( G \) 中的每一条边：
- 边 \( (a, b) \) 映射到 \( (x, x) \)，但 \( E_H \) 中只有边 \( (x, y) \)，因此这条边的映射不是有效的。
- 边 \( (b, c) \) 映射到 \( (x, y) \)，这是有效的。
- 边 \( (c, a) \) 映射到 \( (y, x) \)，这也是有效的。
在这个例子中，映射 \( f \) 并没有完全保留边的结构，因为 \( (a, b) \) 在 \( H \) 中并没有对应的边。因而，\( f \) 并不是一个有效的同态。
#### 例子 2：完整图的同态
**图 \( G \)（有三个顶点和两条边的图）**：
- 顶点集合 \( V_G = \{1, 2, 3\} \)
- 边集合 \( E_G = \{(1, 2), (2, 3)\} \)
**图 \( H \)（有四个顶点和两条边的图）**：
- 顶点集合 \( V_H = \{a, b, c, d\} \)
- 边集合 \( E_H = \{(a, b), (b, c)\} \)
**映射 \( f \)**：
- \( f(1) = a \)
- \( f(2) = b \)
- \( f(3) = c \)
**验证同态**：
- 对于 \( G \) 中的每一条边：
- 边 \( (1, 2) \) 映射到 \( (a, b) \)，这在 \( H \) 中是存在的。
- 边 \( (2, 3) \) 映射到 \( (b, c) \)，这在 \( H \) 中也是存在的。
在这个例子中，映射 \( f \) 是一个有效的同态，因为每条边在 \( G \) 中都有相应的边在 \( H \) 中与之对应。
### 总结
- 图的同态保留了边的存在性，但不要求顶点间的连接关系完全一致。
- 同态映射可以用来研究图的结构特性和图的简化问题。
- 在第一个例子中，映射并不是有效的同态，因为并不是所有边都可以映射到目标图中；而在第二个例子中，映射是有效的同态，因为所有边在目标图中都有对应的边。
- 同构Graph Isomorphism
图的同构（Graph Isomorphism）是图论中的一个核心概念，用于描述两个图在结构上的完全等价关系。两个图 \( G \) 和 \( H \) 被称为同构的，如果存在一个顶点的双射（双向一一映射） \( f: V_G \to V_H \)，使得对于 \( G \) 中的每一条边 \( (u, v) \in E_G \)，在 \( H \) 中有一条边 \( (f(u), f(v)) \in E_H \)，且这种映射保留了图的边的连接关系。即：
\[ \forall (u, v) \in E_G, (f(u), f(v)) \in E_H \]
### 例子
#### 例子 1：三角形图的同构
**图 \( G \)（完全图 \( K_3 \)）**：
- 顶点集合 \( V_G = \{a, b, c\} \)
- 边集合 \( E_G = \{(a, b), (b, c), (c, a)\} \)
**图 \( H \)（另外一个完全图 \( K_3 \)）**：
- 顶点集合 \( V_H = \{x, y, z\} \)
- 边集合 \( E_H = \{(x, y), (y, z), (z, x)\} \)
**同构映射 \( f \)**：
- \( f(a) = x \)
- \( f(b) = y \)
- \( f(c) = z \)
**验证同构**：
- 对于 \( G \) 中的每一条边：
- 边 \( (a, b) \) 映射到 \( (x, y) \)，这在 \( H \) 中存在。
- 边 \( (b, c) \) 映射到 \( (y, z) \)，这在 \( H \) 中存在。
- 边 \( (c, a) \) 映射到 \( (z, x) \)，这在 \( H \) 中存在。
在这个例子中，映射 \( f \) 是一个有效的同构映射，因为它保留了边的结构，说明图 \( G \) 和图 \( H \) 是同构的。
#### 例子 2：具有不同标签的同构图
**图 \( G \)（两个三角形共享一个公共边）**：
- 顶点集合 \( V_G = \{a, b, c, d, e\} \)
- 边集合 \( E_G = \{(a, b), (b, c), (c, a), (b, d), (d, e), (e, b)\} \)
**图 \( H \)（另一个具有相同结构的图）**：
- 顶点集合 \( V_H = \{1, 2, 3, 4, 5\} \)
- 边集合 \( E_H = \{(1, 2), (2, 3), (3, 1), (2, 4), (4, 5), (5, 2)\} \)
**同构映射 \( f \)**：
- \( f(a) = 1 \)
- \( f(b) = 2 \)
- \( f(c) = 3 \)
- \( f(d) = 4 \)
- \( f(e) = 5 \)
**验证同构**：
- 对于 \( G \) 中的每一条边：
- 边 \( (a, b) \) 映射到 \( (1, 2) \)，这在 \( H \) 中存在。
- 边 \( (b, c) \) 映射到 \( (2, 3) \)，这在 \( H \) 中存在。
- 边 \( (c, a) \) 映射到 \( (3, 1) \)，这在 \( H \) 中存在。
- 边 \( (b, d) \) 映射到 \( (2, 4) \)，这在 \( H \) 中存在。
- 边 \( (d, e) \) 映射到 \( (4, 5) \)，这在 \( H \) 中存在。
- 边 \( (e, b) \) 映射到 \( (5, 2) \)，这在 \( H \) 中存在。
在这个例子中，映射 \( f \) 是一个有效的同构映射，因为它保留了边的结构，说明图 \( G \) 和图 \( H \) 是同构的。
### 总结
- **图的同构** 需要存在一个顶点的双射，使得图的每条边在两个图中都有对应的边，并且这种映射完全保留了图的结构。
- **例子 1** 展示了两个完全图 \( K_3 \) 的同构，它们的结构完全相同，但顶点标签不同。
- **例子 2** 展示了两个具有不同标签但结构相同的图，它们之间的映射也是同构的。
通过这些例子，可以看到图的同构不仅考虑了图的结构，而且还允许不同的顶点标签，只要边的连接关系被保留。