图着色是将颜色分配给图 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，并由它连接的顶点集表示。示例 - 让我们... 阅读更多