握手引理_图论中的握手引理–握手定理

港控/mmm° 2022-12-07 12:57 253阅读 0赞

![f70cd51f3ef71638ed52c52d56ef0a2a.png][]

握手引理

Hello Everyone,

大家好，

Today we will see Handshaking lemma associated with graph theory. Before starting lets see some terminologies.

今天，我们将看到与图论相关的握手引理。 在开始之前，让我们先看一些术语。

**Degree**: It is a property of vertex than graph. Degree is a number of edges associated with a node.

**度** ：顶点比图的属性。 度是与节点关联的许多边。

**Pendant vertices**: Vertices with degree 1 are known as pendant vertices.

**吊坠顶点** ：顶点度数为1被称为挂件顶点。

**Isolated vertices**: Vertices with degree 0 are known as Isolated vertices.

**孤立的顶点** ：度为0的顶点称为孤立的顶点。

Now let us see the statement of the lemma first, It says:

现在让我们首先看一下引理的陈述，它说：

***In every finite undirected graph number of vertices with odd degree is always even. ***

***在每个有限的无向图中，奇数度的顶点数始终为偶数。***

**Note**: This theorem is only correct for undirected graphs with finite length.

**注意** ：该定理仅适用于长度有限的无向图。

The Handshaking lemma can be easily understood once we know about the degree sum formula. The degree sum formula says that:

一旦我们知道度和公式，就可以轻松地理解握手问题。 度和公式表示：

***The summation of degrees of all the vertices in an undirected graph is equal to twice the number of edges present in it. ***

***无向图中所有顶点的度数总和等于其中存在的边数的两倍。***

It can be stated as:

可以这样表示：

![Handshaking Theorem 1][]

This is evident as every edge is associated with two nodes and will add 2 to the total summation.

这很明显，因为每个边都与两个节点相关联，并且会将2加到总和上。

Let’s take an example :

让我们举个例子：

![Handshaking Lemma][]

In the above image the number of edges is 8, so |E| = 8.

在上图中，边的数量为8，因此| E | = 8。

Now,

现在，

deg(A) = 3

度(A)= 3

deg(B) = 2

度(B)= 2

deg(C) = 3

摄氏度(摄氏度)= 3

deg(D) = 2

度(D)= 2

deg(E) = 4

度(E)= 4

deg(F) = 2

度(F)= 2

Which sums upto 16 which is equal to 2\*|E|.

总计16等于2 \* | E |。

Now let’s come to our original statement.

现在，让我们来看一下原始说明。

***In every finite undirected graph number of vertices with odd degree is always even. ***

***在每个有限的无向图中，奇数度的顶点数始终为偶数。***

Now to understand this,

现在了解一下

Lets write the above degree some formula as:

让我们将上述程度的一些公式写为：

![Handshaking Theorem 2][]

Here k denotes vertices with odd degree and t denotes vertices with degree.

在此，k表示具有奇数度的顶点，t表示具有度数的顶点。

The summation of degrees of all the vertices with even degree will be even now remaining are the vertices with odd degree and as we know the total sum must be even so the summation of degrees of all the vertices having odd degree must be even. This is only possible if the number of vertices is even which proves our lemma.

现在，所有具有偶数度数的顶点的度数总和将是偶数个，而我们知道总和必须是偶数，因此所有具有奇数度数的顶点的度数之和必须是偶数。 仅当顶点数为偶数且证明我们的引理时才有可能。

The above lemma is very useful for proving some very interesting properties of trees and to understand different properties of cut vertices, Full and complete binary trees.

上面的引理对于证明树的一些非常有趣的属性以及理解切点，完整和完整的二叉树的不同属性非常有用。

> 翻译自: [https://www.thecrazyprogrammer.com/2019/10/handshaking-lemma.html][https_www.thecrazyprogrammer.com_2019_10_handshaking-lemma.html]

握手引理

[f70cd51f3ef71638ed52c52d56ef0a2a.png]: /images/20221123/f593267461b34863bead1b33604320ff.png
[Handshaking Theorem 1]: /images/20221123/6d8f75da849d4490aa950da7f6a93271.png
[Handshaking Lemma]: /images/20221123/4ae0f7fa43964a4ab15d497773ab2b5c.png
[Handshaking Theorem 2]: /images/20221123/c62858bfb66d42e8b9d41e740a12ff84.png
[https_www.thecrazyprogrammer.com_2019_10_handshaking-lemma.html]: https://www.thecrazyprogrammer.com/2019/10/handshaking-lemma.html