离散数学回路与图的连通性ppt.pptx

离散数学回路与图的连通性21、简单通路、简单通路:如果通路中各边都不相同。如果通路中各边都不相同。如简单通路如简单通路:v1v2 v5 v6 v2 v3 v4长度为长度为6如简单回路如简单回路:v1v2 v3 v5 v2 v6 v1长度为长度为62、简单回路、简单回路:如果回路中各边都不相同。如果回路中各边都不相同。33、基本通路、基本通路:如果通路中各个顶点与边都不相同。如果通路中各个顶点与边都不相同。4、基本回路、基本回路(圈圈):如果回路中各个顶点与边都不相同。如果回路中各个顶点与边都不相同。如基本通路如基本通路:v1v6 v3 v4长度为长度为3如基本回路如基本回路:v1v6 v3 v2 v1显然显然,基本通路基本通路(回路回路)一定就是简单通路一定就是简单通路(回路回路)。反之不然。反之不然。4若通路若通路(回路回路)中有边重复出现中有边重复出现,则称为复杂通路则称为复杂通路(回路回路)、5关于通路与回路得几点说明关于通路与回路得几点说明n表示方法表示方法 用用顶顶点点与与边边得得交交替替序序列列(定定义义),如如=v0e1v1e2elvl 用边得序列用边得序列,如如=e1e2el 简单图中简单图中,用顶点得序列用顶点得序列,如如=v0v1vl 非非 简简 单单 图图 中中,可可 用用 混混 合合 表表 示示 法法,如如=v0v1e2v2e5v3v4v5n环就是长度为环就是长度为1得圈得圈,两条平行边构成长度两条平行边构成长度为为2得圈得圈、6在图在图G中中,如果如果A到到B存在一条通路存在一条通路,则称则称A到到B就是可达得。就是可达得。1、无向图得连通性、无向图得连通性如果无向图中如果无向图中,任意两点就是可达得任意两点就是可达得,图为连通图。否则为图为连通图。否则为不连通图。不连通图。当图就是不连通时当图就是不连通时,定就是由几个连通子图构成。称这样得定就是由几个连通子图构成。称这样得连连通图就是连通分支。通图就是连通分支。二、图得连通性二、图得连通性:7无向图得连通性无向图得连通性 设无向图设无向图G=,u与与v连通连通:若若u与与v之间有通路之间有通路、规定规定u与自身总连通与自身总连通、连连通通关关系系 R=|u,v V且且u v就就是是V上上得得等等价价关关系系连通图连通图:平凡图平凡图,任意两点都连通得图任意两点都连通得图连通分支连通分支:V关于关于R得等价类得导出子图得等价类得导出子图 设设V/R=V1,V2,Vk,GV1,GV2,GVk就就是是G得连通分支得连通分支,其个数记作其个数记作p(G)=k、G就是连通图就是连通图 p(G)=1若若G为非连通图为非连通图,则则P(G)2,在所有得在所有得n阶无向图中阶无向图中,n阶零图就是连通分支最多得其分支数为阶零图就是连通分支最多得其分支数为n、8设设 A=1,2,8,R=|x,yAxy(mod 3)即即:A上模上模3等价关系得关系图为等价关系得关系图为:上述关系图被分成三个互不连通得部分上述关系图被分成三个互不连通得部分,每部每部分中得数两两都有关系分中得数两两都有关系,不同部分得图无关系。不同部分得图无关系。9n【例例】求求证证:若若图图中中只只有有两两个个奇奇度度数数顶顶点点,则则二二顶顶点必连通。点必连通。n 证明证明 用反证法来证明。用反证法来证明。n 设设二二顶顶点点不不连连通通,则则她她们们必必分分属属两两个个不不同同得得连连通通分分支支,而而对对于于每每个个连连通通分分支支,作作为为G得得子子图图只只有有一一个个奇奇度度数数顶顶点点,余余者者均均为为偶偶度度数数顶顶点点,与与握握手手定定理理推推论论矛矛盾盾,因因此此,若若图图中中只只有有两两个个奇奇度度数数顶顶点点,则则二二顶顶点点必必连通。连通。10【例例】在在一一次次国国际际会会议议中中,由由七七人人组组成成得得小小组组a,b,c,d,e,f,g中中,a会会英英语语、阿阿拉拉伯伯语语;b会会英英语语、西西班班牙牙语语;c会会汉汉语语、俄俄语语;d会会日日语语、西西班班牙牙语语;e会会德德语语、汉汉语语与与法法语语;f会会日日语语、俄俄语语;g会会英英语语、法法语语与与德德语语。问问:她她们们中中间间任任何何二二人人就就是是否否均均可可对对话话(必必要要时时可可通通过过别别人人翻译翻译)？11n解解 用用顶顶点点代代表表人人,如如果果二二人人会会同同一一种种语语言言,则则在在代代表表二二人人得得顶顶点点间间连连边边,于于就就是是得得到到下下图图。问问题题归归结结为为:在在这这个个图图中中,任任何何两两个个顶顶点点间间就就是是否否都都存存在在着着通通路路？由由于于下下图图就就是是一一个个连连通通图图,因因此此,必必要要时时通通过过别别人人翻翻译译,她们中间任何二人均可对话。她们中间任何二人均可对话。大家学习辛苦了，还是要坚持继续保持安静继续保持安静13定理定理 在在n阶简单图阶简单图G,如果对如果对G得每对顶点得每对顶点u与与v,deg(u)+deg(v)n1,则则G就是连通图。就是连通图。证明证明 假设假设G不连通不连通,则则G至少有两个分图。至少有两个分图。设设其其中中一一个个分分图图含含有有q个个顶顶点点,而而其其余余各各分分图图共共含含有有n q个顶点。个顶点。在这两部分中各取一个顶点在这两部分中各取一个顶点u与与v,则则0deg(u)q 1,0deg(v)n q 1,因此因此deg(u)+deg(v)n 2,这与题设这与题设deg(u)+deg(v)n 1矛盾。矛盾。14无向图得短程线与距离无向图得短程线与距离u与与v之间得短程线之间得短程线:u与与v之间长度最短得通路之间长度最短得通路(u与与v连通连通)u与与v之间得距离之间得距离d(u,v):u与与v之间短程线得长度之间短程线得长度若若u与与v不连通不连通,规定规定d(u,v)=、性质性质:d(u,v)0,且且d(u,v)=0 u=v d(u,v)=d(v,u)d(u,v)+d(v,w)d(u,w)15n在实际问题中在实际问题中,除了考察一个图就是除了考察一个图就是否连通外否连通外,往往还要研究一个图连通往往还要研究一个图连通得程度得程度,作为某些系统得可靠性度量。作为某些系统得可靠性度量。n图得连通性在计算机网、通信网与图得连通性在计算机网、通信网与电力网等方面有着重要得应用。电力网等方面有着重要得应用。图得连通性得应用图得连通性得应用162、有向图得连通性、有向图得连通性对于有向图对于有向图,“图中任意两点都有通路相连图中任意两点都有通路相连”,这个要求很高这个要求很高,因为有向图虽然就是连在一起得因为有向图虽然就是连在一起得,但受到边得方向得限制但受到边得方向得限制,任意两点不一定有通路。任意两点不一定有通路。以下分三种情况讨论以下分三种情况讨论:171)强连通图强连通图:有向图中有向图中,任意任意A、B就是互为可达得。如图就是互为可达得。如图(a)2)单向连通图单向连通图:在有向图中在有向图中,任意两点任意两点A、B存在着存在着A到到B得通路得通路 或存在着或存在着B到到A得通路。如图得通路。如图(b)3)弱连通图弱连通图:在有向图中在有向图中,如果其底图就是无向连通图。如图如果其底图就是无向连通图。如图(c)显然显然:在有向图中在有向图中,如果有一条通过图中所有点得回路如果有一条通过图中所有点得回路,则此图就是强连通得。则此图就是强连通得。如果有一条通过图中所有点得通路如果有一条通过图中所有点得通路,则此图就是单向连通图。则此图就是单向连通图。(a)(b)(c)18单向连通图都就是弱连通图单向连通图都就是弱连通图,但弱连通图但弱连通图却不一定就是单向连通图。却不一定就是单向连通图。在弱连通图中在弱连通图中,存在这样得顶点存在这样得顶点A、B,从从A到到B不可达不可达,且从且从B 到到A也不可达。也不可达。强连通图既就是单向连通图强连通图既就是单向连通图,又就是弱连通图。又就是弱连通图。即即强连通强连通单向连通单向连通弱连通弱连通 19有向图得连通性有向图得连通性(续续)定定理理(强强连连通通判判别别法法)D强强连连通通当当且且仅仅当当D中中存存在在经经过过每个顶点至少一次得回路每个顶点至少一次得回路定定理理(单单向向连连通通判判别别法法)D单单向向连连通通当当且且仅仅当当D中中存存在在经过每个顶点至少一次得通路经过每个顶点至少一次得通路(1)(2)(3)例例 下图下图(1)强连通强连通,(2)单连通单连通,(3)弱连通弱连通20思考思考:判断下列图中哪些就是强连通图判断下列图中哪些就是强连通图,哪些就是单向连通图哪些就是单向连通图,哪些哪些 就是弱连通图。就是弱连通图。(a)(b)(d)(c)答案答案:(a),(d)就是强连通图就是强连通图,(b)就是单向连通图就是单向连通图,(c)就是弱连就是弱连通图通图、21有向图得有向图得短程线与距离短程线与距离u到到v得短程线得短程线:u到到v长度最短得通路长度最短得通路(u可达可达v)u与与v之间得距离之间得距离d:u到到v得短程线得长度得短程线得长度若若u不可达不可达v,规定规定d=、性质性质:d 0,且且d=0 u=v d+d d 注意注意:没有对称性没有对称性227、7 设设n阶无向简单图阶无向简单图G中中 ,问问 应为多少？应为多少？解：由于解：由于 ，说明，说明G中任何顶点中任何顶点v 的度数的度数而由于而由于G为简单图，于是为简单图，于是则有则有 ，因此，因此说明说明G中每个顶点得度数都为中每个顶点得度数都为n-1,于就是有于就是有说明说明G为为n-1阶正则图阶正则图,即即G为为n 阶完全图。阶完全图。237、8 一个一个n(n2)阶无向简单图阶无向简单图G中中,n为奇数为奇数,已知已知G中得中得r个奇数度顶点个奇数度顶点,问问G得补图得补图 有几个有几个奇数度顶点？奇数度顶点？解解:由于由于而而n为奇数为奇数,于就是于就是Kn中各顶点得度数中各顶点得度数n-1为偶数为偶数,对于对于，应有，应有 ，且，且由于由于n-1为偶数，所以为偶数，所以 同为奇数或同为奇数或同为偶数。同为偶数。因此因此G中的中的r个奇数度顶点，则个奇数度顶点，则 也有也有r r个个奇数度顶点。奇数度顶点。247、9 设设D就是就是n 阶有向简单图阶有向简单图,就是就是D得子图得子图,已知已知 得边数为得边数为 ,问问D得边数得边数m为多少？为多少？解：由于解：由于所以所以而而n阶有向简单图中，边数阶有向简单图中，边数于是于是说明说明D为为n阶有向完全图，且阶有向完全图，且