离散数学复习ing（2）
离散数学复习ing（2）
欧拉路径
问题：
题目： 给定一个图 $ G $，其中顶点 $ a $ 和 $ b $ 的度数为奇数，其他顶点的度数为偶数。请问该图是否可以通过一笔画出来？使用欧拉路径定理，证明该图是否可以画出。
证明：
欧拉路径定理：
定理 2：一个连通图如果存在欧拉路径但不存在欧拉回路，则当且仅当它有恰好两个奇度顶点。
1. 定义欧拉路径和欧拉回路：
- 欧拉路径：一个经过图中每条边一次且仅一次的路径。
- 欧拉回路：一个经过图中每条边一次且仅一次的回路，即起点和终点是同一个顶点。
2. 欧拉路径的条件：
根据定理，一个连通图有欧拉路径，当且仅当该图有恰好两个奇度顶点，其他顶点的度数为偶数。
3. 分析给定图的条件：
- 顶点 $ a $ 和 $ b $ 的度数是奇数。
- 其他顶点的度数是偶数。
根据定理 2，图 $ G $ 有恰好两个奇度顶点，因此，图 $ G $ 满足有欧拉路径的条件。
4. 连通性：
题目假设图 $ G $ 是连通的。因此，图 $ G $ 满足欧拉路径的条件。
5. 结论：
由于图 $ G $ 满足欧拉路径的条件（恰好两个奇度顶点且图是连通的），因此可以通过一笔画出来，即图 $ G $ 可以绘制为一条欧拉路径。
解释：
- 奇度顶点：一个顶点的度数为奇数时，表示这个顶点必须在路径的开始或结束时出现。
- 偶度顶点：一个顶点的度数为偶数时，表示该顶点在欧拉路径中出现的次数是偶数次，即可以作为路径的中间经过点。
因此，图 $ G $ 可以通过一笔画出来，因为它满足欧拉路径存在的充分条件：恰好两个奇度顶点且图是连通的。
平面图
问题：
题目： 证明 $ K_5 $ 和 $ K_{3,3} $ 是非平面图。
证明：
证明 (1)：证明 $ K_5 $ 非平面
假设 $ K_5 $ 是平面图： 根据欧拉公式，对于一个平面图 $ r = e - v + 2 $，其中：
- $ e $ 是图中的边数，
- $ v $ 是图中的顶点数，
- $ r $ 是平面图中的区域数。
考虑区域的度数： 平面图中每个区域的度数都大于等于 3（每个区域至少有 3 条边）。根据这个条件，可以得到： $ r $ 这是因为每条边被两个区域共享，且每个区域至少有 3 条边。
代入欧拉公式： 代入欧拉公式 $ r = e - v + 2 $ 得到： $ e - v + 2 $ 通过移项得到： $ 2e (e - v + 2) $ 展开简化： $ 2e 3e - 3v + 6 $ $ 0 e - 3v + 6 $ $ e 3v - 6 $ 这是平面图的边数与顶点数之间的关系。
对于 $ K_5 $ 的具体计算： 对于 $ K_5 \(，它有 5 个顶点和 10 条边。代入公式：\) e = 10, v = 5 $ 显然，10 不满足 $ e 3v - 6 $，因为 $ 3 - 6 = 9 $，而 $ e = 10 \(。 由于不满足这个不等式，\) K_5 $ 不能是平面图，因此 $ K_5 $ 是非平面图。
证明 (2)：证明 $ K_{3,3} $ 非平面
假设 $ K_{3,3} $ 是平面图： 同样使用欧拉公式 $ r = e - v + 2 $，其中：
- $ e = 9 \(（\) K_{3,3} $ 有 9 条边），
- $ v = 6 \(（\) K_{3,3} $ 有 6 个顶点）。
考虑区域的度数： 因为平面图中的每个区域至少有 3 条边，类似地我们得到： $ r $
代入欧拉公式： 代入欧拉公式 $ r = e - v + 2 $ 得到： $ e - v + 2 $ 代入 $ e = 9 $ 和 $ v = 6 $ 得到： $ - 6 + 2 $ $ 6 $ 这个不等式显然不成立，因此 $ K_{3,3} $ 不能是平面图。
另一种证明方法： $ K_{3,3} $ 是一个二部图，其中每个部分有 3 个顶点，且每个顶点与另一个部分的所有顶点都有边相连。根据著名的 Kuratowski 定理，如果一个图包含子图 $ K_5 $ 或 $ K_{3,3} \(，则该图是非平面图。因此，\) K_{3,3} $ 本身就是非平面图。
结论：
- $ K_5 $ 是非平面图，因为它的边数不满足平面图的限制条件。
- $ K_{3,3} $ 是非平面图，且可以通过 $ K_{3,3} $ 自身的性质或使用 Kuratowski 定理直接证明。
因此，两个图 $ K_5 $ 和 $ K_{3,3} $ 都是非平面图。
鸽巢定理
问题：
题目： 证明在任意六个人中，总有三个人要么彼此认识，要么彼此不认识。
证明：
我们将这个问题转化为图论中的问题。假设有六个人，我们用六个顶点来表示这六个人。如果两个人彼此认识，则在对应的两个顶点之间画一条红色边；如果两个人不认识，则在对应的两个顶点之间画一条蓝色边。我们需要证明，在这样的图 $ K_6 $ 中，必定存在一个红色三角形（即三个人彼此认识）或者一个蓝色三角形（即三个人彼此不认识）。
1. 转化为图论问题：
- 六个人可以用六个顶点表示，图 $ K_6 $ 表示六个人之间的关系。
- 每一对顶点之间的边要么是红色（表示两个人认识），要么是蓝色（表示两个人不认识）。
我们的目标是证明在图 $ K_6 $ 中，必定存在一个红色三角形（即三个人彼此认识）或蓝色三角形（即三个人彼此不认识）。
2. 假设：
假设六个人分别为 $ u, v_1, v_2, v_3, v_4, v_5 $。
我们考虑顶点 $ u $，它与其他五个顶点 $ v_1, v_2, v_3, v_4, v_5 $ 各有一条边连接。
3. 应用抽屉原理：
根据抽屉原理，顶点 $ u $ 与五个顶点的五条边中，至少有三条边是相同颜色的。也就是说，这三条边要么都是红色（表示 $ u $ 与这三个人彼此认识），要么都是蓝色（表示 $ u $ 与这三个人彼此不认识）。
假设 $ u $ 与 $ v_1, v_2, v_5 $ 三个人之间的边是红色的，即 $ u $ 与 $ v_1, v_2, v_5 $ 之间三条边都是红色，这意味着 $ u $ 和这三个人彼此认识。
4. 考虑其他边的颜色：
现在，我们来看 $ v_1, v_2, v_5 $ 三个顶点之间的关系，即考虑以下三条边的颜色：
- $ (v_1, v_2) $
- $ (v_1, v_5) $
- $ (v_2, v_5) $
如果其中的任何一条边是红色，那么我们就找到了一个红色三角形（例如，如果 $ (v_1, v_2) $ 是红色，那么 $ v_1, v_2, u $ 就形成了一个红色三角形）。如果这三条边都是蓝色，那么 $ v_1, v_2, v_5 $ 就形成了一个蓝色三角形（即这三个人彼此不认识）。
5. 结论：
无论 $ (v_1, v_2) $, $ (v_1, v_5) $, $ (v_2, v_5) $ 中哪条边的颜色是红色或蓝色，最终都会找到一个红色三角形或者蓝色三角形。因此，我们证明了，在任意六个人中，总有三个人彼此认识或三个人彼此不认识。
结论：
在任意六个人中，必定存在三个彼此认识的人或者三个彼此不认识的人。
图同构
问题： 给定两个图 $ G $ 和 $ H $，判断它们是否同构。如果它们是同构的，请提供一个同构函数，将图 $ G $ 的顶点映射到图 $ H $ 的顶点。
解答： 图 $ G $ 和 $ H $ 是 同构 的。这意味着在 $ G $ 和 $ H $ 之间存在一个一一对应的顶点映射关系，且这个映射关系保持了邻接关系（即，$ G $ 中的两个顶点如果相邻，那么它们在 $ H $ 中的对应顶点也相邻，反之亦然）。
它们之间的同构关系为：
- $ f(u_1) = v_6 $
- $ f(u_2) = v_3 $
- $ f(u_3) = v_4 $
- $ f(u_4) = v_5 $
- $ f(u_5) = v_1 $
- $ f(u_6) = v_2 $
解释： 为了确认 $ G $ 和 $ H $ 是同构的，我们需要验证在应用映射函数 $ f $ 后，图 $ G $ 中的顶点连接（边）与图 $ H $ 中的顶点连接相匹配。
- 我们检查图中顶点之间的邻接关系，并确保在 $ G $ 中相邻的顶点在 $ H $ 中的对应顶点也相邻。
- 例如，如果 $ u_1 $ 和 $ u_2 $ 在 $ G $ 中是相邻的，那么 $ v_6 $ 和 $ v_3 $ 在 $ H $ 中必须是相邻的，按照同构函数 $ f $。
- 对于图中所有的邻接顶点对，映射后的对应顶点对也必须满足相邻的条件。
由于这个同构映射保持了邻接结构，图 $ G $ 和 $ H $ 确实是同构的。
