2023年7月19日发(作者：)

专题二：欧拉图与欧拉路径

该材料用于图论第2讲课问题说明及自学提示环节与学生课外自学环节

自学章节： 8.2.4

学时安排：课内2学时，课外6学时

重点：欧拉定理及推论、实际问题转换为欧拉图求解

问题一：一笔画问题

有347个顶点的完全图能否一笔画？有1286个顶点的完全图呢？

问题二：蚂蚁比赛问题

甲、乙两只蚂蚁分别位于下图中的结点a，b处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点c处。如果它们的速度相同，问谁先到达目的地？

问题三：展览馆游览问题

一展览馆平面图如下：一参观者来到展览馆门外，他想在参观过程中把所有门都不重复的穿行一遍，问他能办到吗？为什么？

问题提示：

图模型的构建是关键。

问题四：多米诺骨牌问题（例8.2-2）

多米诺骨牌骨牌的一面可以是0,1,2,3,4,5,6中的一个数字，问：是否能将28张不同（只要有一面不同视为牌不同）的多米诺骨牌排成一个圆形,使得在这个排列中,每两块相邻的骨牌其相邻的两个半面是相同的? 提示：

图模型的构建是关键。教材分析很含糊。

问题五：布鲁英(DeBruijn)序列问题

造出一个长度为16的布鲁因序列

提示：

参看例8.2-3，如何构造8长度的布鲁因序列。这是有向欧拉图在译码上面的应用。