第七十九讲 欧拉图与平面图讲义-2026年高中数学竞赛

第七十九讲  欧拉图与平面图

1. 欧拉图

欧拉图的概念源于欧拉对哥尼斯堡七桥问题的研究。下面我们首先讲述这一著名的问题。

例 1 景致迷人的哥尼斯堡 (即现今的加里宁格勒) 被帕瑞格尔河横贯。河中有两个岛 与 ,河上有 7 座桥连接这两个岛及河的两岸 (如图)。试问:一个旅游者能否通过每一座桥恰好一次并回到出发点?

                      

                      

解 将两个岛屿 以及两岸 抽象为顶点,连接它们之间的 7 座桥抽象为这 4 个顶点之间的 7 条边,如图。

我们得到一个图 ,问题转化为能否从某个顶点出发,走遍 中所有的边恰好一次并回到出发点? 用图论语言来讲,是否存在一个遍历所有边的闭迹?

由于 4 个顶点的度分别为5,3,3,3,均为奇顶点。由下面的欧拉一笔画定理可知答案是否定的。

在图 中,一条遍历所有边的迹、闭迹,分别称为欧拉迹、欧拉闭迹。若图 中存在欧拉闭迹，则称 是欧拉图。

定理(欧拉一笔画定理) 一个连通图 是欧拉图当且仅当 的每个顶点均是偶点。

证明 必要性:考虑 的一个欧拉闭迹

对每条边 ,给予定向: 指向 (约定 ),从而得到 的一个定向图 。对每个 ，边 指向 ，边 由 指出，边 分别为 提供了一个入度和一个出度,而边 和 为 也提供了一个出度和一个入度，因此 中每个顶点的出度与入度相同。从而在 中,每个顶点都是偶点。

充分性: 我们对 的边数 归纳。 时, 是空图,结论显然成立。假设 0，且结论在边数较小时成立。由于 的每个顶点均为偶顶点，从而每个顶点的度均不小于 2,于是 中存在圈 (圈也是闭迹)。取 的长度最长的闭迹 。若 不是欧拉闭迹,从 中删去 上的所有边 。从必要性的论证可知, 上每个顶点均为偶点,因此 中每个顶点也是偶点。设 是 的一个非平凡连通分支,由归纳假设, 是欧拉图。由 的连通性,可知 中必有顶点在 上。设 是 的欧拉闭迹,并且 在 上,可将 的顶点和边作适当循环,不妨设 ,这样可将 与 合并为更长的闭迹,

这与 的最大性矛盾。因此 是欧拉闭迹。

推论 一个连通图存在欧拉迹当且仅当奇点的个数是 0 或 2 。

证明 必要性: 设图 中存在欧拉迹,沿着欧拉迹的方向给每条边定向,若是欧拉闭迹，则每个顶点的出度和入度相同，从而 的每个顶点均是偶点; 若不是闭迹，则起点和终点的出入度相差 1 ，这两个点是奇点。从而奇点的个数是 0 或 2。

充分性:若奇点个数为 0，则由上面的定理得 中有欧拉闭迹。若奇点的个数为 2,设 是两个奇点,在 中添上一条联结 的边 ,得到图 ,每个顶点都是偶点,从而 中有欧拉闭迹,不妨设闭迹中的最后一条边是 ,删去 后,得到 中的从 到 的欧拉迹。

例 2 将若干个单位立方体沿着对角线各打一个小孔,再用一根细线把它们穿起来。允许这些小立方体在空间自由移动，但每两个相邻的立方体的顶点必须保持接触。设 是起点, 是终点。细线上穿有 个单位立方体,这里 均为正整数。

(1)    确定 需满足的充分必要条件，使得可以把这个正方体串变成一个长、 宽、高分别为 的长方体。

(2)    同问题(1)，但增加条件顶点 与顶点 重合。

解 将 的长方体 分成单位立方体,每个立方体内四条对角线都画出, 以所有单位立方体的顶点为顶点集,这些 条对角线为边集,构成一个图 。更具体而言,可设

在 中相邻当且仅当 1。顶点按坐标奇偶性分成四个集合, ,

(奇,奇,奇),(偶,偶,偶) (奇,奇,偶),(偶,偶,奇)

(奇,偶,奇),(偶,奇,偶) (偶,奇,奇),(奇,偶,偶)}。

记 。每个 均是连通的,每个正方体的四条对角线分别属于这四个子图, 故每个 的边数均为 。

问题(1)等价于问是否有某个 恰是一个欧拉路，问题(2)等价于问是否有