图的顶点度

贡献者：零穹

预备知识　图

　　 [1] 图的某一顶点的度反映了与该点关联的边数，过点的环被定义贡献了 2 度。由于图论的早期主要研究的是无向图，因此顶点度的概念往往专门用于无向图。然而，为了一般化起见我们将它定义在任一图上。

定义 1　顶点度，出度，入度，孤立点

　　设 $G = (V, E, φ)$ 是图， $v \in V$ 。则 $G$ 中与 $v$ 关联的边数加上以该点为端点的环数称为 $v$ 在 $G$ 中的度（degree），记作 $d_{G} (v)$ （或简记为 $d (v)$ ）。 $G$ 中以 $v$ 为起点的有向边数称为 $v$ 在 $G$ 中的出度（out degree），记作 $d_{G}^{+} (v)$ 。 $G$ 中以 $d$ 为终点的有向边数称为 $v$ 在 $G$ 中的入度（in degree），记作 $d_{G}^{-} (v)$ 。度为 $d$ 的点称为 $d$ 度点（d degree vertex）。零度点称为孤立点（isolated vertex），出度等于入度的点称为平衡点（balanced vertex）。

例 1　

　　设 $G$ 是有向图。试证明 $d_{G} (v) = d_{G}^{+} (v) + d_{G}^{-} (v)$ 。

　　 证明：设 $E^{+}$ 是 $G$ 中以 $v$ 为起点的边集， $E^{-}$ 是 $G$ 中以 $v$ 为终点的边集。则 $E_{0} = E^{+} \cap E^{-}$ 是过 $v$ 的环集。由于 $E^{+} ∖ E_{0}, E_{0}, E^{-} ∖ E_{0}$ 是 $E (v)$ 的划分，因此

\begin{matrix} (1) & | E (v) | = | E^{+} ∖ E_{0} | + | E_{0} | + | E^{-} ∖ E_{0} | . \end{matrix}

设

r

是过

v

的环数，因为

| E (v) | = d_{G} (v) - r, | E^{+} ∖ E_{0} | = d_{G}^{+} (v) - r, | E_{0} | = r, | E^{-} ∖ E_{0} | = d_{G}^{-} (v) - r

，所以

\begin{matrix} (2) & d_{G} (v) = d_{G}^{+} (v) + d_{G}^{-} (v) . \end{matrix}

　　图的所有点当中最大的度和最小的度人们习惯用记号 $Δ, δ$ 分别来标记它。

1. 相关定义

定义 2　平衡图

　　每个点都为平衡点的有向图称为平衡有向图（balanced digraph），简称平衡图。

定义 3　最大度，最小度，平均度

　　设 $G$ 是图。则称 $G$ 中顶点度的最大者称为 $G$ 的最大度（maximum degree），记作 $Δ (G)$ ；而 $G$ 中顶点度的最小者称为最小度（minimum degree），记作 $δ (G)$ ；所有点的度之和除于点数称为平均度（average degree），记作 $d (G)$ 。即

\begin{matrix} (3) & \begin{aligned} Δ (G) := max {d_{G} (v) | v \in V}, \\ δ (G) := min {d_{G} (v) | v \in V}, \\ d (G) := \frac{1}{| V (G) |} \sum_{v \in V} d_{G} (v) . \end{aligned} \end{matrix}

习题 1　

　　试证明不等式： $δ (G) \leq d (G) \leq Δ (G)$ 。

　　当所有点具有相同的度时，人们习惯用正则这个词来形容图。当所有点的出度等于入度的时候，人们习惯用平衡形容图。

定义 4　正则

　　若图 $G$ 中的所有点都具有相同的度 $k$ ，则称 $G$ 是 $k$ 正则的（ $k$ regular），简称正则的（regular）。若图 $G$ 的所有点的出度等于入度，则称 $G$ 是平衡的。

　　特别的， $3$ 正则图称为 立方图（cubic graph）。

定理 1　

　　设 $G$ 是任一无环图，则其边集和点集个数具有如下关系：

\begin{matrix} (4) & | E (G) | = \frac{1}{2} d (G) | V (G) | . \end{matrix}

