图论中的握手定理

如果我们想了解握手定理，那么我们必须首先了解图。只有这样才能正确理解握手定理。

Graph

图是边和顶点非空集合的集合。图也可以表示为点和线的图形表示。图的两条线通过点连接。图的顶点用点表示，图的边用线表示。两个顶点通过一条边连接。图可以表示为 G = (V, E)，其中 V 表示顶点集合，E 表示边集合。图可以是各种类型，如加权图、有向图和无向图。

借助这些图，我们可以展示不同元素之间的关系和交互。为了理解它，我们可以设想一个社交网络，其中网络中的每个人都用一个顶点表示，人与人之间的友谊或连接可以用网络的边表示。同样，各种类型的网络或结构都可以借助图进行建模，例如交通系统、计算机网络模型和分子结构。因此，图是一个强大的工具，通过它我们还可以分析复杂的结构。

握手定理

握手定理可以描述为图论中的一个基本原理。我们可以用许多其他名称来称呼握手定理，即握手引理或度数和定理。该定理用于无向图，它指出所有顶点的度数之和等于图中边数的两倍。如果一个图有 E 条边和 n 个顶点，那么我们有一个公式可以用来表示握手定理

此处，

• Deg(v) 表示顶点 v 的度数。
• E 表示与顶点关联的边数。
• '∑(deg(v))' 表示所有顶点的度数之和。

握手定理用于显示图中边数和顶点度数之间的潜在连接。此连接用于提供对图结构和关系的宝贵见解。

注意：从上述握手定理公式中，我们可以得出一些重要的结论，如下所示

• 在一个图中，如果我们对所有顶点的度数求和，那么结果总是偶数。
• 在一个图中，如果我们对所有度数为奇数的顶点求和，那么结果总是偶数。
• 在一个图中，如果我们找到度数为奇数的顶点数量，那么结果总是偶数。

握手定理的含义和应用

握手定理有很多应用和含义，可以更好地理解图的结构和属性。现在，我们将展示握手定理的一些应用和含义，如下所示

1. 网络分析：借助该定理，可以轻松分析网络。我们可以通过揭示顶点度数形式的模式来分析各种类型的网络，如社交网络、通信网络、交通网络等等。
2. 数据验证：借助该定理，可以轻松验证数据表示。在验证数据时，如果发现任何不一致或错误，则清楚地表明该定理被违反了。
3. 结构洞察：借助该定理，可以轻松获得对图结构的洞察。它可以用来了解图的顶点是如何相互连接的。
4. 图设计：借助该定理，可以轻松展示用于图中各种应用程序的图设计。它可以在此处用于在图的顶点之间创建平衡连接。
5. 连通性分析：借助该定理，可以轻松分析图的连通性。它还可以用于判断任何图是连通的还是非连通的。
6. 计算机科学算法：借助该定理，可以轻松设计用于各种图遍历任务的算法。这种任务主要用于数据分析或计算机科学。

握手定理的证明

我们上面已经学习了一个关于图的边数和图的顶点度数之和之间关系的公式，为了证明握手定理，我们必须证明那个公式。在这里，我们将像这样一步一步地证明这个定理

第 1 步：定义

这是第一步，我们假设一个具有一些顶点和边的无向图。在这里，边用 E 表示，顶点用 n 表示。在这里，我们还假设一些符号来表示图的顶点度数。所以，我们假设它们为 deg(v1), deg(v2), deg(v3), ...., deg(vn)。

第 2 步：计数边

在任何图中，图的每条边都有两个端点。因此，图的每条边都包含两个顶点的度数。因此，我们可以说顶点度数之和是图边数的两倍，如下所示

第 3 步：计算总度数

在上面的等式中，左侧所示的部分表示所有顶点的度数之和。我们可以通过以下方式对其进行数学表示

第 4 步：与边数的关系

借助上述步骤，表明度数之和是边数的两倍。因此，我们可以通过以下方式将 2*E 替换为 ∑(deg(v))

第 5 步：结论

借助上述等式，可以很容易地表明无向图所有顶点的度数之和与边数的两倍相似。所以，最后，表示边和顶点度数之和之间关系的公式如下所示

因此，借助上述步骤，我们证明了握手定理。该定理还用于通过显示边数和顶点度数之间的逻辑连接来显示图中基本关系。

握手定理的推论

