温州职业技术学院：《高等应用数学》第八章 图论（8.3）通路、回路、连通图、树及生成树

8.3通路、回路、连通图、树及生成树 一、概念和公式的引出 二、进一步的练习 三、概念和公式的引出 ■四、进一步的练习 五、概念和公式的引出 六、进一步的练习 click Here

8.3 通路、回路、连通图、树及生成树 一、概念和公式的引出 二、进一步的练习 三、概念和公式的引出 四、进一步的练习 五、概念和公式的引出 六、进一步的练习

、概念和公式的引出 弩在下图中,称ve2e4为一条从v到v 且长度为2的通路,其中长度是指通路中边 的条数.称V2e233e4V2为—条回路 高等应用数学CAⅠ电子教案 上页下页迅回

一、概念和公式的引出 且长度为2的通路，其中长度是指通路中边 在下图 中，称 1 1 2 4 4 v e v e v 为一条从v1到v4 2 2 3 3 4 4 2 的条数．称 v e v e v e v 为一条回路．

连通图 任意两点之间都有通路的图为连通图 树 如果一个图是一个连通的,且不包含回路,这样 的图称为树 生成树」 如果一个连通图的某个子图是一棵树,则称该树 为此图的生成树 高等应用数学CAⅠ电子教案 上页下页迅回

任意两点之间都有通路的图为连通图． 连通图 树 如果一个图是一个连通的，且不包含回路，这样 的图称为树 。 生成树 如果一个连通图的某个子图是一棵树，则称该树 为此图的生成树

E=、进一步练习 练习1在下图中V2e2334为一条从 v1到v的通路,且长度为3;ve3v3esve4 为一条回路;且此图为一个连通图 高等应用数学CAⅠ电子教案 上页下页迅回

二、进一步练习 练习1 在下图中， 1 1 2 2 3 5 4 v e v e v e v 为一条从 v1到v4的通路，且长度为3； 1 3 3 5 4 4 1 v e v e v e v 为一条回路；且此图为一个连通图．

练习2在下图中,(a)、(b)是(1)的生成 树 播放 高等应用数学CAⅠ电子教案 上页下页迅回

练习2 在下图中，（a）、（b）是（1）的生成 树．

三、概念和公式的引出 欧拉通路与欧拉图 如果一个图中存在经过每一条边一次且仅只一次的 通路,称此通路为欧拉通路 如果一个图中存在经过每一条边一次且仅只一次的 回路,称为欧拉回路,具有欧拉回路的图称为欧拉图 高等应用数学CAⅠ电子教案 上页下页迅回

三、 概念和公式的引出 如果一个图中存在经过每一条边一次且仅只一次的 欧拉通路与欧拉图 通路，称此通路为欧拉通路． 如果一个图中存在经过每一条边一次且仅只一次的 回路，称为欧拉回路，具有欧拉回路的图称为欧拉图．

习四进-步练习 练习1观察下图可知,图(1)存在欧拉通路 图(2)存在欧拉通路 (1) (2) 高等应用数学CAⅠ电子教案 产页下页回

练习1 观察下图可知，图（1）存在欧拉通路， 图（2）存在欧拉通路． 四、进一步练习 （1） （2）

练习2下图(1)存在欧拉通路,图(2)存在 欧拉回路且为欧拉图 高等应用数学CAⅠ电子教案 上页下页迅回

练习2 下图（1）存在欧拉通路，图（2）存在 欧拉回路且为欧拉图． （1） （2）

≯五、概念和公式的引出 一个无向图具有一条欧拉通路的充分必要条件是该 图连通且度数为奇数的端点为0个或2个 一个无向图为欧拉图的充分必要条件是该图连通且 所有端点的度数全为偶数 高等应用数学CAⅠ电子教案 上页下页迅回

五、 概念和公式的引出 一个无向图具有一条欧拉通路的充分必要条件是该 一个无向图为欧拉图的充分必要条件是该图连通且 图连通且度数为奇数的端点为0个或2个． 所有端点的度数全为偶数．

F六、进一步练习 练习1蚂蚁比赛问题]甲、乙两只蚂蚁分别位于 下图中的a、b处,并设 abcde为一正5边形的顶 点.甲、乙进行比赛:从它们所在的点出发, 走过图中的所有边,最后到达点c处.如果它们 速度相同,问谁先到达目的地? 高等应用数学CAⅠ电子教案 产页下页回

练习1[蚂蚁比赛问题] 甲、乙两只蚂蚁分别位于 下图中的a、b两处，并设abcde为一正5边形的顶 点．甲、乙进行比赛：从它们所在的点出发， 走过图中的所有边，最后到达点c处．如果它们 速度相同，问谁先到达目的地？ 六、进一步练习