离散数学复习ing

图的同构

Find out whether G and H are isomorphic. No matter what the judgment is, please give your explanation and argument.

两个图 $ G $ 和 $ H $ 是同构的，如果存在一个顶点到顶点的一一映射（即函数 $ f $），使得图 $ G $ 中的边与图 $ H $ 中的边在映射下对应，即如果 $ u $ 和 $ v $ 在图 $ G $ 中相连，则它们在图 $ H $ 中的映射点 $ f(u) $ 和 $ f(v) $ 也要相连。

度数分析

度数（degree） 是一个图中一个顶点的邻居数量。图同构要求度数相同的顶点映射到度数相同的顶点上。

度数（deg）信息用于帮助确定映射关系：

$ (u_3) = (v_2) = 2 $，所以 $ f(u_3) = v_2 $ 是唯一的选择。
$ (u_1) = (u_5) = (v_1) = (v_4) = 3 $，因此 $ f(u_1) $ 和 $ f(u_5) $ 之间的映射关系必须是 $ f(u_1) = v_1 $ 和 $ f(u_5) = v_4 $，或者反过来 $ f(u_1) = v_4 $ 和 $ f(u_5) = v_1 $。
$ (u_2) = (u_4) = (v_3) = (v_5) = 4 $，因此 $ f(u_2) $ 和 $ f(u_4) $ 的映射关系必须是 $ f(u_2) = v_3 $ 和 $ f(u_4) = v_5 $，或者反过来 $ f(u_2) = v_5 $ 和 $ f(u_4) = v_3 $。

尝试不同的映射方式

根据度数相同的条件，我们尝试了一个可能的映射：
$ f(u_3) = v_2 $，$ f(u_1) = v_1 $，$ f(u_5) = v_4 $，$ f(u_2) = v_3 $，$ f(u_4) = v_5 $。
如果我们将这些映射应用到图 $ G $ 和 $ H $ 中，且边的连接关系也保持一致（即对应的顶点之间有边连接），那么我们可以得出结论：图 $ G $ 和 $ H $ 是同构的。

证明题

证明以下命题是一个重言式（tautology）： $ (x)(P(x) Q(x)) ((x) P(x) (x) Q(x)) $

解答与解释：

初始表达式： 我们要证明的是： $ (x)(P(x) Q(x)) ((x) P(x) (x) Q(x)) $
逻辑等价变换： 首先，使用逻辑公式将命题进行变形和简化。
- 步骤 1: 使用命题逻辑的等价式，将 $ P(x) Q(x) $ 替换为 $ P(x) Q(x) $：$ (x)(P(x) Q(x)) (x)(P(x) Q(x)) $
- 步骤 2: 将 $ x P(x) x Q(x) $ 转换为 $ x P(x) x Q(x) $，并且应用 $ x P(x) x P(x) $：$ (x) P(x) (x) Q(x) x P(x) x Q(x) x P(x) x Q(x) $
- 步骤 3: 然后，整个公式变为： $ x (P(x) Q(x)) (x P(x) x Q(x)) $
进一步简化：
- 步骤 4: $ x (P(x) Q(x)) $ 等价于 $ x (P(x) Q(x)) $，所以公式变为：$ x (P(x) Q(x)) x Q(x) x P(x) $
- 步骤 5: $ x P(x) $ 等价于 $ x P(x) $，所以我们得到：$ x ((P(x) Q(x)) Q(x)) x P(x) $
- 步骤 6: 可以进一步合并项 $ (P(x) Q(x)) Q(x) $ 为 $ P(x) Q(x) $，所以公式变为：$ x (P(x) Q(x)) x P(x) $
最终化简：
- 步骤 7: 由于 $ x P(x) $ 和 $ x P(x) $ 互为对立项，最终得出： $ x P(x) x Q(x) x P(x) $
- 该公式显然是恒真的（1），因为 $ x P(x) $ 和 $ x P(x) $ 互为补集，不论 $ x P(x) $ 是否成立，都会保证该公式成立。

推理题

Construct an argument using rules of inference to show that the hypotheses:

“Ellen, a student in this class, owns a red convertible. Everyone who owns a red convertible has gotten at least one speeding ticket.”

imply the conclusion “someone in this class has gotten a speeding ticket.”

