图论 - 例子
在本章中，我们将介绍一些标准示例来演示我们在前面的章节中已经讨论过的概念。
实施例1
求下图中生成树的数量。
解决方案
从上图中获得的生成树数量为 3。它们如下 -
这三个是给定图的生成树。这里图 I 和图 II 是同构的。显然，非同构生成树的数量为二。
实施例2
具有 3 个顶点的简单非同构图可能有多少种？
解决方案
有 3 个顶点可能有 4 个非同构图。它们如下所示。
实施例3
令“G”为具有 20 个顶点的连通平面图，每个顶点的度数为 3。求图中的区域数。
解决方案
根据度数总和定理，
20 Σ i=1 度(Vi) = 2|E|
20(3) = 2|E|
|E| = 30
根据欧拉公式，
|V| + |R| =|E| + 2
20+ |R| = 30 + 2
|R| = 12
因此，区域数量为 12。
实施例4
完全图 K n的色数是多少？
解决方案
在完全图中，每个顶点都与剩余的 (n–1) 个顶点相邻。因此，每个顶点都需要一种新颜色。因此色数 K n = n。
实施例5
下图对应的数字是多少？
解决方案
顶点数 = 9
我们只能匹配 8 个顶点。
匹配数为4。
实施例6
下图中的直线覆盖了多少条线？
解决方案
顶点数 = |V| = n = 7
线路覆盖数 = (α 1 ) ≥ [n/2] = 3
α1≥3 _ _
通过使用 3 条边，我们可以覆盖所有顶点。
因此，行覆盖数为 3。