最后更新: 2025-11-21 17:01 查看: 139 次纠错评论(0) 课件开VIP

顶点的度数与握手定理

## 顶点的度数与握手定理
由于结点与边的关联关系是图的根本属性，因此结点上所关联的边的数目，是图的属性研究的重要依据，这里给出相关的定义与定理。

**定义5.2** 在无向图中，顶点 $\boldsymbol{v}$ 作为边的端点的次数之和为 $\boldsymbol{v}$ 的**度数**，简称**度**，记作 $d(\boldsymbol{v})$ ．

在有向图中，称顶点 $\boldsymbol{v}$ 作为边的始点的次数之和为 $\boldsymbol{v}$ 的**出度**，记作 $d^{+}(\boldsymbol{v})$ ；称 $\boldsymbol{v}$ 作为边的终点的次数之和为 $\boldsymbol{v}$ 的**入度**，记作 $d^{-}(\boldsymbol{v})$ ；称 $\boldsymbol{v}$ 作为边的端点的次数之和为 $\boldsymbol{v}$ 的度数，简称度，记作 $d(\boldsymbol{v})$ 。显然，

$$
\boxed{
d(\boldsymbol{v})=d^{+}(\boldsymbol{v})+d^{-}(\boldsymbol{v})
}
$$

![图片](/uploads/2025-11/2497c3.jpg)

在图5．1（a）中，$d\left(\boldsymbol{v}_1\right)=4, d\left(\boldsymbol{v}_2\right)=4, d\left(\boldsymbol{v}_3\right)=3, d\left(\boldsymbol{v}_5\right)=0$ 。在图5．1（b）中，$d^{+}\left(\boldsymbol{v}_1\right)=2$ ， $d^{-}\left(\boldsymbol{v}_1\right)=1, d\left(\boldsymbol{v}_1\right)=3, d^{+}\left(\boldsymbol{v}_2\right)=1, d^{-}\left(\boldsymbol{v}_2\right)=2, d\left(\boldsymbol{v}_2\right)=3$ 。注意，在图5．1（a）中， $\boldsymbol{v}_2$ 作为环 $e_1$ 的端点是 2 次。在图5．1（b）中，$v_1$ 作为环 $e_1$ 的一次始点、一次终点，即 2 次端点。称度数为 1 的顶点为**悬挂顶点**，它所关联的边为**悬挂边**．

对于无向图 $G=\langle V, E\rangle$ ，记

$$
\begin{gathered}
\triangle(G)=\max \{d(v) \mid v \in V\}, \\
\delta(G)=\min \{d(v) \mid v \in V\},
\end{gathered}
$$

分别称为 $G$ 的**最大度**和**最小度**．

对于有向图 $D=\langle V, E\rangle$ ，除了最大度 $\triangle(D)$ 、最小度 $\delta(D)$ 外，还有最大出度 $\triangle^{+}(D)$ 、最大入度 $\triangle^{-}(D)$ 、最小出度 $\delta^{+}(D)$ 、最小入度 $\delta^{-}(D)$ ，分别定义如下：

$$
\begin{aligned}
\triangle(D) & =\max \{d(\boldsymbol{v}) \mid \boldsymbol{v} \in V\} ; \\
\delta(D) & =\min \{d(\boldsymbol{v}) \mid \boldsymbol{v} \in V\} ; \\
\triangle^{+}(D) & =\max \left\{d^{+}(\boldsymbol{v}) \mid \boldsymbol{v} \in V\right\} ; \\
\triangle^{-}(D) & =\max \left\{d^{-}(\boldsymbol{v}) \mid \boldsymbol{v} \in V\right\} ; \\
\delta^{+}(D) & =\min \left\{d^{+}(\boldsymbol{v}) \mid \boldsymbol{v} \in V\right\} ; \\
\delta^{-}(D) & =\min \left(d^{-}(\boldsymbol{v}) \mid \boldsymbol{v} \in V\right\} .
\end{aligned}
$$

在图5．1（a）中，$\Delta=4, \delta=0$ ．图5．1（b）中，$\triangle=4, \delta=2, \Delta^{+}=2, \Delta^{-}=3, \delta^{+}=1, \delta^{-}=0$ ．
下面定理给出图中顶点度数与边数之间的关系．

> **定理 5．1（握手定理）设图 $G=\langle V, E\rangle$ 为无向图或有向图，$V=\left\{v_1, v_2, \cdots, v_n\right\}$ ，边数 $|E|=m$ ，则$\sum_{i=1}^n d\left(v_i\right)=2 m$**

证明 每一条边有 2 个端点，所有顶点的度数之和等于它们作为端点的次数之和，因此恰好等于边数的 2 倍。

握手定理是图论中的基本定理，它有一个重要推论．