使用推理规则构建一个论证，证明以下假设： “Ellen，这个班级的一名学生，拥有一辆红色敞篷车。每个拥有红色敞篷车的人至少收到过一次超速罚单。” 推出结论：“这个班级中的某人曾经收到过超速罚单。”

解析

给定以下命题和符号：

$ S(x) $: $ x $ 是这个班级的学生。
$ R(x) $: $ x $ 拥有一辆红色敞篷车。
$ O(x, y) $: $ x $ 拥有 $ y $。
$ T(x) $: $ x $ 收到了一张超速罚单。

假设：

$ H1 $: $ S() y (R(y) O(, y)) $（Ellen 是班级中的学生，并且 Ellen 拥有一辆红色敞篷车）
$ H2 $: $ x (y (O(x, y) R(y)) z (T(z) O(x, z))) $（每个拥有红色敞篷车的人至少会收到一次超速罚单）
结论：$ C: x y (S(x) T(y) O(x, y)) $（班级中至少有一个人收到了超速罚单）

证明：

1. 对 $ H2 $ 使用普遍化实例化（Universal Instantiation，UI）

选择 $ x = $。
由 $ H2 $ 可得： $ z (T(z) O(, z)) $ 这意味着 Ellen 至少收到了一个超速罚单。

2. 对 $ H1 $ 使用存在量化消除（Existential Instantiation，EI）

从 $ H1 $ 可得： $ S() y (R(y) O(, y)) $ 即 Ellen 是班级的学生，并且她拥有一辆红色敞篷车。

3. 结合 $ H1 $ 和 $ H2 $ 的推论

从 $ H1 $ 和 $ H2 $ 的组合，我们可以得出结论： $ z (T(z) O(, z)) $ 这表示 Ellen 收到了一个超速罚单，并且该罚单与她所拥有的红色敞篷车相关。

4. 得出结论：

我们已经证明了班级中至少有一个人（Ellen）收到了超速罚单。
因此，得出结论： $ x y (S(x) T(y) O(x, y)) $ 即班级中至少有一个人（如 Ellen）曾经收到过超速罚单。

平面图

Prove that Petersen graph is non-planar graphs.

The sub-graph H of the Petersen shown in Figure (b) obtained by deleting 3 and the three edges that have 3 as an endpoint,

is homeomorphic to K3,3.

Hence, the Petersen graph is non-planar.

图 (b) 中的子图 $ H $ 通过删除顶点 3 及与 3 相连接的三条边得到，且该子图与 $ K_{3,3} $ 同胚。
因此，Petersen 图是非平面图。

图模型

如果六个站点的位置如表格所示，且当两个站点之间的距离小于 180 英里时，它们不能使用相同的频道，那么需要多少个不同的频道？

这个调度问题可以通过图模型来解决，其中顶点表示站点，两个顶点之间如果它们的距离小于 180 英里，就在它们之间画一条边。

建图完成后进行图着色，图的色数是 3。

容斥原理

问题：

在20个华南理工大学（SCUT）学生中，8人是2010年亚运会志愿者（VAG），6人是2010年亚残运会志愿者（VAPG），且有2人既是亚运会志愿者又是亚残运会志愿者。问：有多少人既不是亚运会志愿者也不是亚残运会志愿者？

解答：

设 $ W $ 是亚运会志愿者（VAG）的集合，设 $ S $ 是亚残运会志愿者（VAPG）的集合。
- $ |W| = 8 $（亚运会志愿者的数量）
- $ |S| = 6 $（亚残运会志愿者的数量）
- $ |W S| = 2 $（既是亚运会志愿者又是亚残运会志愿者的人数）
需要求的是既不是亚运会志愿者也不是亚残运会志愿者的人数，即求 $ |W^c S^c| $，这表示的是集合 $ W $ 和 $ S $ 的补集交集的大小。
根据集合的补集公式： $ |W^c S^c| = 20 - |W S| $ 其中，$ |W S| $ 是 $ W $ 和 $ S $ 的并集大小，表示至少是亚运会志愿者或者亚残运会志愿者的人数。
使用并集公式： $ |W S| = |W| + |S| - |W S| $ 将已知数值代入： $ |W S| = 8 + 6 - 2 = 12 $
代入补集公式计算： $ |W^c S^c| = 20 - 12 = 8 $

