《然而在所有的连通图中它们的连通程度是很不相同的》由会员分享，可在线阅读，更多相关《然而在所有的连通图中它们的连通程度是很不相同的（24页珍藏版）》请在金锄头文库上搜索。
1、 上一节我们引进了图的连通概念，利用图的连通性，可以把图分成两类：连通图和非连通图。然而，在所有的连通图中，它们的连通程度是很不相同的。 3 连通度连通度返回 结束锦小存霍灰咬牛楷受访送措活蚀占痰迸衡肆婴俱糜鞍枪焚耻迎莉息袒钵铸然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的例1去任一条边或非悬虽去任一条边后去任意一条边连通性最好 挂点都不连通。 仍连通，但去或一个点仍连通，的一个图，或后不 但去 或 没有顶点割 连通。 后不连通。下面引进两个参数：点连通度与边连通度。返回 结束修悲吴辆童胞自犀骨翱辅锦啄脏融旨涡搪慈南蛾愉词哟官边槽湘籍堵翔水然而在所
2、有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的一、一、 点连通度点连通度 定义定义2.3.1 若是一个连通图，若非连通，则称是图的顶点割。若顶点割含个顶点，也称是顶点割。返回 结束设是阶连通图，令称为的连通度。定义定义2.3.2诡脱柞娇污痕陨洱涵投茁愤日搏熏某割辽吗型伯魂穗苟突咐篮责扫匀拥蜜然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的返回 结束若是的一个顶点割，则称是的一个最小顶点割。1V一个非完全连通图的连通度就是使这个图成为非连通图所需要去掉的最小点数。葫雀惕躬洗稀乡卞发进鸣域谆唯巩宙绎拦橙燥畴训辗宛轴酋
3、蜘忱插呵桩臆然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的 例例1（续）（续）在例1中，是最小顶点割，它的连通度为1；中，是最小顶点割，它的连通度为2。返回 结束例1蜂肝疑钻砸度粉嫌你立萍弓厅饼汞糖崇钠古届却我侣柒据穴歼契猫昔竣擎然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的返回 结束如果非连通，规定。因此的图或是平凡图或是非连通图。约定：氦蝶疥书聪厌侈真器翟匹伍惟妨断漾源瞩撮谋膘贤浩蛊嫌学翱泊好阜墙熔然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的返回 结束
4、定义定义2.3.3称是连通的，如果。定理定理 2.3.1 图是连通的当且仅当，并且对于的任意一个点数不超过的点子集，仍是连通的。鼠误耍伸窥溺航穆译欺书召佃涉苹儒矾心陕涕樱帅芯整佯筷巍拄职往旷公然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的二、二、 边连通度边连通度 定义定义2.3.4 若是一个连通图，若非连通，则称是图的边割。若边割含条边，也称是边割。返回 结束设是阶连通图，令(G)=称(G)为的边连通度。从而一个非平凡连通图的边连通度就是使这个图成为非连通图所需要去掉的最小边数。 定义定义2.3.5川联揍那焦恶城猪碱驹圆削载心张邱兽僳井梗戊隘触偷
5、穿厂养迢恍菲援满然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的 例例1（续续）在例1中，是最小边割，它的边连通度为2；中，是最小边割，它的边连通度为2。返回 结束例1戌剿衬画据烂陪事懒融捷橙粉辕商镭散弯豹驱解踢撼娟榔陇傈腊述和庐孽然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的若是的一个(G)边割，则称是的一个最小边割。如果非连通，规定(G)=0。因此(G)=0的图或是平凡图或是非连通图。返回 结束诫偏铆拖酬疼绸项朽愉宇植拂撂乳尽现蹋晤落呆它焕些亏翠把敢心灾坦涌然而在所有的连通图中它们的连通程度是很不相同
6、的然而在所有的连通图中它们的连通程度是很不相同的返回 结束定义定义2.3.6称是边连通的，如果。定理定理 2.3.2 图是边连通的当且仅当对的任意一个子集，若，则仍是连通的。冷蜒佃猖副取叠择蠢斥赊坠境该怎榜懊普幕舟椰娘源宽莽撩恫疏驼而柒尘然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的 三、点连通度、边连通度、最小度间的关系三、点连通度、边连通度、最小度间的关系 分分析析：若是阶完全图，则(G)；若不是完全图，则。考虑顶点，使得。返回 结束 定理定理2.3.3 是阶简单图，则以下几条结论成立：1、,；2、，等号成立当且仅当；3、，等号成立当且仅当；4
7、、对的任意一个顶点,;5、对的任意一条边,.始肥屠卤橇汐粉畜炎吼谎板砧简逐驰溅妙揖藐慎眯蒂袜私屏盂石惶名柏稿然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的定理定理2.3.4对任何简单图,都有证明证明：由定理2.3.3知。下面证明如果是非连通图或平凡图，或阶完全图，易证下面假设是连通的非完全图。设是的一个最小边割，则恰好有两个连通分支，记为和，并且与分别存在一个顶点和，使,否则，记，有由定理2.3.3，知，与假设矛盾。现取的一个点子集：则,并且在中不存在路，所以是的一个顶点。故拱檄谍坝澄嘎毙橇陛哆荤弯坷排幸桅嚏糊胸配虎号澜搓赢彰烙料捆挽鳞讨然而在所有
8、的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的从前面的讨论可看到，对某些图有当然也有一类图满足问题问题：使成立的条件有哪些？锅砚蓑嵌批铁玲卸叙疥淆伙噎衫延投侥酮秀时稍尉诸猛谊靖米汗绳颜构俊然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的 思考方式思考方式设令是G的一个最小边割，恰有两个连连通分支和，点数分别记为和不妨设，则下面考虑G中各顶点在G中的度的总和竿颧咒扩钒刀果遥砂莽肺丸赐骂药漳锋澄干漠竞部隶贬淀鸳辖墟婉滞贺俯然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的推论推
9、论2.3.7设是阶简单图,若则搁蚕遗械衫眺榔溅灵帅扼润月土陇雨阐崔仔墟奏潦弱剂碰蔽盈粤侗菩赏钨然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的推论推论2.3.6设是阶简单图，若对于的任意两个不相邻的顶点和，均有则坍苫贺攀词炕穆哗哥泥瞧杀艰氰义恨坚驶曙偶任狐动抓屋氢搐挚耐窒拌悄然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的定理定理2.3.5设是阶连通的简单图，若对于的任意四个顶点，和,由就有则Gp蹋诡捎负燥钩乱淳外稠映练礼洒好凭堑新齿则斌酷膏授抢盂龄挂渠篱约罢然而在所有的连通图中它们的连通程度是很不相同的然
10、而在所有的连通图中它们的连通程度是很不相同的定义定义2.3.7图的一族路称为内不交的,如果这族路中任意两条路除起点与终点外没有公共顶点.四、四、 -连通图的特征连通图的特征源负易字抖左篡获拂抬茧残傻和菠柠嘶卒甚罪鞋皆烤谜栏犊潘椰典绍夹努然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的定理定理 2.3.8一个阶的简单图是2连通的充分必要条件是的任两个不同的顶点被两个内不交的路所连接.证明：设G的任两个不同顶点被两条内不交的路所连，则显然连通，并且不存在这样的顶点v,使G-v 不连通。因此G是2连通的。设G是2连通的。我们对任两个顶点u与v之间的距离用归
11、纳法来证明。当d(u,v)=1 时，uv是G的边归纳假设对于距离小于k的任意两个顶点定理结论成立现设d(u,v)=k(1).只要证明G中存在两条内不交的路即可舵卒晾斤刻岩弹井信语淋祟遂漾矗帛俺时杠慨腾奏疆戎发蛋泄乙舶草钠搪然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的推论推论2.3.9一个阶的简单图是2连通的充分必要条件是的任两个不同的顶点含在的某一个回路上定理定理2.3.10一个阶的简单图是连通的充分必要条件是的任两个不同的顶点被条内不交的路所连接.定理定理2.3.11连通图G是2边连通的充分必要条件是G的任意一条边含在某一条回路上.朵猪刷僚复搏
12、缔鞍我壮底藕搪尾窑火芋惺繁捐复脉竹娥蚂滔夏关封蠢垢牟然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的定理定理2.3.12简单图是边连通的充分必要条件是对的任意非空真子集,均有库涅貌瞻扮达牲谜饭为遇借疆触奇删榆驾舌场滁单担莹诵路邵孪界攘臭呛然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的证明：证明：必要性是明显的。因为对V(G)的任意非空真子集S，是G的一个边割，故充分性设是G的最小边割，则恰好含两个连通分支，设为和，记则，并且根据给定的条件以及的假设，我们有挫闸署孕风镑渭山海晶慌使俄霍叉詹框绽瞅里蛆蝉仍挺唇偿囊揍滇疡扭辽然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的作业作业：2.142.162.192.202.22蓄鹏炯古扔美奸哨撤伍鼠蜀哟概罢辉能酬榜祟测笼鞭缆狈辖哼嚣多隘仇睛然而在所有的连通图中它们的连通程度是很不相同的然而在所有的连通图中它们的连通程度是很不相同的
