第七十八讲 连通图和生成树 讲义-2026年高中数学竞赛

第七十八讲  连通图和生成树

1. 连通图

连通性是图的重要概念, 直观上很容易理解, 如果图表示为图示后, 从任意一个顶点可以通过边移动到另外任意一个顶点, 这样的图称为连通的。

下面我们给出连通性的严格定义。设 是一个图,若将顶点集任意划分为两个非空子集 ,都存在 和 ,使得 ,则称 是连通图。只有一个顶点的图自然是连通图。

容易证明: 图 是连通的,当且仅当对 中任意两个顶点 ,都存在 路。在图 中,极大的连通诱导子图称为 的一个连通分支。这里极大的意义是在包含关系下。或等价地,若存在 -路,则令 ,则 是 上的等价关系, 在每个等价类上的诱导子图就是 的一个连通分支。每个图总可以写成若干个连通分支的不交并。

定理 设 是 阶连通图,则 的边数不小于 。

证明 任取 ,令 ,则 。假设对某个 ,定义了 ,且 ,由连通性定义, ,设 联结了 ,和 。则令 ,于是 。这样我们归纳地得到 ,于是 。

推论 设 是一个 阶图,若 有 个连通分支,则 的边数不小于 。

例 1 证明: 任意一个有偶数个顶点的连通简单图都存在一个生成子图, 其各个顶点的度均为奇数。

证明 设 是一个连通的简单图,且 为偶数。由于度为奇数的顶点有偶数个,从而度为偶数的顶点也有偶数个,记所有度为偶数的点为 , 。由于 是连通的,设 是从 到 的一条路上所有边构成的集合, 。令

则 的子图 各个顶点的度均为奇数。事实上,由于 , 故 。将 逐个对 作对称差,考察顶点度的改变,路 内部顶点度数改变偶数,而起点和终点,即 改变 1,其他顶点不改变,因此 的每个顶点的度均为奇数。

例 2 设 是一个有 条边的连通图。证明: 可以将 的边标上 ,使得每个度不小于 2 的顶点处所有边上所标数字的最大公约数为 1 。

证明 将 分拆成若干个(无公共边的)迹 ,使得 最小。对 的起点终点与 的起点终点不同,否则可将 与 合并成一条迹,这与 的最小性矛盾。如果有某个 是闭迹,那么 ,否则若 ,由图的连通性, 必有另一个迹 与 有公共顶点 ,这样 与 可以合并为一条迹 (沿 走到 ,从 可走完 的所有边,再继续沿 走到终点),与 的最小性矛盾。

设 的长度为 。现在我们对 的边从起点开始依次标 ,接着对 的边从起点开始依次标 ,如此下去,最后对 的边从起点开始依次标 。对于 的任意一个度不小于 2 的顶点 ,如果它是某条迹中间经过的点,那么该顶点处有两条边标的是相邻两个正整数,从而最大公约数为 1 。如果 不是任意一条迹中间经过的点,那么它只能是一条迹的起点和终点,由上面讨论可知, 是一个闭迹,该顶点处恰有两条边,标的

数是 1 和 ,也满足要求。

例 3 设 是 到自身的双射。 的一个轨道是指如下的集合

的不同轨道的个数记为 。

设 都是 到 的双射, 。证明:

证明 只需证明 的情形, 的情形可反复利用 时的结论得到。

现设 是两个双射, 的轨道给出 的划分 ,而 的轨道给出 的另一个划分 。作二部图,对 ,若 ,就在 , 之间连一条边。这个图的边数不超过 ,共有 个顶点,因此连通分支数至少有 。

对 ,设 ,若 不在同一个连通分支中,那么 不在 的同一个轨道里。因此 的轨道数至少有 。

2. 树

树是包含边数最少的连通图, 任何一个连通图中也总有一个生成子图是树 (称为生成树), 因此可以说树是最基本的连通图。

我们称一个连通无圈的图为树。

定理 设 是一个 阶简单连通图。以下结论等价:

(1)  G 是树，即 不含圈。

(2)  的边数为 。