线性代数8-3.ppt

8.3 通路、回路、连通图、树及生成树,一、,概念和公式的引出,二、进一步的练习,三、,概念和公式的引出,四、,进一步的练习,五、,概念和公式的引出,六、,进一步的练习,一、概念和公式的引出,且长度为,2,的,通路,，其中长度是指通路中边,在下图 中，称,为一条从,v,1,到,v,4,的条数称,为一条,回路,任意两点之间都有通路的图为,连通图,连通图,树,如果一个图是一个连通的，且不包含回路，这样的图称为,树,。,生成树,如果一个连通图的某个子图是一棵树，则称该树为此图的,生成树,。,二、进一步练习,练习,1,在下图中，,为一条从,v,1,到,v,4,的通路，且长度为,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,，,所以乙先到达目的地,解,练习,2,一笔画问题,一个无向图是否存在欧拉通路（回路）的问题，称为“一笔画问题”，即笔不离纸，每条边只画一次而不许重复，能够画完该图观察下图可以看出，图（,1,）、（,2,）都是可以一笔画出但又有区别，不同之处在于图（,1,）结束点不能回到出发点,（1,）,（2,）,