83通路、回路、连通图、树及生成树 一、概念和公式的引出 二、进一步的练习 三、概念和公式的引出 四、进一步的练习 五、概念和公式的引出 六、进一步的练习 Click Here
8.3 通路、回路、连通图、树及生成树 一、概念和公式的引出 二、进一步的练习 三、概念和公式的引出 四、进一步的练习 五、概念和公式的引出 六、进一步的练习
一、概念和公式的引出 在下图中，称YV为一条从v到4 且长度为2的通路，其中长度是指通路中边 的条数.称V2CV3eV4e42为一条回路 高等应用数学CAI电子教案 上页下页返回
一、概念和公式的引出 且长度为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 为一条回路．
连通图 任意两点之间都有通路的图为连通图 树 如果一个图是一个连通的，且不包含回路，这样 的图称为树。 生成树 如果一个连通图的某个子图是一棵树，则称该树 为此图的生成树。 高等应用数学CAI电子教案 上页下页返回
任意两点之间都有通路的图为连通图． 连通图 树 如果一个图是一个连通的，且不包含回路，这样 的图称为树 。 生成树 如果一个连通图的某个子图是一棵树，则称该树 为此图的生成树
二、进一步练习 ③练习1在下图中eV4为一条从 v,到v的通路，且长度为3；yey,eVeY 为一条回路；且此图为一个连通图· 高等应用数学CAI电子教案 上页下页返回
二、进一步练习 练习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)的生成 树. 播放 高等应用数学CAI电子教案 上页下页巡回
练习2 在下图中，（a）、（b）是（1）的生成 树．
◆三、概念和公式的引出 欧拉通路与欧拉图 如果一个图中存在经过每一条边一次且仅只一次的 通路，称此通路为欧拉通路。 如果一个图中存在经过每一条边一次且仅只一次的 回路，称为欧拉回路，具有欧拉回路的图称为欧拉图 高等应用数学CAI电子教案 上页下页返回
三、 概念和公式的引出 如果一个图中存在经过每一条边一次且仅只一次的 欧拉通路与欧拉图 通路，称此通路为欧拉通路． 如果一个图中存在经过每一条边一次且仅只一次的 回路，称为欧拉回路，具有欧拉回路的图称为欧拉图．
四、进一步练习 练习1观察下图可知，图(1)存在欧拉通路， 图(2)存在欧拉通路 (1) (2) 高等应用数学CAI电子教案 上页下页返回
练习1 观察下图可知，图（1）存在欧拉通路， 图（2）存在欧拉通路． 四、进一步练习 （1） （2）
管练习2下图(1)存在欧拉通路，图(2)存在 欧拉回路且为欧拉图 (1) (2) 高等应用数学CAI电子教案 上页下页返回
练习2 下图（1）存在欧拉通路，图（2）存在 欧拉回路且为欧拉图． （1） （2）
十五、 概念和公式的引出 个无向图具有一条欧拉通路的充分必要条件是该 图连通且度数为奇数的端点为0个或2个· 一个无向图为欧拉图的充分必要条件是该图连通且 所有端点的度数全为偶数. 高等应用数学CA|电子教案 上页下页返回
五、 概念和公式的引出 一个无向图具有一条欧拉通路的充分必要条件是该 一个无向图为欧拉图的充分必要条件是该图连通且 图连通且度数为奇数的端点为0个或2个． 所有端点的度数全为偶数．
六、进一步练习 练习1蚂蚁比赛问题]甲、乙两只蚂蚁分别位于 下图中的a、b两处，并设abcde为一正5边形的顶 点.甲、乙进行比赛：从它们所在的点出发 走过图中的所有边，最后到达点处·如果它们 速度相同，问谁先到达目的地？ 高等应用数学CAI电子教案 上页下页巡回
练习1[蚂蚁比赛问题] 甲、乙两只蚂蚁分别位于 下图中的a、b两处，并设abcde为一正5边形的顶 点．甲、乙进行比赛：从它们所在的点出发， 走过图中的所有边，最后到达点c处．如果它们 速度相同，问谁先到达目的地？ 六、进一步练习