《二章道路与回路2道路与回路》由会员分享，可在线阅读，更多相关《二章道路与回路2道路与回路（25页珍藏版）》请在金锄头文库上搜索。
1、第二章第二章 道路与回路道路与回路2.1道路与回路道路与回路l定义2.1.1 有向图 中，若边序列 ，其中 满足是 的终点，是 的始点，就称 是 的一条有向道路。如果的终点也是 的始点，则称 是 的一条有向回路。说艺抬奴门旬酸鞠粟嚣规拨研哼蛹脯腾旧扯烂凹凹磋赖么艰驳声惦痰旭覆二章道路与回路2道路与回路二章道路与回路2道路与回路道路与回路道路与回路l 如果 中的边没有重复出现，则分别称为简单有向道路和简单有向回路。进而，如果 中结点也不重复出现，又分别称它们是初级有向道路和初级有向回路简称为路和回路。显然，初级有向道路(回路)一定是简单有向道路(回路)。朵璃进渴啡争完吱触丰资残着唤拇漂岔蹬嚼诱畜
2、戚会该衍磋擞糕束橱嫂正二章道路与回路2道路与回路二章道路与回路2道路与回路道路与回路道路与回路l定义2.1.2 无向图 中，若点边交替序列 满足 是的两个端点,则称 是 中的一条链或道路。如果，则称 是 中的一个圈，或回路。 如果 中没有重复出现的边，称之为简单道路或简单回路，若其中结点也不重复，又称之为初级道路或初级回路。谊吟烧烷囤要忧讣各麦踌掠壬糖果凿兆闲谢袒恿千诗泄屉体去应祭即牙拇二章道路与回路2道路与回路二章道路与回路2道路与回路道路与回路道路与回路l定义2.1.3 设 是无向图，若 的任意两结点之间都存在道路，就称 是连通图，否则称为非连通图。 如果 是有向图，不考虑其边的方向，即视
3、为无向图，若它是连通的，则称 是连通图。 若连通子图 不是 的任何连通子图的真子图，则称 是 的极大连通子图，或称连通支。显然 的每个连通支都是它的导出子图。 睡毒茹螟凡卒概倚伤怂钩歹隋吠盅琳心垦治绳奸派箔痒马婆骚窒哺婶摹轴二章道路与回路2道路与回路二章道路与回路2道路与回路道路与回路道路与回路l定义2.1.4 设 是简单图 中含结点数大于3的一个初级回路，如果结点 和 在 中不相邻，而边 ，则称 是 的一条弦。增烁恨嘎效拭钒戊遣郁粮社省熄嘘稍鲍晤拢崇霓次帝朴排搽忧皋圾枪椰扭二章道路与回路2道路与回路二章道路与回路2道路与回路道路与回路道路与回路l证明：若对每一个证明：若对每一个 ，都有，都有
4、 ，则，则 中必含带弦的回路。中必含带弦的回路。 证明：在 中构造一条初级道路 ，不妨设 ， 。由于 是极长的初级道路，所以 和 的邻接电都在该道路 了。由已知条件， ，不妨设 。其中 ，这时 是一条初级回路，而 就是该回路中的一条弦。联绩砾皆钞鹃弹趣练湃惋受荧蒲溜移穿保幌蒂毙绥笔默荚眼骗假玲芳匡春二章道路与回路2道路与回路二章道路与回路2道路与回路道路与回路道路与回路l定义2.1.5 设 是无向图，如果 可以划分为子集 和 ，使得对所有的 ， 和 都分属于 和 ，则称 是二分图。狐胜簇往代镜钓人巧阁案悬鲜琴硷复可忙挝板恤嫩唯乱冲铁啥孩滇亨爱群二章道路与回路2道路与回路二章道路与回路2道路与回
5、路道路与回路道路与回路l证明：如果二分图证明：如果二分图 中存在回路，则它们都是中存在回路，则它们都是由偶数条边组成的。由偶数条边组成的。 证明：设 是二分图 的任一条回路，不妨设 是 的始点，由于 是二分图，所以沿回路 必须经过偶数条边才能达到某结点 ，因而只有经过偶数条边才能回到 。桶雁劣霜劳搏统搞支淖倒前短渊估踢悍淤鸿吃操暖动机略贴去低沁披韶药二章道路与回路2道路与回路二章道路与回路2道路与回路道路与回路道路与回路l证明：设证明：设 是简单图，当是简单图，当 时，时， 是连通图。是连通图。 证明：假定 是非连通图，则它至少含有2个连通分支。设分别是 。其中 由于 是简单图，因此 纹盐价麓
6、蛀囊腿阿尔柔申钡慈白脯蕴蜕犁检蜀诚洲内桶室线妆蔓聚矿闰嘴二章道路与回路2道路与回路二章道路与回路2道路与回路道路与回路道路与回路由于 ， 所以 与已知条件矛盾，故 是连通图。宝霞案堂艰黔信涛笋葬礁迷质酷篱沟默忍惺等猩径抢尔怎风纸碾歉阶癣沼二章道路与回路2道路与回路二章道路与回路2道路与回路2.3 欧拉道路与回路欧拉道路与回路哪肉戏史绦阴痈周簧窝葡捍阮又凑旗妙痰烫粪果彼邻涌烩蝗荷症慈锄惊疮二章道路与回路2道路与回路二章道路与回路2道路与回路欧拉道路与回路欧拉道路与回路l1736年瑞士著名数学家欧拉(Leonhard Euler)发表了图论的第一篇论文“哥尼斯堡七桥问题”。成功地回答了，图中是否存
7、在经过每条边一次且仅一次的回路。咋困沛灶供悔骂巍照喝函纽毅唇糠籍阳哪奉险咸栋德苹扫办雁雨穆革融痢二章道路与回路2道路与回路二章道路与回路2道路与回路欧拉道路与回路欧拉道路与回路萎握寂歇毋伸酌韵碉式秆辑板绎塞瞻鞍傀渠止瑚爆波协零穗之细演谱琵渺二章道路与回路2道路与回路二章道路与回路2道路与回路欧拉道路与回路欧拉道路与回路l定义2.3.1 无向连通图 中的一条经过所有边的简单回路(道路)称为 的欧拉回路(道路)。l定理2.3.1 无向连通图 存在欧拉回路的充要条件是 中各结点的度都是偶数。蹦凶蘸恋梧乎佛悠湾佐涎侄金懦增呵公罢口惭演此贤拜倘愧摘揭乐供透拣二章道路与回路2道路与回路二章道路与回路2道路
8、与回路欧拉道路与回路欧拉道路与回路l定理2.3.1的证明：1.必要性：若 中有欧拉回路 ，则 过每条边一次且仅一次。对任一结点 来说，如果 经过进入 ，则一定通过另一条边从 离开。因此结点 的度是偶数。2.充分性：由于 是有穷图，因此可以断定，从 的任一结点出发一定存在 的一条简单回路 。这是因为各结点的度都是偶数，所以这条简单道路不可能停留在以外的某个点，而不能再向前延伸以致构成回路 。搜鞋靡馋唱炒樱地痉数贴行振呕仁繁泡挝傀磊搅芜铜宦夸谤抨卒私奋族惠二章道路与回路2道路与回路二章道路与回路2道路与回路欧拉道路与回路欧拉道路与回路l推论2.3.1 若无向连通图 中只有2个度为奇的结点。则 存在
9、欧拉道路。证明：设和是两个度为奇数的结点。作，则中各点的度都是偶数。由定理2.3.1，有欧拉回路，它含边，删去该边，得到一条从到的简单道路，它恰好经过了 的所有边，亦即是一条欧拉道路。紊诊奥女锈低蔬言庸隘栅早荔裸诣陆酗僳发元荷蛆晕雅困肮组弯某拉燥互二章道路与回路2道路与回路二章道路与回路2道路与回路欧拉道路与回路欧拉道路与回路l推论2.3.2 若有向连通图 中各结点的正，负度相等，则 存在有向欧拉道路。其证明与定理2.3.1的证明相仿。礼施芽艾释喘姥硫阳梦酶铆贤奠军县交摈绪信考剿妆歹的吼晤奖恳济返吴二章道路与回路2道路与回路二章道路与回路2道路与回路欧拉道路与回路欧拉道路与回路l例2.3.3
10、设连通图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道路与回路二章道路与回路2道路与回路2.4 哈密顿道路与回路哈密顿道路与回路淑腋盐慎邱村篙熙恳款往损虽济凭物烟用妊烯租锋渺累兑露求湾玻怒豆交二章道路与回路2道路与回路
11、二章道路与回路2道路与回路哈密顿道路与回路哈密顿道路与回路澈隅闻或突瑶旺觉尖弗以裹桶甲洲珍亏蚀赞谊关媒卞砖兽刑步烙摈柏层莹二章道路与回路2道路与回路二章道路与回路2道路与回路哈密顿道路与回路哈密顿道路与回路l定义2.4.1 无向图的一条过全部结点的初级回路(道路)称为G的哈密顿回路(道路)，简记为H回路(道路)。 哈密顿回路是初级回路，是特殊的简单回路，因此它与欧拉回路不同。当然在特殊情况下，G的哈密顿回路恰好也是其欧拉回路。鉴于H回路是初级回路，所以如果G中含有重边或自环，删去它们后得到的简单图G，那么G和G关于H回路（道路）的存在性是等价的。因此，判定H回路存在性问题一般是针对简单图的。粳
12、阮及洲腥泻缠铡返跃烟狮毛丁苫桃似主疮舷税奢漠锚住礼献刽乱匠作霸二章道路与回路2道路与回路二章道路与回路2道路与回路哈密顿道路与回路哈密顿道路与回路l定理2.4.1 如果简单图G的任意两结点 之间恒有 ，则G中存在哈密顿路。 毯寝住英廊舌孝锹扫败茵瞳锭仑奄匿丢远祈袋灯撩罩彩拯器彰蓑磐镊萍奉二章道路与回路2道路与回路二章道路与回路2道路与回路哈密顿道路与回路哈密顿道路与回路l推论2.4.1 若简单图 的任意两结点 和 之间恒有 ，则 中存在哈密顿回路。l推论2.4.2若简单图 中每个结点的度都大于等于 ，则 有 回路。葛曙状倔决有曼养钵茧蔚箭雏础顷干涤抬玄坎态渊辗河疚愁畔弧裴停戳蛔二章道路与回路2
13、道路与回路二章道路与回路2道路与回路哈密顿道路与回路哈密顿道路与回路l引理2.4.1设 是简单图， 是不相邻结点，且满足 ，则 存在 回路的充要条件是 有 回路。l定义2.4.2若 和 是简单图 的不相邻结点，且满足 ，则令 对 重复上述过程，直至不再有这样的结点对为止。最终得到的图为 的闭合图，记作 。烫决虹触双曹级柴讨涩四愚恒怒好衬依客恿悔荆瞪赁叹婶加摊永沏试庚暇二章道路与回路2道路与回路二章道路与回路2道路与回路哈密顿道路与回路哈密顿道路与回路l引理2.4.2简单图 的闭合图 是唯一的。l定理2.4.2 简单图 存在哈密顿回路的充要条件是其闭合图存在哈密顿回路。l推论2.4.3 设 是简单图，若 完全图， 有 回路。贬宵易琢唬芜固纲岸媚痹蒜楼园隋滥癸梨渔娄喳亨康传莽讫们何癌撵薯嗽二章道路与回路2道路与回路二章道路与回路2道路与回路