对于顶点标定的无向图，它的度数列是唯一的．反之，对于任意给定的非负整数列 $d=\left(d_1, d_2, \cdots, d_n\right)$ ，若存在以 $V=\left\{v_1, v_2, \cdots, v_n\right\}$ 为顶点集的 $n$ 阶无向图 $G$ ，使得 $d\left(v_i\right)=d_i$ ，则称 $d$ 是可图化的．特别地，如果得到的图是简单图，则称 $d$ 是可简单图化的．

> **推论 任何图（无向的或有向的）中，度数为奇数的顶点个数是偶数**．

对有向图来说，还有下面的定理．

**定理5.2** 设有向图 $D=\langle V, E\rangle, V=\left\{\boldsymbol{v}_1, \boldsymbol{v}_2, \cdots, \boldsymbol{v}_n\right\},|E|=m$ ，则

$$
\sum_{i=1}^n d^{+}\left(v_i\right)=\sum_{i=1}^n d^{-}\left(v_i\right)=m .
$$

与定理 5.1 的证明类似．

以上两定理及其推论都是非常重要的，应掌握并灵活运用．

设 $v=\left\{Y_1, Y_2, \cdots, Y_N\right\}$ 为图 $g$ 的顶点集，称 $\left(D\left(Y_1\right), D\left(Y_2\right), \cdots, D\left(Y_N\right)\right)$ 为 $g$ 的**度数序列**。有向图还有入度序列和出度序列．图5．1（a）的度数序列为 $(4,4,3,1,0)$ ，图5．1（b）的度数序列为 $(3,3,2,4,2)$ ，人度序列为 $(1,2,0,3,1)$ ，出度序列为 $(2,1,2,1,1)$ ．

`例`（1）（ $3,3,2,3$ ），（ $5,2,3,1,4$ ）分别能成为图的度数序列吗？为什么？
（2）已知图 $G$ 中有 10 条边， 4 个度数为 3 的顶点，其余顶点的度数均小于等于 2 ，问 $G$ 中至少有多少个顶点？为什么？

解（1）由于这两个序列中，奇数个数均为奇数，由握手定理的推论可知，它们都不能成为图的度数列．
（2）图中边数 $m=10$ ，由握手定理可知，$G$ 中各顶点度数之和为 20,4 个 3 度顶点占去 12 度，还剩 8 度．若其余全是 2 度顶点，还需要 4 个顶点来占用这 8 度，所以 $G$ 至少有 8 个顶点．

`例` 判断下列各非负整数列哪些是可图化的，哪些是可简单图化的？
（1）$(5,5,4,4,2,1)$ ．
（2）$(5,4,3,2,2)$ ．
（3）$(3,3,3,1)$ ．
（4）$(4,4,3,3,2,2)$ ．
（5）$(3,2,2,1)$ ．
解 根据定理易知，除序列（1）不可图化外，其余各序列都可图化。
除（5）外都不可简单图化．原因如下：
（2）中序列有 5 个数，若它可简单图化，设所得图为 $G$ ，则 $\Delta(G)=\max \{5,4,3,2,2\}=5$ ，这与定理 8.3 矛盾．所以（2）中序列不可简单图化．类似可证（4）中序列不可简单图化．

对于（3）中的序列，假设可以简单图化为 $G=\langle V, E\rangle, G$ 以（3）中序列为度数列．不妨设 $V=\left\{v_1, v_2, v_3, v_4\right\}$ ，且 $d\left(v_1\right)=d\left(v_2\right)=d\left(v_3\right)=3, d\left(v_4\right)=1$ ，由于 $d\left(v_4\right)=1$ ，因而 $v_4$ 只能与 $v_1, v_2, v_3$之一相邻，于是 $v_1, v_2, v_3$ 不可能都是 3 度顶点，这是矛盾的，因而（3）中序列也不可简单图化．
（5）可简单图化，图 8.3 所示的无向简单图即以序列（5）为度数列．

![图片](/uploads/2025-11/031332.jpg)

## 理解:握手定理
握手定理是图论中的一个基本定理，它描述了无向图中顶点度数之和与边数之间的关系。下面我将从定理陈述、直观理解、证明思路、例子和应用等方面详细解释这个定理。

### 1. **定理陈述**
握手定理的正式表述是：在任何一个无向图中，所有顶点的度数之和等于边数的两倍。即，如果图 $ G = (V, E) $ 有 $ n $ 个顶点和 $ m $ 条边，那么：
$$
\sum_{v \in V} \deg(v) = 2m
$$
其中，$\deg(v)$ 表示顶点 $v$ 的度数（即与 $v$ 相连的边的数量）。

