8.3 通路、回路、连通图、树及生成树
一、概念和公式的引出
二、进一步的练习
三、概念和公式的引出
四、进一步的练习
五、概念和公式的引出
六、进一步的练习
一、概念和公式的引出
且长度为 2的 通路, 其中长度是指通路中边
在下图 中，称
44211 vevev 为一条从 v1到 v4
2443322 vevevev
的条数, 称 为一条 回路,
任意两点之间都有通路的图为 连通图,
连通图
树
如果一个图是一个连通的, 且不包含回路, 这样
的图称为 树 。
生成树
如果一个连通图的某个子图是一棵树, 则称该树
为此图的 生成树 。
二、进一步练习
练习 1 在下图中，
4532211 vevevev 为一条从
v1到 v4的通路, 且长度为 3；
1445331 vevevev
为一条回路；且此图为一个连通图,
练习 2 在下图中，（ a）、（ b）是（ 1）的生成
树．
三,概念和公式的引出
如果一个图中存在经过每一条边一次且仅只一次的
欧拉通路与欧拉图
通路，称此通路为 欧拉通路,
如果一个图中存在经过每一条边一次且仅只一次的
回路，称为 欧拉回路,具有欧拉回路的图称为 欧拉图,
练习 1 观察下图可知，图（ 1）存在欧拉通路，
图（ 2）存在欧拉通路．
四、进一步练习
（ 1） （ 2）
练习 2 下图（ 1）存在欧拉通路，图（ 2）存在
欧拉回路且为欧拉图．
（ 1） （ 2）
五,概念和公式的引出
一个无向图具有一条欧拉通路的 充分必要条件 是该
一个无向图为欧拉图的 充分必要条件 是该图连通且
图连通且度数为奇数的端点为 0个或 2个．
所有端点的度数全为偶数．
练习 1[蚂蚁比赛问题 ] 甲、乙两只蚂蚁分别位于
下图中的 a,b两处，并设 abcde为一正 5边形的顶
点．甲、乙进行比赛：从它们所在的点出发，
走过图中的所有边，最后到达点 c处．如果它们
速度相同，问谁先到达目的地？
六、进一步练习
在上图中,b,c两个点的度数为奇数，因而存
在从 b到 c的欧拉通路，蚂蚁乙走到 c，只要走一
条欧拉通路，边数为 9．而蚂蚁甲要走完所有
的边到达 c，必须先要走到 b，再走一条欧拉通
路，因而它至少要走 10条边才能到达 c，所以乙
先到达目的地．
解
练习 2[一笔画问题 ] 一个无向图是否存在欧拉通路
（回路）的问题，称为“一笔画问题”，即笔不
离纸，每条边只画一次而不许重复，能够画完该
图．观察下图可以看出，图（ 1）、（ 2）都是可
以一笔画出．但又有区别，不同之处在于图（ 1）
结束点不能回到出发点．
（ 1） （ 2）