(涵盖第 8、9、11 个讲义)

LN8-11 图论

“一笔走完” 问题

• 对于一张由 V vertex/vertices(点) 和 E edge(桥) 组成的图，如果想要 “一笔走完”，也就是恰好经过每个桥一次 (称为欧拉路径)，每个中途经过的点都需要连着偶数个桥（指向该点和指离该点），而只有路径的头尾可以有奇数个桥 (负责一笔的开始和结束)。所以，对于一个有 n 个桥的图，如果想要经过每个桥恰好一次，最多只能有两个点有奇数桥。
• 下图为柯尼斯堡七桥问题，由于所有点都连着奇数桥，所以是不可能的。

欧拉定理：对于单体连续图，只存在小于等于两个“奇桥点”，那么图有欧拉路径。

• 如果一个欧拉路径不是只能 “原路返回”，而是首尾相连的话，就叫做欧拉回路。

欧拉定理 (续)：对于单体连续图，所有点都有偶数个桥，那么图有欧拉回路。

• 你可以这么理解：所有欧拉路径经过的点中，只有开始/结尾点是可以有奇数个桥的。如果没有头尾，那所有点都得是偶数桥的。而一个没有头尾的欧拉路径就是欧拉回路。

图论基础

• 度数 deg(v)：图中任意点 v 指出去的桥数 (自指桥算两次)。比如上面那张“柯尼斯堡七桥”图片中最左边那个点的度数为 5
• 简单图 (simple graph)：两点间不存在多桥、桥没有方向、桥不指向自己的图，也就是所有点的度数 ≤ 2
• multigraph：桥没有方向，但可以有多桥或自指桥
• directed graph：桥有方向，也可以有多桥或自指桥
• 相邻集 N(v)：点 v 的相邻点组成的集合
• degree sequence：所有点的桥数组成的点坐标 “(deg(a), deg(b), …)”
• 同构图：通过扭曲、改变视角、改变名字可以互相等效的图，同构图一定有相同的 degree sequence。
• 树图：没有循环，也没有 deg()>2 的点的单体图。其 “叶” 是所有 deg()=1 的点。

握手定理：对于任意种类的单体连续图，$2E = \sum_{v∈V} deg(v)$。所以：

• 度数和不为偶数的图不存在
• 永远只可能存在偶数个“奇桥点”

匹配与完全图

一般把简单图的 vertex 数叫做 n，edge 数叫做 m，某种匹配叫做 M

• Matching (匹配)：桥互不共享点，所有点度数小于等于 1 的图。
• Maximum matching (最大匹配)：桥数最多的匹配。 Berge 引理：一个匹配 M 是最大匹配 ⇔ 图中不存在相对 M 的增广路 (augmenting path)
• M() perfect matching (完美匹配)：n 必为偶数，覆盖全部点的匹配，所有点度数为 1。
• K_n complete graph (完全图)：每个点与所有其它点都有桥，所有点度数为 n-1 的图。

某个 “偶数完全图” 的完美配对数，也就是 M(K_2n) 是多少？第一个点有 2n-1 种配对可能，配对后给第三个点留下 2n-3 种配对可能，以此类推直到最后两点只有唯一的配对方式：$$(2n-1)!!\ =\prod_{ß=0}^{ß=n-1}(2n-1-2ß)={(2n)!\over 2^nn!}$$

二分图和霍尔婚配定理

二分图 Bipartite K_{m, n}就是将点分为数量为 m, n 的两个组，组内不存在桥。

二分图中的欧拉定理：

• K_{m, n}有欧拉回路 ⇔ m 和 n 都是偶数
• K_{m, n}有欧拉路径⇔ m 和 n 都是偶数 or m 和 n 分别是 2 和奇数 or m = n = 1

Hall 定理 (判断二分图能否完美匹配)

对二分图 G=(X,Y,E)，存在覆盖 X 的完美匹配 ⇔ 对任意 S⊆X，有 |N(S)| ≥ |S|。即 X 的所有非空子集包含的点的桥数和大于每个子集的大小。

• 证明：核查所有子集
• 证伪：给出一个反例子集 S 使 |N(S)|<|S|

例： U = {u1, u2, u3, u4}, V = {v1, v2, v3, v4}; N(u1) = {v1, v2}, N(u2) = {v1, v3}, N(u3) = {v2, v4}, N(u4) = {v3, v4}.

• |S|=1：显然 |N(S)| = 2 ≥ 1
• |S|=2：例如 |N({u1, u2})| = 3；|N({u3, u4})| = 3，其他二元子集也至少包含 2 个顶点
• |S|=3：如 |N({u1, u2, u3})| = 4，其它三元子集同理
• |S|=4：N(U)=V，|N(U)|=4 ≥ 4 证毕，存在完美配对。

染色问题

染色问题需要相邻的点有不同颜色；χ(图) = k 代表某个图在染色问题下最少需要 k 种颜色。文字记作 k-colorable (k-染)：

• 比如简单环 C_n (∀ v, deg(v) = 2)，称为一个循环，χ(奇循环) = 3、χ(偶循环) = 2。
• 又比如任意的完全图 K_n，χ(K_n) = n；所以说任何图的染色都大于等于其最大子完全图大小： $χ(G) ≥ \omega(G)$。特殊的：**所有区间图 interval graph 的染色解等于其最大子完全图大小相等。**比如下图左边是航班到达的区间图，画成 “航班冲突图” 之后最大完全图为 K₃，所以需要的最少登机口为 χ(K₃) = n。

• 任何二分图都不存在奇循环，也就一定可以 2-染。任意有奇循环的图显然不可 2-染。
• 所有地图都是 4-染。(把地图每个国家想象成点，接壤区域想象成桥即可)

平面问题

平面图的性质：在纸面上画出来时，可以做到不让任何两个桥相交。

• 三个点以上的完全图一定不是平面图。（如下图所示，桥一定会重叠）

平面欧拉公式

• ”面“ 是指相邻点连接形成的连续空间，分为内空间和外空间。内空间是封闭的，是至少三个桥围成的连续区域；外空间是不封闭的所有点外部的区域。比如 f(K₄)=5。
• 欧拉公式(平面)：如果一个连续单体平面图有 n 个点, m 个桥, and f 个面，那么：n – m + f = 2。

简单图的边长推论

因为简单图中没有两点间双桥，每个面的 “边长“ 至少是 3 (个桥)，而每个桥两边的空间如果被三个桥围起来才是面，所以每个桥最多提供了 2 个“边长”，因此知道：2m ≥ 3f。

• 你可以这么理解：”每个桥最多作为 2 个边长 (LHS)，每个面最少边长为 3 (RHS)“

结合平面欧拉公式，我们得到欧拉引理：m ≤ 3n-6；再套用握手定理的变形 ( 平均度数 = ∑deg(v)/n = 2m/n)，我们又可以知道：$\bar{d} = {2m\over n} ≤ {6n-12\over n} = 6- {12\over n}$，无论 n 的值是多少，简单平面图的平均度数小于 6，也就是至少有一个点的度数小于等于 5。

• 从这里可以证明所有平面图均可 6-染。(数学归纳法) 图 G 中一定存在某点 v 有最多 5 个桥，假设 G-v 可以 6-染，很容易证明 G 也可以 6-染。

• CSC3001