在握手定理的情况下，我们总共有 5 种推论，它们都与主要结果相关或源自主要结果。这些推论可用于提供对图中度数、顶点和边之间关系的额外见解，如下所示

推论 1：顶点的平均度数

如果有一个无向图，我们想计算顶点的平均度数，那么我们可以通过将无向图所有顶点的度数之和除以顶点总数来做到这一点。有一个公式用于找到顶点的平均度数。该公式描述如下

在上述公式中

符号 E 表示边数，符号 n 表示顶点数。

推论 2：奇数度数顶点的偶数

如果我们有一个无向图，我们想计算包含奇数度数的顶点数量，那么我们总是得到偶数作为顶点数量的结果。这个推论源于一个事实，即当我们计算奇数之和时总是得到偶数，当我们计算度数之和（边数的两倍）时总是得到偶数。

推论 3：二分图的握手定理

无向图的握手定理和二分图的握手定理必须有不同的公式。二分图的顶点应该分成两个不相交的集合。在二分图的情况下，一个集合的每个顶点必须通过一条边连接到第二个集合的任何顶点。同一集合内的顶点不能连接。因此，根据握手定理，第一个集合中顶点度数之和与第二个集合中顶点度数之和应该彼此相似。以下方式用于显示此结果

在这里，不相交的顶点集合用集合 A 和 B 表示。

推论 4：最大边数

如果有一个图，其中有 n 个顶点，那么有一个公式可以通过它获得最大边数，而不会创建任何循环或多条边（这意味着图必须是简单的），如下所示

借助此推论，可以轻松显示对边数上限的洞察。

推论 5：多重图的握手定理

无向图的握手定理和多重图的握手定理的公式是不同的。在多重图的情况下，这种关系扩展到多于一条边。在多重图的情况下，同一对顶点之间可能有多于一条边。因此，根据握手定理，所有顶点的度数之和是边数的两倍（这里，我们也包括多条边）。

握手定理的例子

握手定理包含很多例子。一些例子如下所示

示例 1

这个例子包含一个简单图，其中边数为 30，每个顶点的度数为 2。在这里，我们需要计算这个图的顶点数。

解：根据问题，我们知道关于图的一些细节，如下所示

图的边数 = 30

图的每个顶点的度数 = 2

在这里，我们还假设图包含 n 个顶点。

根据握手定理的定义，我们知道顶点和边之间的关系，如下所示

所有顶点的度数之和 = 2 * 边数

现在我们将边和顶点的值代入上述握手公式，如下所示

n * 2 = 2 * 30

n * 2 = 60

n = 60 / 2

n = 30

因此，该图中的顶点数 = 30

示例 2

这个例子包含一个图，其中包含一些顶点和边。在这里，边数为 40，在所有顶点中，有 4 个顶点度数为 5，所有其他顶点度数为 3。在这里，我们需要计算这个图的顶点数。

解：根据问题，我们知道关于图的一些细节，如下所示

图的边数 = 40

度数为 4 的顶点数 = 5

图的所有其他顶点的度数为 3。

在这里，我们还假设图包含 n 个顶点。

根据握手定理的定义，我们知道顶点和边之间的关系，如下所示

所有顶点的度数之和 = 2 * 边数

现在我们将边和顶点的值代入上述握手公式，如下所示

5 * 4 + (n - 4) * 3 = 2 * 40

20 + 3n - 12 = 80

3n = 60 + 12

3n = 72

n = 24

因此，该图中的顶点数 = 24

示例 3

这个例子包含一个图，其中包含一些顶点和边。在这里，边数为 50，在所有顶点中，1 个顶点度数为 3，3 个顶点度数为 5，5 个顶点度数为 4。在这里，我们需要计算这个图中断数为 2 的顶点数。

解：根据问题，我们知道关于图的一些细节，如下所示

图的边数 = 50

度数为 3 的顶点数 = 1

度数为 5 的顶点数 = 3

度数为 4 的顶点数 = 5

在这里，我们还假设度数为 2 的顶点数 = n。

根据握手定理的定义，我们知道顶点和边之间的关系，如下所示

所有顶点的度数之和 = 2 * 边数

现在我们将边和顶点的值代入上述握手公式，如下所示

1 * 3 + 3 * 5 + 5 * 4 + n * 2 = 50 * 2

3 + 15 + 20 + 2n = 100

2n = 100 - 15 - 3 - 20

2n = 62

n = 62 / 2

n = 31

