欧拉图和哈密尔顿图.ppt

第二节 图的连通性,通路和回路 无向图的连通性 有向图的连通性 欧拉图 哈密顿图,通路和回路,可达的：在图G中，结点u和结点v之间存在一条路，则称结点u到结点v是可达的。,通路：G中前后相互关联的点边交替序列w=v0e1v1e2envn称为连接v0到vn的通路。W中边的数目K称为通路W的长。,回路：在点边序列v0e1v1e2envn中，当v0=vn时称此通路为回路。,无向图的连通性,图是连通的判定法则：从图中任意一结点出发，通过某些边一定能到达其它任意一结点，则称图是连通的。,连通：在无向图G中，结点u和结点v之间存在一条路，则称结点u与结点v是连通的。约定：任一结点与自身总是连通的。,连通图：若图G中，任意两个结点均连通，则称G是连通图，否则称非连通图。对非连通图可分成几个无公共结点的连通分支。无向图中结点间的连通关系是等价关系。,练习1：连通图的判定,指出下列各图是否连通,欧拉图,设G=是连通无向图欧拉通路：在图G中存在一条通路，经过图G中每条边一次且仅一次。,欧拉图：具有欧拉回路的图。,欧拉回路：在图G中存在一条回路，经过图G中每条边一次且仅一次。（能一笔画）,定理7-4 无向图G=具有欧拉回路，即是欧拉图的充分必要条件是这个图是连通的，并且图G中所有结点的度数都是偶数，即都与偶数条边相连。,定理7-5 无向图G=具有欧拉通路的充分必要条件是图G是连通的，并且图G中恰有两个度数是奇数的结点或者没有度数是奇数的结点。,欧拉图的判定定理,练习3：欧拉回路的判定,指出下列各图哪些是欧拉回路？哪些是欧拉通路？,例7-7,。,b,d,。,。,。,。,。,a,a、b、c、d都为奇结点，无欧拉通路与欧拉回路,a、c为奇结点，无欧拉回路有欧拉通路,全部结点为偶结点，有欧拉回路有欧拉通路,。,。,。,。,。,。,a、b、c、e都为奇结点，无欧拉通路与欧拉回路,。,。,。,全部结点为偶结点，有欧拉回路有欧拉通路,例7-8 如图街道，是否存在一条投递线路使邮递员从邮局a出发通过所有街到一次在回到邮局a?,l,k,j,i,h,g,f,e,d,c,b,a,全部结点为偶结点，故有欧拉回路，即所求投递线路，,例如(abcgebdfhdeihkiglkjfa),此投递线路即一笔画线路。,一笔画问题：就是判断一个图形能否一笔画成,实质上就是判断图形是否存在欧拉通路和欧拉回路的问题。,一笔画的判定定理：如果图中的每个结点都与偶数条边相连，则可以任取一点做始点，一笔画完，回到始点；如果图中只有两个顶点与奇数条边相连，则选择这两个顶点中的一个做始点，一笔画完，终点为另一个与奇数条边相连的结点。,练习3：一笔画的判定,指出下列各图是否一笔画,例7-9一笔画的判定,g,f,e,d,c,b,a,A、f是奇点，有欧拉通路，可以A、f为起点，F、A为终点一笔画成。,如(agfecfbdaegdf),全部结点为偶结点，故有欧拉回路，可以任意结点为起点，且为终点一笔画成。,哈密尔顿图,?,设G=是连通无向图 图G中存在一条经过图中的每个结点一次且仅一次的通（回）路，称此通路为哈密顿通（回）路 哈密顿图：具有哈密尔顿回路的图。目前还没有找到连通无向图具有哈密顿通（回）路的充分必要条件。,练习4：哈密尔顿回路判定,判定下图是否存在哈密尔顿回路！,1856年,英国数学家哈密尔顿设计了一个周游世界的游戏，他在一个正十二面体的二十个顶点上标上二十个著名城市的名字，要求游戏者从一个城市出发，经过每一个城市一次且仅一次，然后回到出发点。,Example 周游世界问题,哈密尔顿回路图,