在一个加权的、连通的、无向图 $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 是一个重言式真值表如下所示-ABA → B(A → B) ∧ A[ (A → B) ∧ A ] → B真真真真真真假假假真假真真假真假假真假假真如我们所见，[ (A → B) ∧ A ] → B 的每个值都为“真”，它是一个重言式。矛盾矛盾是指对于其命题变量的每个值都始终为假的公式。示例-证明 (A ∨ B) ∧ [ ( ¬ A) ∧ (¬ B) ] ... 阅读更多

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

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

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

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

同构如果两个图 G 和 H 包含相同数量的顶点并以相同的方式连接，则它们称为同构图（表示为 G ≅ H）。检查非同构比检查同构更容易。如果出现以下任何条件，则两个图是非同构的-连通分量的数量不同顶点集基数不同边集基数不同度序列不同示例以下图是同构的-同态从图 G 到图 H 的同态是映射（可能不是双射映射）h: G → H，使得-(x, y) ∈ E(G) → (h(x), h(y)) ∈ ... 阅读更多