欧拉图和哈密尔顿图.ppt

第二节图的连通性 通路和回路无向图的连通性有向图的连通性欧拉图哈密顿图 通路和回路 可达的 在图G中 结点u和结点v之间存在一条路 则称结点u到结点v是可达的 通路 G中前后相互关联的点边交替序列w v0e1v1e2 envn称为连接v0到vn的通路 W中边的数目K称为通路W的长 回路 在点边序列v0e1v1e2 envn中 当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周游世界问题 哈密尔顿回路图