悬挂顶点 通过使用顶点的度数，我们有两种特殊的顶点类型。度数为一的顶点称为悬挂顶点。示例 在此示例中，顶点“a”和顶点“b”具有连接边“ab”。因此，关于顶点“a”，只有一条边指向顶点“b”，类似地，关于顶点“b”，只有一条边指向顶点“a”。最后，顶点“a”和顶点“b”的度数为一，也称为悬挂顶点。孤立顶点 度数为零的顶点称为孤立顶点。示例 在这里，顶点“a”……阅读更多

集合 S 的划分是一组 n 个不相交子集，例如 P1, P1, ... Pn，满足以下三个条件：Pi 不包含空集。                            [ Pi ≠ {∅}，对于所有 0 < i ≤ n]子集的并集必须等于整个原始集合。                            [ P1 ∪ P2 ∪ ... ∪ Pn = S]任何两个不同集合的交集为空集。            ... 阅读更多

具有小于或等于加权、连通和无向图 $G$ 的每棵可能的生成树的权重的生成树称为最小生成树 (MST)。生成树的权重是分配给生成树的每条边的所有权重的总和。以下是查找最小生成树 (MST) 的两种最流行的算法。克鲁斯卡尔算法 克鲁斯卡尔算法是一种贪婪算法，用于查找连通加权图的最小生成树。它找到该图的一棵树，其中包含每个顶点，并且总权重为……阅读更多

可以使用邻接矩阵的方式表示图。邻接矩阵 邻接矩阵 A[V][V] 是大小为 V × V 的二维数组，其中 $V$ 是无向图中顶点的数量。如果 Vx 和 Vy 之间存在边，则 A[Vx][Vy]=1 且 A[Vy][Vx]=1，否则值为零。对于有向图，如果 Vx 和 Vy 之间存在边，则 A[Vx][Vy]=1，否则值为零。无向图的邻接矩阵 让我们考虑以下无向图并构造邻接矩阵：上述无向图的邻接矩阵……阅读更多

命题 命题是声明语句的集合，它具有真值“真”或真值“假”。命题由命题变量和连接词组成。我们用大写字母（A、B 等）表示命题变量。连接词连接命题变量。谓词 谓词是在某个特定域上定义的一个或多个变量的表达式。通过为变量赋值或量化变量，可以将具有变量的谓词设为命题。以下是谓词的一些示例：令 E(x, y) 表示“x = y”令 X(a, b, c) 表示“a + ……阅读更多

数学可以大致分为两类：连续数学 - 它基于连续数轴或实数。它的特点是，在任意两数之间，几乎总有一组无限的数。例如，连续数学中的函数可以用没有间断的光滑曲线作图。离散数学 - 它涉及不同的值；即在任意两点之间，只有可数的点。例如，如果我们有一组有限的对象，则可以将函数定义为具有这些对象的序偶列表……阅读更多

重言式 重言式是对于其命题变量的每个值始终为真的公式。示例 - 证明 [(A → B) ∧ A] → B 是重言式 真值表如下：A B A → B (A → B) ∧ A [(A → B) ∧ A] → B真 真 真 真 真真 假 假 假 真假 真 真 假 真假 假 真 假 真如我们所见，[(A → B) ∧ A] → B 的每个值都是“真”，它是一个重言式。矛盾 矛盾是对于其命题变量的每个值始终为假的公式。示例 - 证明 (A ∨ B) ∧ [(¬ A) ∧ (¬ B)]……阅读更多

逻辑连接词是一个符号，用于连接两个或多个命题或谓词逻辑，使得结果逻辑仅取决于输入逻辑和所使用的连接词的含义。通常有五个连接词：OR (∨)AND (∧)否定/非 (¬)蕴含/如果-那么 (→)当且仅当 (⇔)。OR (∨) - 如果命题变量 A 或 B 中至少有一个为真，则两个命题 A 和 B 的 OR 运算（写为 A ∨ B）为真。真值表如下：A B A ∨ B真 真 真真 假 真假 真 真假 假 假AND (∧) - 如果命题变量 A 和 B 都为真，则两个命题 A 和 B 的 AND 运算（写为 A ∧ B）为真。……阅读更多

匹配图是图的子图，其中没有边彼此相邻。简单地说，任何两条边之间都不应该有任何公共顶点。匹配 令'G' = (V, E) 为一个图。如果 G 的每个顶点最多与 M 中的一条边关联，则子图称为匹配 M(G)，即 deg(V) ≤ 1 ∀ V ∈ G这意味着在匹配图 M(G) 中，顶点的度数应为 1 或 0，其中边应来自图 G。符号 - M(G)示例 在匹配中，如果 deg(V) = 1，……阅读更多

覆盖图是一个子图，它包含所有顶点或与其他图对应的一些边的子图。包含所有顶点的子图称为线/边覆盖。包含所有边的子图称为顶点覆盖。线覆盖 令G = (V, E) 为一个图。如果G的每个顶点都至少与C中的一条边关联，即deg(V) ≥ 1 ∀ V ∈ G，则子集C(E)称为G的线覆盖，因为每个顶点都通过一条边与另一个顶点连接。因此，它具有最小……阅读更多