图论-同构

图可以以具有相同数量的顶点、边以及相同的边连通性的不同形式存在。这样的图称为同构图。请注意，我们在本章中对图表进行标记主要是为了引用它们并相互识别它们。

同构图

两个图 G 1和 G 2被称为同构如果 -

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

  • 它们的边缘连接性被保留。

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

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.

笔记

如果 G 1 ≠ G 2则 -

|V(G 1 )| = |V(G 2 )|

|E(G 1 )| = |E(G 2 )|

G 1和G 2的度数序列相同。

如果顶点 {V 1 , V 2 , .. Vk} 在 G 1中形成长度为 K 的循环，则顶点 {f(V 1 ), f(V 2 ),… f(Vk)} 应形成循环G 2中的长度K。

上述所有条件都是图G 1和G 2同构所必需的，但不足以证明图G 1 和G 2 同构。

  • (G 1 ≡ G 2 ) 当且仅当 (G 1 − ≡ G 2 −) 其中 G 1和 G 2是简单图。

  • (G 1 ≠ G 2 ) 如果 G 1和 G 2的邻接矩阵相同。

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

例子

下列哪些图是同构的？

图是同构的

在图 G 3中，顶点“w”仅具有度 3，而所有其他图顶点具有度 2。因此 G3 与 G 1或 G 2不同构。

取 G 1和 G 2的补集，你有 -

其他图顶点

这里，(G 1 − == G 2 −)，因此(G 1 == G 2 )。

平面图

如果图“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”具有与 K 5或 K 3,3同胚的子图。

同态

两个图 G 1和 G 2被称为同态，如果这些图中的每一个都可以通过用更多顶点划分 G 的一些边而从同一图“G”获得。看一下下面的例子 -

同态

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

一个顶点

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

完整图

如果 G 1同构于 G 2，则 G 与 G2 同构，但反之则不必成立。

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

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

  • 完全图 K n是平面的当且仅当 n ≤ 4。

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

  • 具有最少顶点数的简单非平面图是完全图 K 5。

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

多面体图

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

  • 3|V| ≤ 2|E|

  • 3|R| ≤ 2|E|