因此，该图中断数为 2 的顶点数 = 31

示例 4

这个例子包含一个简单图，其中边数为 25，每个顶点的度数为 k。在这里，我们需要计算所有给定选项中可能的顶点数。选项如下所示

1. 18
2. 25
3. 30
4. 9

解：根据问题，我们知道关于图的一些细节，如下所示

图的边数 = 25

图的每个顶点的度数 = k

在这里，我们还假设图包含 n 个顶点。

根据握手定理的定义，我们知道顶点和边之间的关系，如下所示

所有顶点的度数之和 = 2 * 边数

现在我们将边和顶点的值代入上述握手公式，如下所示

n * k = 2 * 25

k = 50 / n

有一些重要点可以计算该图的顶点数，如下所示

图的每个顶点的度数是整数。因此，我们只允许 n 的那些值，这些值会给出 k 的整数值。

现在我们通过代入所有上述给定选项来获取 k 的值

1. 对于 n = 18，k 的值将为 2.7。k 的值不是整数。因此，不允许 n = 18。
2. 对于 n = 25，k 的值将为 2。k 的值是整数。因此，允许 n = 25。
3. 对于 n = 30，k 的值将为 1.6。k 的值不是整数。因此，不允许 n = 30。
4. 对于 n = 9，k 的值将为 5.5。k 的值不是整数。因此，不允许 n = 9。

因此，选项 (B) 是正确的。

示例 5

假设有一个聚会，总共有 30 名成员。在这里，我们假设每个成员都与恰好 3 名其他成员握手的情况。那么，我们需要找出聚会中发生的握手总数。

解：对于每次握手，我们需要总共 2 个人。因此，握手有助于两个顶点的度数。在这里，边用于显示握手次数，顶点用于显示聚会成员人数。

根据握手定理的定义，我们知道顶点和边之间的关系，如下所示

所有顶点的度数之和 = 2 * 边数

我们可以通过以下方式找到度数之和

度数之和 = 2 * 30 = 60

现在我们将边和顶点的值代入上述握手公式，如下所示

60 = 2 * E

E = 60 / 2

E = 30

因此，在这个聚会中，握手总数 = 30。

示例 6

假设一所大学组织了一场体育锦标赛，共有 10 支队伍。锦标赛中的每支队伍都必须与其他每支队伍恰好比赛一次。在这里，我们需要找出需要进行的总比赛场次。

解：在这里，边用于显示比赛场次，顶点用于显示参加锦标赛的队伍数量。

根据握手定理的定义，我们知道顶点和边之间的关系，如下所示

所有顶点的度数之和 = 2 * 边数

我们可以通过以下方式找到度数之和

度数之和 = 10(10 - 1)

度数之和 = 90

现在我们将边和顶点的值代入上述握手公式，如下所示

90 = 2 * E

E = 90 / 2

E = 45

因此，本次锦标赛中，总比赛场次将为 = 45。

例 7：假设我们住在一家酒店，酒店的每个成员只与另一个成员握手一次。如果发生握手的次数是 28，那么我们需要找出酒店中在场的人数。

解：为此，我们假设酒店中在场的人数是 n。在这里，边用于显示握手次数，顶点用于显示酒店中在场的人数。

根据握手定理的定义，我们知道顶点度数和边之间的关系，如下所示

所有顶点的度数之和 = 2 * 边数

众所周知，酒店的每个成员都与 (n-1) 个其他成员握手。因此，度数之和为 n(n-1)。所以，

n(n-1) = 2 * 28

n(n-1) = 56

n² - n - 56 = 0

(n - 8) (n + 7) = 0

当我们设置每个因子时，我们将得到以下结果

n - 8 = 0 → n = 8

n + 7 = 0 → n = -7

所以，我们得到 n 的两个值，即 8 和 -7，但我们选择正数成员。

因此，酒店中成员总数为 8。

示例 8

假设有一个社交网络，其中所有用户的度数之和为 80。在这里，我们需要找出网络中可能发生的连接总数。

解：为此，我们假设酒店中在场的人数是 n。在这里，边用于显示连接数，顶点用于显示网络中在场的用户数。

根据握手定理的定义，我们知道顶点度数和边之间的关系，如下所示

所有顶点的度数之和 = 2 * 边数

我们可以通过以下方式找到度数之和

80 = 2 * E

E = 80 / 2

E = 40

因此，在这个社交网络中，连接总数 = 40。