---

图论 - 同构

图可以以不同的形式存在，但具有相同数量的顶点、边以及相同的边连通性。这样的图称为同构图。请注意，我们在本章中标记图主要是为了引用它们并将它们彼此区分开来。

同构图

如果 −，则两个图 G₁ 和 G₂ 被称为同构。

• 它们的组件（顶点和边）数量相同。

• 它们的边连通性得以保留。

注意 − 简而言之，在两个同构图中，一个是另一个的调整版本。未标记图也可以被认为是同构图。

There exists a function ‘f’ from vertices of G1 to vertices of G2
   [f: V(G1) ⇒ V(G2)], such that
Case (i): f is a bijection (both one-one and onto)
Case (ii): f preserves adjacency of vertices, i.e., if the edge {U, V} ∈ G1, then the
edge {f(U), f(V)} ∈ G2, then G1 ≡ G2.

注意

If G₁ ≡ G₂ then −

|V(G₁)| = |V(G₂)|

|E(G₁)| = |E(G₂)|

G₁和G₂的度序列相同。

如果顶点{V₁，V₂，.. Vk}在G₁中形成一个长度为K的循环，则顶点{f(V₁)，f(V₂)，… f(Vk)}应该在G₂中形成一个长度为K的循环。

以上所有条件都是图G₁和G₂同构的必要条件，但不足以证明这两个图是同构的。

• (G₁ ≡ G₂)当且仅当(G₁− ≡ G₂−)，其中 G₁ 和 G₂ 是简单图。

• (G₁ ≡ G₂)，如果 G₁ 和 G₂ 的邻接矩阵相同。

• (G₁ ≡ G₂)，当且仅当 G₁ 和 G₂ 的对应子图（通过删除 G1 中的一些顶点及其在图 G₂ 中的图像获得）是同构的。

示例

以下哪些图是同构的？

在图 G₃ 中，顶点"w"的度数只有 3，而所有其他图顶点的度数都是 2。因此，G3 不与 G₁ 或 G₂ 同构。

取 G₁ 和 G₂ 的补集，则有 −

这里，(G₁− ≡ G₂−)，因此 (G₁ ≡ G₂)。

平面图

如果图"G"可以绘制在平面或球面上，使得没有两条边以 为交点相交，则称该图为平面图非顶点。

示例

区域

每个平面图都将平面划分为称为区域的连通区域。

示例

有界区域的度 r = deg(r) = 包围区域 r 的边数。

deg(1) = 3
deg(2) = 4
deg(3) = 4

deg(4) = 3
deg(5) = 8

无界区域的度数r = deg(r) = 包围区域 r 的边数。

deg(R1) = 4
deg(R2) = 6

在平面图中，以下性质成立 −

在具有'n'个顶点的平面图中，所有顶点的度数之和为 −

n Σ i=1 deg(V_i) = 2|E|

根据区域度数之和定理，在具有'n'个区域的平面图中，区域度数之和为 −

n Σ i=1 deg(ri) = 2|E|

根据上述定理，可以得出以下结论 −

在平面图中，

如果每个区域的度数为K，则区域度数之和为 −

K|R| = 2|E|

如果每个区域的度至少为 K(≥ K)，则

K|R| ≤ 2|E|

如果每个区域的度最多为 K(≤ K)，则

K|R| ≥ 2|E|

注意 − 假设所有区域的度相同。

根据平面图的欧拉公式，

如果图"G"是连通平面图，则

|V| + |R| = |E| + 2

如果平面图有"K"个分量，则

|V| + |R|=|E| + (K+1)

其中，|V| 为顶点数，|E| 为边数，|R| 为区域数。

边顶点不等式

如果"G"是连通平面图，且每个区域的度至少为"K"，则

|E| ≤ k / (k-2) {|v| - 2}

你知道，|V| + |R| = |E| + 2

K.|R| ≤ 2|E|

K(|E| - |V| + 2) ≤ 2|E|

(K - 2)|E| ≤ K(|V| - 2)

|E| ≤ k / (k-2) {|v| - 2}

如果 'G' 是简单连通平面图，则

|E| ≤ 3|V| − 6
|R| ≤ 2|V| − 4

至少存在一个顶点 V •∈ G，使得 deg(V) ≤ 5。

如果"G"是简单连通平面图（至少有 2 条边）且没有三角形，则

|E| ≤ {2|V| – 4}

库拉托夫斯基定理

图"G"非平面当且仅当"G"有一个子图与 K5 或 K3,3同胚。

同态

如果可以通过用更多顶点划分 G 的一些边，从同一个图"G"获得这两个图 G₁ 和 G₂，则称这两个图是同态的。看一下下面的例子 −

通过添加一个顶点将边'rs'分成两条边。

下面显示的图与第一个图同态。

如果 G₁ 同构于 G₂，则 G 同构于 G2，但反之则不一定成立。

• 任何具有 4 个或更少顶点的图都是平面的。

• 任何具有 8 条或更少边的图都是平面的。

• 当且仅当 n ≤ 4 时，完全图 Kn 才是平面的。

• 完全二分图 Km, n 是平面的当且仅当 m ≤ 2 或 n ≤ 2。

• 顶点数最少的简单非平面图是完全图 K5。

• 边数最少的简单非平面图是 K3, 3。

多面体图

如果每个顶点的度数≥3，即 deg(V)≥3∀V∈G，则简单连通平面图称为多面体图。

• 3|V| ≤ 2|E|

• 3|R| ≤ 2|E|

---