专业文档是百度文库认证用户/机构上传的专业性文档,文库VIP用户或购买专业文档下载特权礼包的其他会员用户可用专业文档下载特权免费下载专业文档。
阅读已结束,下载本文到电脑
几种特殊的图 哥尼斯堡七桥问题 哥尼斯堡城(现在俄罗斯)在18世纪属东普鲁士,它位于普雷格尔(Pregel)河畔,河中有两个岛,通过七座桥彼此相联,如下图: 内容提要 8.1 二部图 8.2 欧拉图与哈密尔顿图 8.3 平面图 8.1 二部图
,如下图所示。 8.1 二部图 由图显而易见, 分配a1去完成b1,a2去完成 B2,a3去完成b4,a4去完成 B3就能满足要求。 在此图中,a1,a2,a3,a4彼此 不相邻, b1,b2,b3,b4也彼此 不相邻。像这样的图,称它为二部图。 8.1 二部图 定义8.1.1 若能将无向图的顶点集V分成两个子集V1和V2(V1?V2=?),使得G中任何一条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图(或称偶图、双图、二分图),V1,V2称为互补顶点子集. 若G是二部图,也可将G记为G=。 又若V1中任一顶点与V2中任一顶点均有且仅有一条边相关联,则称二部图G为完全二部图。若|V1|=r,|V2|=s,则记完全二部图为Kr,s 8.1 二部图 8.2 欧拉图与哈密尔顿图 引例:哥尼斯堡七桥问题 如何不重复地走完七桥后回到起点? 8.2 欧拉图与哈密尔顿图 一、欧拉图 定义8.2.1 给定无孤立结点图G=,若存在一条通路,经过图中每条边一次且仅一次,该通路称作欧拉通路;若G中欧拉通路又是回路,则称它为G中的欧拉回路;具有欧拉回路的图称为欧拉图。 注意:只有欧拉通路无欧拉回路的图不是欧拉图。 8.2 欧拉图与哈密尔顿图 8.2 欧拉图与哈密尔顿图 定理8.2.1 无向图G具有一条欧拉通路,当且仅当G是连通的,且有零个或两个奇数度结点。 证明 必要性 设G具有欧拉通路,即有点边序列 v0e1v1e2v2…eiviei+1…ekvk,其中结点可能重复出现,但边不重复,因为欧拉通路经过所有图G的结点,故图G是连通的。 对任意一个不是端点(始点和终点)的结点vi,在欧拉通路中每当vi出现一次,必关联两条边,故vi虽可重复出现,但deg(vi)必是偶数。对于端点,若v0=vk,则d(v0)为偶数,即G中无奇数度结点;若端点v0与vk不同,则d(v0)为奇数,d(vk)为奇数,G中就有两个奇数度结点。 8.2 欧拉图与哈密尔顿图 充分性 若图G连通,有零个或两个奇数度结点,我们构造一条欧拉通路如下: (1)若有两个奇数度结点,则从其中的一个结点考试构造一条迹,即从v0出发经关联边e1“进入”v1,若deg(v1)为偶数,则可由v1再经关联边e2进入v2,如此进行下去,每边仅取一次。由于G是连通的,故必可到达另一奇数度结点停下,得到一条迹L: v0e1v1e2v2…eiviei+1…ekvk.若G中没有奇数度结点则从任一结点v0出发,用上述方法必可回到结点v0,得到上述一条闭迹L1. 8.2 欧拉图与哈密尔顿图 (2)若L1通过了G的所有边,则L1就是欧拉通路。 (3)若G中去掉L1后得到子图G’,则G’中每个结点度数为偶数,因为原来的图是连通的,故L1与G’至少有一个结点vi重合,在G’中由vi出发重复(1)的方法,得到闭迹L2. (4)当L1与L2组合在一起,如果恰是G,即得欧拉通路,否则重复(3)可得到闭迹L3,依此类推直到得到一条经过图G中所有边的欧拉通路。 8.2 欧拉图与哈密尔顿图 由于有了欧拉回路和欧拉通路的判别准则,因此哥尼斯堡七桥问题立即有了确切的否定答案,因为从上图中可以看到deg(A)=5,deg(B)=deg(C)=deg(D)=3,故欧拉回路必不存在。 8.2 欧拉图与哈密尔顿图 欧拉通路和欧拉回路的概念,可以推广到有向图中去。 定义8.2.2 给定有向图G,通过图中每边一次且仅一次的一条单向通路(回路),称作单向欧拉通路(回路)。 定理 8.2.2 有向图G具有一条单向欧拉回路,当且仅当是连通的,且每个结点入度等于出度。一个有向图G具有单向欧拉通路,当且仅当它是连通的,而且除两个结点之外,每个结点的入度等于出度,但这两个结点中,一个结点的入度比出度大1,另一个结点的入度比出度小1。 8.2 欧拉图与哈密尔顿图版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。