集合 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。欧拉回路… 阅读更多