CS70Disc 02A

1. 欧拉巡游与欧拉行走

1(a) 欧拉巡游的存在性

问题：图中是否存在欧拉巡游？如果没有，请给出理由；如果有，请提供一个示例。

欧拉巡游（Eulerian Circuit）是一个遍历图中每条边恰好一次的闭合路径。一个图中存在欧拉巡游的条件是：

所有顶点的度数都是偶数。这是因为在一个巡游中，每次进入一个顶点都需要有一次相应的离开，只有偶数的度数才能保证进入和离开的次数相等。

如果图中所有顶点的度数都是偶数，则该图存在欧拉巡游。

如果图中有一个或多个顶点的度数为奇数，则该图不可能存在欧拉巡游。

解答：不存在欧拉巡游。理由是图中有两个顶点的度数为奇数。

1(b) 欧拉行走的存在性

问题：图中是否存在欧拉行走？欧拉行走是指使用每条边恰好一次的行走。如果没有，请给出理由；如果有，请提供一个示例。

解答：存在欧拉行走。必须选择两个奇数度数的顶点作为起点和终点。比如：1 → 2 → 3 → 4 → 1 → 3 → 6 → 4 → 5 → 2 → 4 → 7 → 5 → 6 → 7，这就是一个欧拉行走的例子（数字表示访问的顶点顺序）。注意，图中总共有14条边。

欧拉行走（Eulerian Path）是一个遍历图中每条边恰好一次的路径，但不同于欧拉巡游，欧拉行走不要求最后回到起点。存在欧拉行走的条件是：

图中恰好有零个或两个顶点的度数为奇数

：

如果有两个奇度数的顶点，欧拉行走的路径会从其中一个奇度数的顶点出发，最终到达另一个奇度数的顶点。

如果所有顶点的度数都是偶数，那么该图不仅存在欧拉行走，也存在欧拉巡游。

1(c) 无向图存在欧拉行走的条件

解答：无向图存在欧拉行走的条件是：图是连通的（除去孤立顶点）且最多有两个奇数度数的顶点。需要注意的是，图中不可能存在只有一个奇数度数的顶点（这由握手引理得出）。欧拉巡游是从同一顶点开始和结束的欧拉行走。

证明：

必要性：假设存在一条欧拉行走，起点为 $ u $，终点为 $ v $（注意 $ u $ 和 $ v $ 不同）。在这条行走中所有顶点都是互相连通的，所有不在此行走中的顶点（如果有）必须是孤立的。因此，图是连通的（除去孤立顶点）。此外，在此行走中的每个顶点的度数配对使用两条边，因此，除了 $ u $ 和 $ v $ 之外，所有其他顶点的度数必须是偶数。

充分性：首先，对于一个没有奇数度数顶点的连通图，我们已经在讲座中证明了存在欧拉巡游，这意味着存在欧拉行走。接下来考虑两个奇数度数顶点的情况。

解决方案 1：取两个奇数度数顶点 $ u $ 和 $ v $，添加一个顶点 $ w $ 与 $ u $ 和 $ v $ 之间分别连接两条边 $(u, w)$ 和 $(w, v)$。得到的新图 $ G' $ 中所有顶点的度数都是偶数（我们将 $ u $ 和 $ v $ 的度数各加一，并引入一个度数为2的顶点），且仍然是连通的。因此，可以在 $ G' $ 上找到一个欧拉巡游。然后，删除使用边 $(u, w)$ 和 $(w, v)$ 的巡游部分。剩下的部分就是在原图 $ G $ 上从 $ u $ 到 $ v $ 的欧拉行走，因为它遍历了原图的每一条边。
解决方案 2：或者，可以构建一个类似于图中介绍的带有拼接的 FindTour 算法。假设 $ G $ 是连通的（除去孤立顶点），且有两个奇数度数的顶点，设为 $ u $ 和 $ v $。首先去掉所有孤立顶点。由于 $ u $ 和 $ v $ 属于同一个连通分量，因此可以找到从 $ u $ 到 $ v $ 的路径。考虑去除路径的边后得到的图。此时，所有顶点的度数都是偶数。因此，对于残余图的每个连通分量，我们都可以找到一个欧拉巡游（注意去除路径的边可能导致图不连通）。观察到，欧拉行走只是一个覆盖所有边的边不相交的行走。我们刚刚做的是将所有边分解为从 $ u $ 到 $ v $ 的路径和一些边不相交的欧拉巡游。路径显然是一个边不相交的行走。然后，给定一个边不相交的行走和一个边不相交的巡游，假设它们共享至少一个公共顶点，可以通过在公共顶点处将巡游添加到行走中来组合成一个边不相交的行走。因此，我们可以将所有边不相交的欧拉巡游与从 $ u $ 到 $ v $ 的路径组合起来，形成从 $ u $ 到 $ v $ 的欧拉行走。