### 2. **直观理解**
握手定理得名于一个经典的握手比喻：假设在一个派对中，每个人与其他一些人握手。那么，所有人的握手次数总和等于握手次数的两倍，因为每次握手涉及两个人。同样，在图论中，每条边连接两个顶点，因此每条边都会贡献两个度数（每个顶点各一个）。所以，所有顶点的度数之和自然就是边数的两倍。

### 3. **证明思路**
证明非常简单：考虑图的边集 $E$，每条边都有两个端点，因此每条边在计算度数之和时会被计算两次（一次用于每个端点）。因此，所有顶点的度数之和正好是边数的两倍。

### 4. **例子**
考虑一个简单的无向图，有 4 个顶点（A、B、C、D）和 3 条边：边 AB、边 BC、边 CD。
- 顶点 A 的度数：1（只连接 B）
- 顶点 B 的度数：2（连接 A 和 C）
- 顶点 C 的度数：2（连接 B 和 D）
- 顶点 D 的度数：1（只连接 C）

度数之和：$1 + 2 + 2 + 1 = 6$
边数：3
显然，$6 = 2 \times 3$，符合握手定理。

###  有向图版本

对于有向图，每条弧（有向边）对一个顶点贡献 1 的出度，对另一个顶点贡献 1 的入度，所以：

$$
\sum_{v \in V} \deg^-(v) = \sum_{v \in V} \deg^+(v) = |E|
$$

其中 $ \deg^-(v) $ 是入度，$ \deg^+(v) $ 是出度。

---

###  例子

考虑一个无向图：三角形（3 个顶点，3 条边）。

- 每个顶点的度数 = 2。
- 度数之和 = $ 2 + 2 + 2 = 6 $。
- 边数 = 3，$ 2 \times 3 = 6 $，相等。

再考虑一个图：顶点集 {A, B, C, D}，边为 AB, BC, CD, DA, AC（一个四边形加一条对角线）。

- 度数：A: 3, B: 2, C: 3, D: 2。
- 度数之和 = $ 3 + 2 + 3 + 2 = 10 $。
- 边数 = 5，$ 2 \times 5 = 10 $，符合。
- 奇度顶点：A 和 C，个数为 2（偶数），符合推论。

## 例子
`例`假设有一个无向图 $ G $，顶点集为 $ V = \{v_1, v_2, v_3, v_4, v_5\} $，边集 $ E $ 如下：

$$
E = \{ v_1v_2, v_1v_3, v_2v_3, v_2v_4, v_3v_4, v_4v_5 \}
$$

（这里 $ v_1v_2 $ 表示顶点 $ v_1 $ 和 $ v_2 $ 之间的边）

1. 画出图结构
可以想象或画出来：
- $ v_1 $ 连接 $ v_2, v_3 $
- $ v_2 $ 连接 $ v_1, v_3, v_4 $
- $ v_3 $ 连接 $ v_1, v_2, v_4 $
- $ v_4 $ 连接 $ v_2, v_3, v_5 $
- $ v_5 $ 只连接 $ v_4 $

2. 计算每个顶点的度数
$$
\deg(v_1) = 2 \quad (\text{边 } v_1v_2, v_1v_3)
$$
$$
\deg(v_2) = 3 \quad (\text{边 } v_1v_2, v_2v_3, v_2v_4)
$$
$$
\deg(v_3) = 3 \quad (\text{边 } v_1v_3, v_2v_3, v_3v_4)
$$
$$
\deg(v_4) = 3 \quad (\text{边 } v_2v_4, v_3v_4, v_4v_5)
$$
$$
\deg(v_5) = 1 \quad (\text{边 } v_4v_5)
$$

3. 度数之和
$$
\sum \deg(v) = 2 + 3 + 3 + 3 + 1 = 12
$$

4. 边数
边集 $ E $ 有 6 条边，所以 $ |E| = 6 $。

5. 验证握手定理
$$
\sum \deg(v) = 12, \quad 2|E| = 2 \times 6 = 12
$$
相等，符合握手定理。

6. 奇度顶点检查
- 奇度顶点：$ v_2 $ (3)，$ v_3 $ (3)，$ v_4 $ (3)，$ v_5 $ (1)  
  度数为奇数的顶点：$ \{v_2, v_3, v_4, v_5\} $ 共 4 个（偶数个），符合推论。

7. 可视化结构（文本示意图）
```
v1 —— v2 —— v4 —— v5
|     /     /
|    /     /
|   /     /
v3 ——————
```
更准确的关系：
- $ v_1\text{—}v_2 $
- $ v_1\text{—}v_3 $
- $ v_2\text{—}v_3 $
- $ v_2\text{—}v_4 $
- $ v_3\text{—}v_4 $
- $ v_4\text{—}v_5 $

---

这个例子展示了握手定理的应用：**度数总和是边数的两倍**，并且**奇度顶点个数为偶数**。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：无向图与有向图

下一篇：连通

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