欧拉图和哈密尔顿图.ppt

《欧拉图和哈密尔顿图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二节图的连通性通路和回路无向图的连通性有向图的连通性欧拉图哈密顿图通路和回路可达的：在图G中，结点u和结点v之间存在一条路，则称结点u到结点v是可达的。通路：G中前后相互关联的点边交替序列w=v0e1v1e2…envn称为连接v0到vn的通路。W中边的数目K称为通路W的长。回路：在点边序列v0e1v1e2…envn中，当v0=vn时称此通路为回路。无向图的连通性图是连通的判定法则：从图中任意一结点出发，通过某些边一定能到达其它任意一结点，则称图是连通的。连通：在无向图G中，结点u和结点v之间存在一条路，则称结点u与结点v是连通的。约定

2、：任一结点与自身总是连通的。连通图：若图G中，任意两个结点均连通，则称G是连通图，否则称非连通图。对非连通图可分成几个无公共结点的连通分支。无向图中结点间的连通关系是等价关系。练习1：连通图的判定(1)(2)(3)(4)(5)(6)(7)(8)指出下列各图是否连通欧拉图设G=是连通无向图欧拉通路：在图G中存在一条通路，经过图G中每条边一次且仅一次。欧拉图：具有欧拉回路的图。欧拉回路：在图G中存在一条回路，经过图G中每条边一次且仅一次。（能一笔画）定理7-4无向图G=具有欧拉回路，即是欧拉图的充分必要条件是这个图是连通

3、的，并且图G中所有结点的度数都是偶数，即都与偶数条边相连。定理7-5无向图G=具有欧拉通路的充分必要条件是图G是连通的，并且图G中恰有两个度数是奇数的结点或者没有度数是奇数的结点。欧拉图的判定定理练习3：欧拉回路的判定指出下列各图哪些是欧拉回路？哪些是欧拉通路？（2）（1）(3)(4)(5)(6)(7)例7-7。bdac。。。。。。。。。edcba。。。。。fde。cbaa、b、c、d都为奇结点，无欧拉通路与欧拉回路a、c为奇结点，无欧拉回路有欧拉通路全部结点为偶结点，有欧拉回路有欧拉通路。。。。。。abcdefa、b、c、e

4、都为奇结点，无欧拉通路与欧拉回路。。。。。abcdef全部结点为偶结点，有欧拉回路有欧拉通路例7-8如图街道，是否存在一条投递线路使邮递员从邮局a出发通过所有街到一次在回到邮局a?lkjihgfedcba全部结点为偶结点，故有欧拉回路，即所求投递线路，例如(abcgebdfhdeihkiglkjfa)此投递线路即一笔画线路。一笔画问题：就是判断一个图形能否一笔画成,实质上就是判断图形是否存在欧拉通路和欧拉回路的问题。一笔画的判定定理：⑴如果图中的每个结点都与偶数条边相连，则可以任取一点做始点，一笔画完，回到始点；⑵如果图中只有两个顶点与

5、奇数条边相连，则选择这两个顶点中的一个做始点，一笔画完，终点为另一个与奇数条边相连的结点。练习3：一笔画的判定(1)(2)(3)(4)(5)(6)(7)(8)指出下列各图是否一笔画例7-9一笔画的判定gfedcbaA、f是奇点，有欧拉通路，可以A、f为起点，F、A为终点一笔画成。如(agfecfbdaegdf)af全部结点为偶结点，故有欧拉回路，可以任意结点为起点，且为终点一笔画成。哈密尔顿图?设G=是连通无向图图G中存在一条经过图中的每个结点一次且仅一次的通（回）路，称此通路为哈密顿通（回）路哈密顿图：具有哈密尔顿回路的图。

6、目前还没有找到连通无向图具有哈密顿通（回）路的充分必要条件。图1图2练习4：哈密尔顿回路判定判定下图是否存在哈密尔顿回路！1856年,英国数学家哈密尔顿设计了一个周游世界的游戏，他在一个正十二面体的二十个顶点上标上二十个著名城市的名字，要求游戏者从一个城市出发，经过每一个城市一次且仅一次，然后回到出发点。Example周游世界问题哈密尔顿回路图