小蓝书 17.2

喜欢水文章。

度数

与一个顶点 \(v\) 关联的边的条数称作该顶点的 度 (degree)，记作 \(d(v)\)。特别地，对于边 \((v, v)\)，则每条这样的边要对 \(d(v)\) 产生 \(2\) 的贡献。

对于无向简单图，有 \(d(v) = \left| N(v) \right|\)。

握手定理（又称图论基本定理）：对于任何无向图 \(G = (V, E)\)，有 \(\sum_{v \in V} d(v) = 2 \left| E \right|\)。

推论：在任意图中，度数为奇数的点必然有偶数个。

若 \(d(v) = 0\)，则称 \(v\) 为 孤立点 (isolated vertex)。

若 \(d(v) = 1\)，则称 \(v\) 为 叶节点 (leaf vertex)/悬挂点 (pendant vertex)。

若 \(2 \mid d(v)\)，则称 \(v\) 为 偶点 (even vertex)。

若 \(2 \nmid d(v)\)，则称 \(v\) 为 奇点 (odd vertex)。任意图中奇点的个数是偶数。

若 \(d(v) = \left| V \right| - 1\)，则称 \(v\) 为 支配点 (universal vertex)。

对一张图，所有节点的度数的最小值称为 \(G\) 的 最小度 (minimum degree)，记作 \(\delta (G)\)；最大值称为 最大度 (maximum degree)，记作 \(\Delta (G)\)。即：\(\delta (G) = \min_{v \in G} d(v)\)，\(\Delta (G) = \max_{v \in G} d(v)\)。

在有向图 \(G = (V, E)\) 中，以一个顶点 \(v\) 为起点的边的条数称为该顶点的 出度 (out-degree)，记作 \(d^+(v)\)。以一个顶点 \(v\) 为终点的边的条数称为该节点的 入度 (in-degree)，记作 \(d^-(v)\)。显然 \(d^+(v)+d^-(v)=d(v)\)。

对于任何有向图 \(G = (V, E)\)，有：

\[ \sum_{v \in V} d^+(v) = \sum_{v \in V} d^-(v) = \left| E \right| \]

若对一张无向图 \(G = (V, E)\)，每个顶点的度数都是一个固定的常数 \(k\)，则称 \(G\) 为 \(k\) - 正则图 (\(k\)-regular graph)。

---

上面只是概念，我们来证明几个东西吧。

1. 握手定理：对于任何无向图 \(G = (V, E)\)，有 \(\sum_{v \in V} d(v) = 2 \left| E \right|\)。

   证明：图 \(G\) 中的每条边都贡献两次，总和就是 \(2 |E|\) 。\(\square\)

2. 任意图中奇点的个数是偶数。

   证明：记 \(a = \sum_{v \in V\setminus S} d(v),~b = \sum_{v \in S} d(v)\) ，其中 \(S\) 为奇点构成的子集

   显然 \(a+b = 2|E|\) ，则 \(a = 2|E| - b\) 。因为 \(2|E|\) 为偶数，所以 \(a,b\) 一定同奇偶。\(\square\)

---

题解之后写。