最后更新: 2025-01-21 16:49 查看: 76 次反馈刷题

握手定理

## 握手定理
定理7－1．1 设 $G =< V , E >$ 为任意无向图， $V =\left\{v_1, v_2, \ldots, v_n\right\}$ ，
则

$$
\sum_{i=1}^{n} d\left(v_i\right)=2|E|
$$

说明 任何无向图中，各顶点度数之和等于边数的两倍。
证明 G中每条边（包括环）均有两个端点，
所以在计算G中各顶点度数之和时，
每条边均提供2度，当然 $|E|$ 条边，共提供 $2|E|$ 度。
定理7－1．3 设 $D =< V , E >$ 为任意有向图， $V =\left\{v_1, v_2, \ldots, v_n\right\}$
，则 $\sum_{i=1}^{ n } d\left(v_i\right)=2|E|$ ，且 $\sum_{i=1}^{ n } d^{+}\left(v_i\right)=\sum_{i=1}^{ n } d^{-}\left(v_i\right)=|E|$

## 握手定理的推论
推论 定理7－1．2 任何图（无向的或有向的）中，奇度顶点的个数是偶数。
证明 设 $G=<V$ ，$E>$ 为任意一图，令

$$
\begin{aligned}
& V_1=\{v \mid v \in V \wedge d(v) \text { 为奇数 }\} \\
& V_2=\{v \mid v \in V \wedge d(v) \text { 为偶数 }\}
\end{aligned}
$$

则 $V _1 \cup V_2= V , V _1 \cap V_2=\varnothing$ ，由握手定理可知

$$
2|E|=\sum_{v \in V} d(v)=\sum_{v \in V_1} d(v)+\sum_{v \in V_2} d(v)
$$

由于 $2| E |$ 和 $\sum_{v \in V_2} d(v)$ 为偶数，所以 $\sum_{v \in V_1} d(v)$ 为偶数但因 $v_1$ 中顶点度数为奇数，所以 $\left| V _1\right|$ 必为偶数。

## 度数列举例
 ![图片](/uploads/2025-01/7954cc.jpg)
 
 
 例1－2
（1）$(3,3,2,3)$ 与 $(5,2,3,1,4)$ 能成为图的度数序列吗 ？为什么？
（2）已知图G中有 10 条边， 4 个 3 度顶点，其余顶点的度数均小于等于 2 ，问 $G$ 中至少有多少个顶点？为什么？
解：
（1）不能，因为度数为奇数的顶点数目不是偶数。
（2）图G中顶点度数之和为 $2 \times 1 0 = 2 0$ ，而已有 4 个顶点的度数之和为 $4 \times 3=12$ ，还剩下 8 度，按题意，还需至少 4 个顶点，所以图 $G$ 至少有 8 个顶点。

例1－3
下列各组数中，哪些能够构成无向图的度数序列？哪些能够构成简单无向图的度数序列？
（1）$\{1,1,1,2,3\}$
（2）$\{2,2,2,2,2\}$
（3）$\{3,3,3,3\}$
（4）$\{1,2,3,4,5\}$
（5）$\{1,3,3,3\}$

提示：根据握手定理，非负整数序列能够构成无向图的度数序列的充要条件是 其和为偶数，即奇数度顶点的数目为偶数个。但这些无向图未必一定是简单图。
解：
 ![图片](/uploads/2025-01/378b7b.jpg)
 
 
 ## 问题研究
 问题：在一个部门的25个人中间，由于意见不同，是否可能每个人恰好与其他5个人意见一致？
解答：不可能。考虑一个图，其中顶点代表人，如两人意见相同，可用边连接，所以每个顶点都奇数度。存在奇数个度数为奇数的图，这不可能的。
说明：
   (1)很多离散问题可以用图模型求解。
   (2)为了建立一个图模型，需要决定顶点和边分别代表什么。
   (3)在一个图模型中，边经常代表两个顶点之间的关系。

例1-4 有9个人在一起打乒乓球，已知他们每人至少和其中另外3个人各打过一场球，则一定有一个人不止和3个人打过球。用图论语言解释这件事。

解：设 $v _1, v _2, \ldots, v _9$ 代表这 9 个人，建立顶点集 $V=\left\{v_1, v_2, \ldots, v_9\right\}$ ，对于其中的任意两个人 $v_i$和 $v _j(i \neq j)$ ，若 $V _i$ 和 $v _j$ 打过一场球，则 $\left\{ V _i, V_j\right\} \in E$ ，得到边集 $E$ ，则我们有了一个无向图 $G=(V, E)$ 。若每一个人仅和其余 3 个人各打过一场球，则 $d \left( v _i\right)=3$ ，而此时图 $G$ 的奇数度的顶点是 9 个，即是奇数个，与推论矛盾。矛盾说明，至少有一个人 $v _i, ~ d\left( v _i\right) \geq 4$ 。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：点的度数

下一篇：完全图

本文对您是否有用？有用 (0) 无用 (0)