欧拉图和哈密尔顿图

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