3.图论(II) - Shane Lorien

由于看的课的中文是机翻，下面对等词语在可能混淆的情形下使用英文。由于画图的麻烦性，并没有画图，建议自行作画。

途径(walk) 是由由边链接的顶点的序列，允许顶点和边的重复。经过的边的数量称为路径长度。 路径(path) 不允许边或顶点的重复的。

Lemma 1 path的存在性

如果存在从节点到的那么就存在到的。

[!证明] 存在从到，根据良序定理，存在一个长度最小的。下面证明这就是一条。如果长度等于，显然成立。如果长度：使用反证法，如果不是，那么就有重复的顶点，设，则路径是一条更短的路(砍掉了的部分)。这就出现了矛盾。所以成立。

连通性 ：如果有一条从到的，那么他们连通。如果一个图的每个顶点都连通，那么称该图连通，或称为连通图。

闭途径(closed walk) 是指一个起点和终点相同的。 环(cycle) 是指不重复经过顶点的。

树：连通无环图。叶：树中为的节点。

Lemma 2 树的连通子图还是树

[!证明] 反证法。子图已经连通，假设子图有环，则原图有环，则不是树，矛盾，故子图无环(显然如此)。

Lemma 3 树的边数

节点为的树有条边。

为证明此，先说明叶子的存在性。

证明：在任何的树中，至少存在两个叶子节点

证明步骤：

取最长路径：

在树中，由于节点数有限且无环，一定存在一条最长路径（Path，点不重复），我们将其记为。
考察端点：

考虑与起点相连的节点。除了路径上的邻居之外，还能有其他的邻居吗？
- 情况 A： 如果与路径之外的某个点相连，那么我们可以把路径延长为。这与是“最长路径”的假设矛盾。
- 情况 B： 如果与路径上已有的某个点（比如，其中）相连，由于和之间已经有一条路径，这条新边会形成一个环。这与树“无环”的定义矛盾。
得出结论：

因此，只能与这一个点相连。也就是说， 的度数 。
同理推导：

同样的逻辑也适用于路径的另一个端点，它的度数也必然为 1。

结果： 路径的两个端点和都是叶子节点。证毕。

[!证明Lemma 3] 归纳法。时显然成立。若时成立，时：删掉一个叶子，那么创造了一个连通子图，根据这就是的树，那么满足有条边，加上这个叶子，那么也只会加上一条边，那么此时就恰好有条边。

生成树(Spanning tree,ST) ：一个连通图的子图，该子图是一个包含所有节点的树。生成树是包含所有顶点最小连通子图的解。

Theorem 每个连通图都有生成树

[!证明] 假设有一个连通图没有生成树。让作为满足是的一个连通子图，拥有的全部顶点的子图中有最小边数的子图。那么根据假设，有环，那么删去环上的一条边，边数变短了，但仍然是连通图，这与边数最小矛盾，所以原命题成立。

仍然连通的说明：考虑任意两个顶点，若连接他们的不包含删去的边，那么当然不会破坏他们的连通性；反之，由环的定义，除了边之外，的顶点和之间一定存在另一条，那么之间就存在路线，可见仍然是连通的。

最小生成树(MST) ：对于有权重的连通图，权值和最小的生成树。

Kruskal 算法（加边法）

每次选择权重最小的边，只要不形成圈就行，直到变成生成树。就变成了最小生成树。

[!Lemma] ，让为包含了按照算法选择的其前条边的集合。则存在最小生成树，使得。

证明：使用归纳法。归纳假设即命题。

时，是空集，显然成立。

设成立，设是第步添加的边，让表示已选择的前条边，根据归纳假设，存在最小生成树使得。

如果，那么显然成立，反之，由于是生成树，顶点已连通，再加边则会生成环，由和连接其顶点的路径组成。由于按照算法选无环，这个环上必定有不属于的边。由于算法先选再选，可知。构造新树，为删去加上，此时图依然连通无环，故也是生成树，且，因为已经是最小生成树，只能取等，所以也是最小生成树。而显然这个新的。成立。

综合以上，归纳得证原命题成立。