集合 S 的基数，记为 |S|，是集合中元素的数量。这个数字也称为基数。如果一个集合有无限多个元素，则其基数为 ∞。例如 - |{1, 4, 3, 5}| = 4，|{1, 2, 3, 4, 5, ....}| = ∞如果存在两个集合 X 和 Y，|X| = |Y| 表示两个集合 X 和 Y 具有相同的基数。当 X 中的元素数量正好等于 Y 中的元素数量时，就会发生这种情况。在这种情况下，存在一个双射函数 'f' ... 阅读更多

图着色是将颜色分配给图 G 的每个顶点的过程，使得没有相邻的顶点获得相同的颜色。目标是在着色图时最小化颜色的数量。对图 G 着色所需的最小颜色数称为该图的色数。图着色问题是一个 NP 完全问题。图着色方法对具有 n 个顶点的图 G 着色的步骤如下：步骤 1 - 按某种顺序排列图的顶点。步骤 2 - 选择第一个... 阅读更多

函数将一个集合的每个元素分配给相关集合的恰好一个元素。函数在各个领域都有应用，例如表示算法的计算复杂度、计数对象、研究序列和字符串，仅举几例。这部分的第三章也是最后一章重点介绍了函数的重要方面。函数 - 定义函数或映射（定义为 f: X → Y）是根据一个集合 X 的元素与另一个集合 Y 的元素之间的关系（X 和 Y 是非空集合）。X 称为函数 'f' 的定义域，Y 称为函数 'f' 的陪域。函数... 阅读更多

问题陈述查找以下图中生成树的数量。解决方案从上图获得的生成树数量为 3。它们如下：这三个是给定图的生成树。这里图 I 和 II 彼此同构。显然，非同构生成树的数量为两个。

问题陈述设 'G' 为一个具有 20 个顶点的连通平面图，每个顶点的度数为 3。求图中区域的数量。解决方案根据度数和定理，20 ∑ i=1 deg(Vi) = 2|E|20(3) = 2|E||E| = 30根据欧拉公式，|V| + |R| = |E| + 220+ |R| = 30 + 2|R| = 12因此，区域的数量为 12。

问题陈述具有 3 个顶点的简单非同构图有多少种可能？解决方案具有 3 个顶点的非同构图有 4 种可能。它们如下所示。

问题陈述以下图的匹配数是多少？解决方案顶点数 = 9我们只能匹配 8 个顶点。匹配数为 4。

问题陈述以下图的边覆盖数是多少？解决方案顶点数 = |V| = n = 7边覆盖数 = (α1) ≥ ⌈ n / 2 ⌉ = 3α1 ≥ 3通过使用 3 条边，我们可以覆盖所有顶点。因此，边覆盖数为 3。

问题陈述完全图 Kn 的色数是多少？解决方案在完全图中，每个顶点都与其剩余的 (n-1) 个顶点相邻。因此，每个顶点都需要一种新颜色。因此，色数 Kn = n。

如果您可以绘制所有顶点之间的路径而不重复相同的路径，则图是可遍历的。基于此路径，有一些类别，例如欧拉路径和欧拉回路，在本节中进行了描述。欧拉路径欧拉路径恰好包含 'G' 的每条边一次，并且至少包含 'G' 的每个顶点一次。如果连通图 G 包含欧拉路径，则称其为可遍历的。示例欧拉路径 = d-c-a-b-d-e。欧拉回路在欧拉路径中，如果起始顶点与结束顶点相同，则称为欧拉回路。示例欧拉路径 = a-b-c-d-a-g-f-e-c-a。欧拉回路... 阅读更多