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

最小生成树 (MST) 是指在加权、连通且无向的图 G 中，其权重小于或等于 G 中所有可能的生成树权重的生成树。生成树的权重是分配给生成树每条边的所有权重的总和。以下是两种最流行的最小生成树 (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 是一个重言式真值表如下：ABA → 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）为真。真值表如下：ABA ∨ 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 中的一条边关联，则子集 C(E) 称为 G 的线路覆盖，即 deg(V) ≥ 1 ∀ V ∈ G因为每个顶点都通过一条边与另一个顶点连接。因此，它具有最小... 阅读更多

基尔霍夫定理可用于查找可从连通图中形成的生成树的数量。示例矩阵 'A' 填充如下，如果两个顶点之间存在边，则应将其指定为 '1'，否则为 '0'。