连通图.ppt

* 第一节 函数及其图形 8.3 通路、回路、连通图、树及生成树 一、概念和公式的引出 二、进一步的练习 三、概念和公式的引出 四、进一步的练习 五、概念和公式的引出 六、进一步的练习 一、概念和公式的引出 且长度为2的通路，其中长度是指通路中边 在下图 中，称 为一条从v1到v4 的条数．称 为一条回路． 任意两点之间都有通路的图为连通图． 连通图 树 如果一个图是一个连通的，且不包含回路，这样的图称为树 。 生成树 如果一个连通图的某个子图是一棵树，则称该树为此图的生成树 。 二、进一步练习 练习1 在下图中， 为一条从 v1到v4的通路，且长度为3； 为一条回路；且此图为一个连通图． 练习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，所以乙先到达目的地． 解