正则图和二部图

本文概述

• 正则图
• 二部图
• 完全二部图
• 欧拉路径
• 陈述并证明欧拉定理

如果G中的每个顶点都与G中的每个其他顶点相连, 则称图G是完整的。因此, 必须连接完整的图G。具有n个顶点的完整图由Kn表示。该图显示了曲线K1至K6。

正则图

如果图的所有顶点具有相同的度数K, 则称该图为正则或K-正则图。其所有顶点的度数为2的图称为2正则图。完整的图Kn是度数n-1的正则。

示例1：绘制2度和3度的正则图。

解决方案：2级和3级的正则图如图所示：

示例2：绘制一个包含五个顶点的2正则图。

解决方案：图中显示了五个顶点的2正则图：

示例3：绘制一个包含五个顶点的3正则图。

解决方案：不可能绘制五个顶点的3正则图。 3正则图的顶点数必须为偶数。

二部图

如果图G =（V, E）的顶点V可以划分为两个子集V1和V2, 使得G的每个边将V1的顶点连接到顶点V2, 则将其称为二部图。用Kmn表示, 其中m和n分别是V1和V2中的顶点数。

示例：绘制二部图K2、4和K3, 4。假定有任意数量的边。

解决方案：首先在两个平行的列或行上绘制适当数量的顶点, 然后将一个列或行中的顶点与另一列或行中的顶点连接起来。双向图K2, 4和K3, 4分别显示在图中。

完全二部图

如果图G =（V, E）的顶点V可以划分为两个子集V1和V2, 使得V1的每个顶点连接到V2的每个顶点, 则称为完全二部图。完整的二部图中的边数为m.n, 因为m个顶点中的每个顶点都连接到n个顶点中的每个顶点。

示例：绘制完整的二部图K3, 4和K1, 5。

解决方案：首先在两个平行的列或行中绘制适当数量的顶点, 然后将第一列或第一行中的顶点与第二列或第二行中的所有顶点连接起来。图K3, 4和K1, 5如图所示：

欧拉路径

通过图的欧拉路径是一条路径, 其边缘列表仅包含一次图形的每个边缘。

欧拉电路：欧拉电路是通过图形的路径, 其中初始顶点第二次出现为终点。

欧拉图：欧拉图是具有欧拉回路的图。欧拉电路仅对每个边使用一次, 但是顶点可以重复。

示例：图中所示的图是欧拉图。确定该图的欧拉电路。

解决方案：此图的欧拉电路为

V1, V2, V3, V5, V2, V4, V7, V10, V6, V3, V9, V6, V4, V10, V8, V5, V9, V8, V1

我们可以为没有奇数个顶点的连接图生成一个欧拉电路。

陈述并证明欧拉定理

陈述：考虑具有R区域, V顶点和E边的任何连接的平面图G =（V, E）。然后, V + R-E ＝ 2。

证明：对边的数量使用归纳法证明该定理。

归纳的基础：假设每个边e = 1, 然后我们有两种情况, 其图如图所示：

在图中：我们有V = 2和R = 1。因此2 + 1-1 = 2

在图中：V = 1, R = 2。因此1 + 2-1 = 2。

因此, 归纳的基础得以验证。

归纳步骤：让我们假设该公式对具有K个边的连接平面图成立。

令G为K + 1边的图。

首先, 我们假设G不包含任何电路。现在, 取一个顶点v并找到一个从v开始的路径。由于G没有电路, 因此只要找到一条边, 我们就会有一个新的顶点。最后, 我们将到达一个度为1的顶点v。因此我们无法进一步前进, 如图所示：

现在删除顶点v以及入射在v上的相应边。因此, 我们剩下了具有K个边的图G *, 如图所示：

因此, 通过归纳假设, 欧拉公式对G *成立。

现在, 由于G的边缘比G *多, 因此顶点的数量比G *多, 且区域数量与G *中相同。因此, 该公式也适用于G。

其次, 我们假设G包含一个电路, 并且e是图所示电路中的边沿：

现在, 因为e是两个区域的边界的一部分。因此, 我们只删除边缘, 然后剩下具有K个边缘的图G *。

因此, 通过归纳假设, 欧拉公式对G *成立。

现在, 由于G的边缘比G *多, 因此与G *多的区域具有与G *相同的顶点数。因此, 该公式也适用于G, 它可以验证归纳步长, 从而证明定理。