结论：

因此，有 8 个人既不是亚运会志愿者也不是亚残运会志愿者。

假言推理

问题：

如果一个人是大学生，那么他要么是文科生，要么是理科生。有些大学生是优秀的学生。John 不是文科生，但他是优秀的学生。John 是大学生。请使用推理规则证明 John 是理科生。

•If a person is a university student, he is either a liberal-arts student or a science student.

•Some university student is an outstanding student. John is not a liberal-arts student, but he is an outstanding student.

• John is a university student.

•Use rules of inference to show that John is a science student.

解答：

给定条件：

$ x (P(x) (Q(x) S(x))) $
—— 如果 $ x $ 是大学生，则 $ x $ 要么是文科生，要么是理科生。
$ x (P(x) T(x)) $
—— 存在一些大学生是优秀的学生。
$ Q(c) $
—— John 不是文科生。
$ T(c) $
—— John 是优秀的学生。
$ P(c) $
—— John 是大学生。

目标：

证明 John 是理科生，即 $ S(c) $。

推理过程：

前提 (1)： $ x (P(x) (Q(x) S(x))) $
这表示每个大学生要么是文科生，要么是理科生。
应用实例化 (UI)：
由于 John 是大学生 ($ P(c) $)，根据前提 (1)，我们可以得到：$ P(c) (Q(c) S(c)) $ 即 John 要么是文科生，要么是理科生。
前提 (3)：$ Q(c) $
由于 John 不是文科生，因此 $ Q(c) $ 为假。
根据假言推理：
如果 $ P(c) $ 为真且 $ Q(c) $ 为假，则根据 $ P(c) (Q(c) S(c)) $，我们可以推得 $ S(c) $ 为真。
即 John 是理科生。
结论：
因此，我们得出结论：John 是理科生，即 $ S(c) $。

结论：

John 是理科生。

连通性

问题：

题目：
有 $ n $ 个城市，通过 $ k $ 条道路连接。每条道路只与两座城市相连，可以视为图中的一条边。已知道路和城市满足以下条件：$ k > $，问题是是否所有城市都可以通过这些道路互相到达。换句话说，给定的图 $ G $ 是否是连通的？

解答：

假设图 $ G $ 包含 $ n $ 个城市和 $ k $ 条道路，图的形式是简单图 $ G = (V, E) $，其中 $ |V| = n $，表示城市的数量，$ |E| = k $，表示道路的数量。

我们需要证明当 $ k > $ 时，图 $ G $ 是连通的。

1. 假设 $ G $ 是非连通的：

假设图 $ G $ 不是连通的，那么图 $ G $ 至少有两个连通分量，设这两个连通分量分别为 $ G_1 = (V_1, E_1) $ 和 $ G_2 = (V_2, E_2) $，其中 $ |V_1| = n_1 $，$ |V_2| = n_2 $，且 $ n_1 + n_2 = n $。

由于 $ G $ 是简单图，所以：

图 $ G_1 $ 中的边数最多为 $ $（即完全图的边数）。
图 $ G_2 $ 中的边数最多为 $ $（即完全图的边数）。

因此，总的边数 $ k $ 满足： $ k + $

2. 利用 $ n_1 + n_2 = n $ 推导：

由于 $ n_1 n - 1 $ 和 $ n_2 n - 1 $，我们可以将边数的上限进一步推导：$ k $

3. 与给定条件进行对比：

根据题目条件，已知 $ k > $，但是根据假设 $ G $ 是非连通的，我们得到了 $ k $。这显然与已知条件 $ k > $ 矛盾。

4. 结论：

由于假设 $ G $ 非连通会导致矛盾，因此 $ G $ 必须是连通的。这意味着，所有的城市都可以通过道路互相到达。

解释：

非连通图的矛盾：通过假设 $ G $ 是非连通的并将其分为两个连通分量 $ G_1 $ 和 $ G_2 $，我们推导出了一个上限 $ k $，而与题目给定的条件 $ k > $ 矛盾。因此，图 $ G $ 不能是非连通的，必须是连通的。
连通图：证明了在给定的条件下，图 $ G $ 一定是连通的，从而确保了每个城市都可以通过道路到达其他城市。