图着色是将颜色分配给图 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。欧拉回路……阅读更多

图是一组点，称为节点或顶点，它们通过一组称为边的线相互连接。图的研究或图论是数学、工程和计算机科学领域许多学科的重要组成部分。图论定义 - 图（表示为 G = (V, E)）由一组非空顶点或节点 V 和一组边 E 组成。顶点 a 代表边的端点。边连接两个顶点 a、b，并由其连接的顶点集表示。示例 - 让我们……阅读更多