最后更新: 2025-01-21 16:49 查看: 206 次纠错评论(0) 课件开VIP

握手定理

## 握手定理
定理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$ 。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：点的度数

下一篇：完全图

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