有根树有根树 G 是一个连通的无环图，其中有一个特殊的节点称为树的根，并且每条边都直接或间接地起源于根。有序有根树是有根树，其中每个内部顶点的子节点都是有序的。如果一个有根树的每个内部顶点最多有 m 个子节点，则称为 m 叉树。如果一个有根树的每个内部顶点恰好有 m 个子节点，则称为满 m 叉树。如果 m = 2，则有根树称为二叉树。二叉... 阅读更多

关系可以使用有向图表示。图中顶点的数量等于定义关系的集合中元素的数量。对于关系 R 中的每个有序对 (x, y)，都将有一条从顶点“x”到顶点“y”的有向边。如果存在有序对 (x, x)，则顶点“x”上将有一个自环。假设在集合 S = { 1, 2, 3 } 上存在一个关系 R = { (1, 1), (1,2), (3, 2) }，它可以用以下图形表示：

主要有两种方法可以表示图：邻接矩阵邻接表邻接矩阵邻接矩阵 A[V][V] 是一个大小为 V × V 的二维数组，其中 $V$ 是无向图中顶点的数量。如果在 Vx 到 Vy 之间存在一条边，则 A[Vx][Vy]=1 且 A[Vy][Vx]=1，否则值为零。对于有向图，如果在 Vx 到 Vy 之间存在一条边，则 A[Vx][Vy]=1，否则值为零。无向图的邻接矩阵让我们考虑以下无向图并构造其邻接矩阵：... 阅读更多

关系可能存在于同一集合的对象之间，或者存在于两个或多个集合的对象之间。定义和属性从集合 x 到 y 的二元关系 R（写成 xRy 或 R(x, y)）是笛卡尔积 x × y 的一个子集。如果 G 的有序对反转，关系也会发生变化。通常，集合 A1、...、和 An 之间的 n 元关系 R 是 n 元积 A1 × ... × An 的一个子集。在这种情况下，关系 R 的最小基数为零，最大基数为 n2。集合上的二元关系 R... 阅读更多

谓词演算处理谓词，谓词是包含变量的命题。谓词谓词是在某个特定域上定义的一个或多个变量的表达式。通过为变量赋值或量化变量，可以将包含变量的谓词变为命题。考虑以下陈述。Ram 是一名学生。现在考虑谓词演算中的上述陈述。这里“是一名学生”是一个谓词，而 Ram 是主语。让我们将“Ram”表示为 x，将“是一名学生”表示为谓词 P，然后我们可以将上述陈述写成 P(x)。通常，用谓词表达的陈述必须在... 阅读更多

集合 S 的幂集是 S 的所有子集的集合，包括空集。基数为 n 的集合 S 的幂集的基数为 2n。幂集表示为 P(S)。示例：对于集合 S = { a, b, c, d }，让我们计算其子集：包含 0 个元素的子集：{ ∅ }（空集）包含 1 个元素的子集：{ a }、{ b }、{ c }、{ d }包含 2 个元素的子集：{ a, b }、{ a, c }、{ a, d }、{ b,... 阅读更多

平面图 - 如果一个图 G 可以绘制在平面上且没有任何边交叉，则称其为平面图。如果我们在平面上绘制图且没有边交叉，则称为将图嵌入平面。非平面图 - 如果一个图不能在平面上绘制而没有任何图边交叉，则称其为非平面图。

如果一个图“G”可以绘制在平面上或球体上，使得任何两条边都不会在非顶点处交叉，则称其为平面图。示例区域每个平面图都将平面划分为称为区域的连通区域。示例有界区域 r 的度数 = deg(r) = 包围区域 r 的边的数量。deg(1) = 3 deg(2) = 4 deg(3) = 4 deg(4) = 3 deg(5) = 8无界区域 r 的度数 = deg(r) = 包围区域 r 的边的数量。deg(R1) = 4 deg(R2) = 6在平面图中，以下性质成立：1. 在... 阅读更多

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

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