2. 树的着色

2(a) 证明所有至少有两个顶点的树至少有两个叶子

问题：证明所有至少有两个顶点的树至少有两个叶子。叶子定义为度数恰好为1的节点。

解答：对于任意树 $ T = (V, E) $，其中 $ |V| $，设 $ L $ 为叶子集合。我们知道 $ |V| - |L| $ 个顶点是非叶子的。叶子的度数为1，而其他顶点的度数至少为2。此外，已知一个 $ |V| $-顶点的树必须有 $ |V| - 1 $ 条边。根据握手引理：

$ 2|V| - 2 = {v V} (v) = {v L} (v) + _{v V L} (v) |L| + 2(|V| - |L|) = 2|V| - |L| $

这表明 $ |L| $，证明完成。

2(b) 证明所有至少有两个顶点的树都是二分图

问题：证明所有至少有两个顶点的树都是二分图：顶点可以划分为两个组，使得每条边都连接两个组之间的顶点。

解答：使用对顶点数 $ n $ 的归纳法进行证明。

基础情况 $ n = 2 $：具有两个顶点的树只有一条边，可以将两个顶点划分为两个独立的部分，因而是二分图。
归纳假设：假设对于任意 $ k $ 的树都是二分图。
归纳步骤：考虑一棵 $ T = (V, E) $ 的树，具有 $ k + 1 $ 个顶点。我们知道每棵树至少有两个叶子（前一部分），因此去掉一个叶子 $ u $ 和与之连接的边 $ e $。结果图 $ T - u $ 是一棵具有 $ k $ 个顶点的树，根据归纳假设，它是一个二分图，因此存在一个顶点的划分 $ V = R L $，使得没有边连接两个 $ L $ 中的顶点或两个 $ R $ 中的顶点。

现在当我们将 $ u $ 添加回图中。如果边 $ e $ 将 $ u $ 与 $ L $ 中的一个顶点连接，那么我们设 $ L' = L $ 和 $ R' = R { u } $。另一方面，如果边 $ e $ 将 $ u $ 与 $ R $ 中的一个顶点连接，那么我们设 $ L' = L { u } $ 和 $ R' = R $。$ L' $ 和 $ R' $ 给出了所需的划分，证明 $ T $ 是二分图。归纳步骤完成，因此通过归纳我们证明了所有至少有两个顶点的树都是二分图。

3. 度序列

问题：度序列是图的顶点度数的序列，按降序排列，重复计数。例如，以下图的度序列为 (3, 2, 2, 2)。

对于以下每个部分，判断是否存在简单无向图 $ G $（即没有自环和多重边）具有给定的度序列。请证明您的主张。

(a) $(3, 3, 2, 2)$

解答：存在

构造如下图：

顶点 $ A $ 和 $ B $ 的度数为 3。
顶点 $ C $ 和 $ D $ 的度数为 2。

连接方式：

$ A $ 连接 $ B, C, D $
$ B $ 连接 $ A, C, D $
$ C $ 连接 $ A, B $
$ D $ 连接 $ A, B $

这样，得到的图的度序列为 $(3, 3, 2, 2)$。

(b) $(3, 2, 2, 2, 2, 1, 1)$

解答：不可能

对于任何图 $ G $，具有奇数度的顶点数量必须为偶数（由手握引理可知，所有顶点的度数之和是边数的两倍，因此总和为偶数）。在该度序列中，有 3 个奇数度的顶点（3, 1, 1），因此不可能构成一个简单无向图。

(c) $(6, 2, 2, 2)$

解答：不可能

给定的度序列包含一个度数为 6 的顶点，但图中总共有 4 个顶点。根据图的性质，任何顶点的度数最多只能等于总顶点数减 1（即 3），所以不存在度数为 6 的顶点。

(d) $(4, 4, 3, 2, 1)$

解答：不可能

在此度序列中，有两个度数为 4 的顶点。根据图的性质，度数为 4 的顶点需要与其他 4 个顶点连接，但这里只有 5 个顶点（包含两个度数为 4 的顶点）。这意味着一个度数为 4 的顶点必须与所有其他顶点相连，而这会导致不能满足另一顶点的度数要求，尤其是度数为 1 的顶点，无法实现。因此，这个度序列不可能构成一个简单无向图。