《二章道路与回路2道路与回路.ppt》由会员分享,可在线阅读,更多相关《二章道路与回路2道路与回路.ppt(25页珍藏版)》请在三一文库上搜索。
1、第二章 道路与回路 2.1道路与回路,定义2.1.1 有向图 中,若边序列 ,其中 满足 是 的终点, 是 的始点,就称 是 的一条有向道路。如果 的终点也是 的始点,则称 是 的一条有向回路。,道路与回路,如果 中的边没有重复出现,则分别称为简单有向道路和简单有向回路。进而,如果 中结点也不重复出现,又分别称它们是初级有向道路和初级有向回路简称为路和回路。显然,初级有向道路(回路)一定是简单有向道路(回路)。,道路与回路,定义2.1.2 无向图 中,若点边交替序列 满足 是 的两个端点,则称 是 中的一条链或道路。如果 ,则称 是 中的一个圈,或回路。 如果 中没有重复出现的边,称之为简单道
2、路或简单回路,若其中结点也不重复,又称之为初级道路或初级回路。,道路与回路,定义2.1.3 设 是无向图,若 的任意两结点之间都存在道路,就称 是连通图,否则称为非连通图。 如果 是有向图,不考虑其边的方向,即视为无向图,若它是连通的,则称 是连通图。 若连通子图 不是 的任何连通子图的真子图,则称 是 的极大连通子图,或称连通支。显然 的每个连通支都是它的导出子图。,道路与回路,定义2.1.4 设 是简单图 中含结点数大于3的一个初级回路,如果结点 和 在 中不相邻,而边 ,则称 是 的一条弦。,道路与回路,证明:若对每一个 ,都有 ,则 中必含带弦的回路。 证明:在 中构造一条初级道路 ,
3、不妨设 , 。由于 是极长的初级道路,所以 和 的邻接电都在该道路 了。由已知条件, ,不妨设 。其中 ,这时 是一条初级回路,而 就是该回路中的一条弦。,道路与回路,定义2.1.5 设 是无向图,如果 可以划分为子集 和 ,使得对所有的 , 和 都分属于 和 ,则称 是二分图。,道路与回路,证明:如果二分图 中存在回路,则它们都是由偶数条边组成的。 证明:设 是二分图 的任一条回路,不妨设 是 的始点,由于 是二分图,所以沿回路 必须经过偶数条边才能达到某结点 ,因而只有经过偶数条边才能回到 。,道路与回路,证明:设 是简单图,当 时, 是连通图。 证明:假定 是非连通图,则它至少含有2个连
4、通分支。设分别是 。其中 由于 是简单图,因此,道路与回路,由于 , 所以 与已知条件矛盾,故 是连通图。,2.3 欧拉道路与回路,欧拉道路与回路,1736年瑞士著名数学家欧拉(Leonhard Euler)发表了图论的第一篇论文“哥尼斯堡七桥问题”。成功地回答了,图中是否存在经过每条边一次且仅一次的回路。,欧拉道路与回路,欧拉道路与回路,定义2.3.1 无向连通图 中的一条经过所有边的简单回路(道路)称为 的欧拉回路(道路)。 定理2.3.1 无向连通图 存在欧拉回路的充要条件是 中各结点的度都是偶数。,欧拉道路与回路,定理2.3.1的证明: 1. 必要性:若 中有欧拉回路 ,则 过每条边一
5、次且仅一次。对任一结点 来说,如果 经过 进入 ,则一定通过另一条边 从 离开。因此结点 的度是偶数。 2. 充分性:由于 是有穷图,因此可以断定,从 的任一结点 出发一定存在 的一条简单回路 。这是因为各结点的度都是偶数,所以这条简单道路不可能停留在 以外的某个点,而不能再向前延伸以致构成回路 。,欧拉道路与回路,推论2.3.1 若无向连通图 中只有2个度为奇的结点。则 存在欧拉道路。 证明:设 和 是两个度为奇数的结点。作 ,则 中各点的度都是偶数。由定理2.3.1, 有欧拉回路,它含边 ,删去该边,得到一条从 到 的简单道路,它恰好经过了 的所有边,亦即是一条欧拉道路。,欧拉道路与回路,
6、推论2.3.2 若有向连通图 中各结点的正,负度相等,则 存在有向欧拉道路。 其证明与定理2.3.1的证明相仿。,欧拉道路与回路,例2.3.3 设连通图G=(V,E)有k个度为奇数的结点,那么E(G)可以划分成k/2条简单道路。 证明:由性质1.1.2,k是偶数。在这k个结点间增添k/2条边,使每个结点都与其中一条边关联,得到G,那么G中各结点的度都为偶数。 由定理2.3.1,G包含一个欧拉回路C。而新添的k/2条边再C上都不相邻。所以删去这些边后,我们就得到由E(G)划分成的k/2条简单道路。,2.4 哈密顿道路与回路,哈密顿道路与回路,哈密顿道路与回路,定义2.4.1 无向图的一条过全部结
7、点的初级回路(道路)称为G的哈密顿回路(道路),简记为H回路(道路)。 哈密顿回路是初级回路,是特殊的简单回路,因此它与欧拉回路不同。当然在特殊情况下,G的哈密顿回路恰好也是其欧拉回路。鉴于H回路是初级回路,所以如果G中含有重边或自环,删去它们后得到的简单图G,那么G和G关于H回路(道路)的存在性是等价的。因此,判定H回路存在性问题一般是针对简单图的。,哈密顿道路与回路,定理2.4.1 如果简单图G的任意两结点 之间恒有 ,则G中存在哈密顿路。,哈密顿道路与回路,推论2.4.1 若简单图 的任意两结点 和 之间恒有 ,则 中存在哈密顿回路。 推论2.4.2 若简单图 中每个结点的度都大于等于 ,则 有 回路。,哈密顿道路与回路,引理2.4.1 设 是简单图, 是不相邻结点,且满足 ,则 存在 回路的充要条件是 有 回路。 定义2.4.2 若 和 是简单图 的不相邻结点,且满足 ,则令 对 重复上述过程,直至不再有这样的结点对为止。最终得到的图为 的闭合图,记作 。,哈密顿道路与回路,引理2.4.2 简单图 的闭合图 是唯一的。 定理2.4.2 简单图 存在哈密顿回路的充要条件是其闭合图存在哈密顿回路。 推论2.4.3 设 是简单图,若 完全图, 有 回路。,
链接地址:https://www.31doc.com/p-3106726.html