图论 - 示例

在本章中，我们将介绍几个标准示例，以演示我们在前面章节中已经讨论过的概念。

示例 1

求下图中生成树的数量。

解决方案

从上图获得的生成树数量为 3。它们如下 −

这三棵是给定图的生成树。这里的图 I 和 II 彼此同构。显然，非同构生成树的数量为 2。

示例 2

有多少个简单的非同构图可能有 3 个顶点？

解决方案

有 4 个非同构图可能有 3 个顶点。它们如下所示。

示例 3

假设"G"是一个连通平面图，有 20 个顶点，每个顶点的度为 3。求图中区域的数量。

解决方案

根据度和定理，

20 Σ i=1 deg(Vi) = 2|E|

20(3) = 2|E|

|E| = 30

根据欧拉公式，

|V| + |R| = |E| + 2

20+ |R| = 30 + 2

|R| = 12

因此，区域数为 12。

示例 4

完全图 Kn 的色数是多少？

解决方案

在完全图中，每个顶点都与剩余的 (n-1) 个顶点相邻。因此，每个顶点都需要一种新颜色。因此色数 Kn = n。

示例 5

以下图形的匹配数是多少？

解决方案

顶点数 = 9

我们只能匹配 8 个顶点。

匹配数为 4。

示例 6

以下图形的线覆盖数是多少？

解决方案

顶点数 = |V| = n = 7

线覆盖数 = (α₁) ≥ [n/2] = 3

α₁ ≥ 3

通过使用 3 条边，我们可以覆盖所有顶点。

因此，线覆盖数为 3。