　　 证明：方法 1：对所有的顶点度求和，由于无环图的每一边有两个端点，计算一个点的度计数一次边，所以每条边刚好被计算两次。因此

\begin{matrix} (5) & | E (G) | = \frac{1}{2} \sum_{v \in V} d_{G} (v) = \frac{1}{2} d (G) | V | . \end{matrix}

　　 方法 2：方法 1 具有较大的 “人为” 部分，或者说形式上不严谨，相当于用了一推所谓的人能思考的逻辑，直接给出了式 5 。为了形式严密起见，下面使用更精细的证明。

　　考虑边及其端点组成的偶对 $(e, v)$ 的全体

\begin{matrix} (6) & A = {(e, v) | v \in e, e \in E (G)} . \end{matrix}

对每一边

e

定义

\begin{matrix} (7) & \tilde{e} = {(e, v) | v \in e, v \in V (G)} . \end{matrix}

对每一点

v

定义

\begin{matrix} (8) & \tilde{v} = {(e, v) | v \in e, e \in E (G)} . \end{matrix}

由于

\begin{matrix} (9) & ⋃_{e \in E} \tilde{e} = A = ⋃_{v \in V} \tilde{v}, \end{matrix}

且不同的

e_{1}, e_{2} \in E (G), v_{1}, v_{2} \in V (G)

，

{\tilde{e}}_{1} \cap {\tilde{e}}_{2} = \emptyset, {\tilde{v}}_{1} \cap {\tilde{v}}_{2} = \emptyset

所以（不相交集合的基数和等于它们的并集的基数）

\begin{matrix} (10) & \sum_{e \in E} | \tilde{e} | = \sum_{v \in V} | \tilde{v} | . \end{matrix}

对无环图而言

| \tilde{e} | = 2, \forall e \in E

，又

| \tilde{v} | = d_{G} (v)

，将它们带入上式即得式 5 。

　　 证毕！

推论 1　

　　任意无环图中具有奇数度的顶点的个数总是偶数。

　　 证明： 由定理 1 和式 3 ，

\begin{matrix} (11) & | E | = \frac{1}{2} \sum_{v \in V} d_{G} (v) . \end{matrix}

由于

| E | \in N

。所以

\begin{matrix} (12) & \sum_{v \in V} d_{G} (v) \in 2 N . \end{matrix}

设全体奇数度的点为

O = {v \in V | d_{G} (v) 为奇数}

，那么

\begin{matrix} (13) & \sum_{v \in O} d_{G} (v) \in 2 N \end{matrix}

上式左边是奇数之和，而右边是偶数。而只有偶数个奇数之和才能为偶数，所以

| O |

是偶数。

　　 证毕！

推论 2　

　　设 $G$ 是任意图，则式 4 任成立。

　　 证明： 设 $G$ 中有 $r$ 个环，则 $| E | - r$ 是去掉所有环后得到的图的边数， $d (G) | V (G) | - 2 r$ 则是得到的无环图的度，而点的个数仍是 $| V (G) |$ ，所以得到的无环图的平均度为 $d (G) - \frac{2 r}{V (G)}$ 。由定理 1 ，得

\begin{matrix} (14) & \begin{aligned} | E (G) | - r & = \frac{1}{2} (d (G) - \frac{2 r}{V (G)}) | V (G) |, \\ ⇓ \\ | E (G) | & = \frac{1}{2} d (G) \cdot | V (G) | . \end{aligned} \end{matrix}

　　 证毕！

　　若想使得式 4 对所有的图成立，那么由式 5 可知，若定义一个环算两条关联边，则式 4 对所有的图成立。这也是一些教材的做法，避免混淆的方法是：在特定的情形遵循约定的惯例即可。

[1] ^ 徐俊明.图论及应用. 中国科学技术大学出版社, 合肥.1998.

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。

图的顶点度

定义 1 顶点度，出度，入度，孤立点

例 1

1. 相关定义

定义 2 平衡图

定义 3 最大度，最小度，平均度

习题 1

定义 4 正则

定理 1

推论 1

推论 2

定义 1　顶点度，出度，入度，孤立点

例 1　

定义 2　平衡图

定义 3　最大度，最小度，平均度

习题 1　

定义 4　正则

定理 1　

推论 1　

推论 2　