(1.3.2)--ch7-2离散数学离散数学.pdf

离离 散散 数数 学学 Discrete Mathematics 7-2 路与回路路与回路 一、路与回路一、路与回路 定义定义 7.2.1 给定图给定图G=,设设 其中其中ei是关联于结点是关联于结点vi-1和和vi的边，的边，称交替序列称交替序列 为连接为连接v0到到vn的的路路(径径),0 1 1 22nnv e v e ve v12,ne eeE 01,nv vvV v0和和vn分别称为路的分别称为路的起点起点与与终点终点.路中路中边的数目边的数目n称作路的称作路的长度长度;当当v0=vn时时,这条路称为这条路称为回路回路;若一条路中所有的若一条路中所有的边均不相同边均不相同,称之为称之为迹迹(简单路径简单路径).若一条路中所有的若一条路中所有的结点均不相同结点均不相同,称之为称之为通路通路(基本路径基本路径).一条回路一条回路,除除v0=vn外其余外其余结点均不相同结点均不相同,称之为称之为圈圈(基本回路基本回路).一条回路所经过的边均不相同一条回路所经过的边均不相同,称该回路为称该回路为闭迹闭迹(简单回路简单回路).注意注意:通路必定是迹通路必定是迹;圈必定是闭迹圈必定是闭迹.例例1.在下面的图中找出一条路在下面的图中找出一条路,一条迹一条迹,一条通路一条通路,一个圈一个圈.路路:迹迹:通路通路:圈圈:1 1 2 3 3 7 5vev e v e v1 2 3 3 2 4 3 7 5ve v e v e v e v1 2 3 3 2 6 5ve v e v e v1 1 2 3 3 2 1vev e v e v定理定理7-2.1 在一个有在一个有n个结点的图中个结点的图中,如果从结点如果从结点vj到结点到结点vk 存在一条路存在一条路,则从结点则从结点vj到到vk必存在一条边数不多于必存在一条边数不多于n-1的路的路.证明证明 如果从结点如果从结点vj到到vk 存在一条路存在一条路,该路上的结点序列是该路上的结点序列是 vjvi vk,如果这条路中有如果这条路中有l 条边条边,则该序列中必定有则该序列中必定有l+1个结点个结点.若若l n-1,则必有结点则必有结点vs,它序列中不止一次出现它序列中不止一次出现,即必有序列即必有序列 vjvsvsvk,在路中去掉从在路中去掉从vs到到vs 的边的边,仍是从仍是从vj到到vk的一条路的一条路.但此路比原来的路但此路比原来的路 边数要少边数要少.如此重复下去如此重复下去,必可得到一条从必可得到一条从vj到到vk的不多于的不多于n-1条边的路条边的路.推论推论.在一个有在一个有n个结点的图中个结点的图中,如果从结点如果从结点vj到结点到结点vk 存在存在 一条路一条路,那么从结点那么从结点vj到结点到结点vk必存在一条边数小于必存在一条边数小于n的通路的通路.始点始点a 终点终点b 回路回路 经过不同结点经过不同结点 圈圈/基本回路基本回路 a=b 通路通路/基本路径基本路径 迹迹/简单路径简单路径 经过的结点不同经过的结点不同 经过的边不同经过的边不同 闭迹闭迹/简单回路简单回路 经过不同边经过不同边 路与回路的思维形式注记图路与回路的思维形式注记图 二、无向图的连通性二、无向图的连通性 和和 之间若存在一条路之间若存在一条路,则称则称 定义定义7-2.2.在无向图在无向图G中中,结点结点 和结点和结点 是是连通的连通的.结点结点 uvuv规定每个结点到自身总是规定每个结点到自身总是连通连通的的.注：注：结点之间的连通性是结点集合结点之间的连通性是结点集合V上的一个等价关系上的一个等价关系.设设G是一个无向图是一个无向图,R是结点集是结点集V上上之间的连通关系之间的连通关系.设设 R 将将V(G)划分成个划分成个k(k1)等价类：等价类：由它们由它们 称为称为G的的连通分支连通分支(图图).图图G的连通分支的个数记为的连通分支的个数记为W(G)12,kV VV12(),(),()kG VG VG V导出的子图导出的子图 定义定义7-2.3 若图若图G只有一个连通分支只有一个连通分支,则称则称G是是连通图连通图.连通图连通图 非连通图非连通图 注注:在连通图中在连通图中,任意两个结点之间必是连通的任意两个结点之间必是连通的.定义定义1 从图从图G=中删去结点集中删去结点集 S 是指作是指作V-S以及从以及从 E中删去与中删去与S 中的全部结点相联结的边中的全部结点相联结的边而得到的子图而得到的子图,记作记作G-S;特别地特别地,当当S=v 时时,简记为简记为G-v;定义定义2 从图从图G=中删去边集中删去边集(或弧集或弧集)T是指作是指作E-T,且且T 中的全部边所关联的结点仍在中的全部边所关联的结点仍在V 中中而得到的子图而得到的子图,记作记作G-T;特别地特别地,当当T=e 时时,简记为简记为G-e;v5 v1 v2 v3 v6 v4(c)v3 v2 v1 v6 v4(a)v5 e v3 v2 v6 v4(b)v5 e 定义定义7-2.4 设无向图设无向图G=为一连通图为一连通图,若有点集若有点集V1 V,则称点集则称点集V1 使图使图G 删除了删除了V1中的所有结点中的所有结点后后,所得所得的的子图是子图是不连通图不连通图.而而 删除了删除了V1的任一真子集后的任一真子集后,得到的子图仍是得到的子图仍是连通图连通图.是图是图G的一个的一个点割集点割集.若点割集中恰只有一个结点若点割集中恰只有一个结点,则称该结点则称该结点为为割点割点.s a b c d a b c d(b)(a)v2,v7,v3,v4 为点割集为点割集;v3,v4为割点为割点;v2,v7,v3,v4 v1,v6,例例1.判断判断 是否为下图的点割集是否为下图的点割集.定义定义3 若若G不是完全图不是完全图,称称|V1|V1是是G的点割集的点割集()mink G 为图为图G的的点连通度点连通度(或连通度或连通度).规定规定 对于不连通图对于不连通图G,对于完全图对于完全图Kn,()1;nk Kn()0;k G 对于存在割点的连通图对于存在割点的连通图G,()1;k G 注注.连通度连通度k(G)是为了产生一个不连通图需要删去是为了产生一个不连通图需要删去点点的最少数目的最少数目.定理定理7-2.3 一个无向连通图一个无向连通图G中的结点中的结点v是图是图G的割点当且的割点当且仅当存在两个结点仅当存在两个结点 u和和 w,使得连接结点使得连接结点 u和和 w 的每一条路都的每一条路都通过结点通过结点v.证明证明 (充分性充分性)若连通图若连通图G中存在结点中存在结点u和和w,使得连接使得连接u和和w的每条的每条路都经过路都经过v,则在子图则在子图Gv中中u和和w必不连通必不连通,故故v是是G 割点割点.(必要性必要性)若若v是是G的割点的割点,则则Gv至少有两个连通分支至少有两个连通分支 G1和和G2.任取任取uV1,wV2,因为因为G连通连通,故在故在G中必有连接中必有连接u和和w的路的路，但但 u、w在在Gv中不连通中不连通,因此因此 必通过必通过 v,即即u和和w之间的任意路之间的任意路必经过必经过v.定义定义7-2.5 设无向图设无向图G=为一连通图为一连通图,若有边集若有边集E1 E,则称则称边边集集 E1 使图使图G 中删除了中删除了E1中的所有边中的所有边后后得得到的到的子图是子图是不连通图不连通图.而而 删除了删除了E1的任一真子集的任一真子集后得到的子图是后得到的子图是连通图连通图.是图是图G的一个的一个边边割集割集.若若边边割集中恰只有一个割集中恰只有一个边边,则称该则称该边为边为割割边边(或桥或桥).G的的割边割边也就是也就是G的一条边的一条边 e 使使得得满足满足W(G-e)W(G).e1e2e3e4e5e6e8e7e9v1v6v5v4v3v2v7e1,e2,e6,e1,e3,e4是边割集是边割集;e6为割边为割边;e1,e2,e6,e2,e4 e1,e3,e4,例例2.判断判断 是否为下图的边割集是否为下图的边割集.定义定义4 若若G 是非平凡图是非平凡图,称称|E1|E1是是G的边割集的边割集()minG 为图为图G的的边连通度边连通度.注注:边通度边通度(G)是为了产生一个不连通图需要删去是为了产生一个不连通图需要删去边的最少数目边的最少数目.规定规定 对于平凡图对于平凡图G,对于完全图对于完全图Kn,()1;nk Kn()0;G 对于存在割边的连通图对于存在割边的连通图G,()1;k G 说明说明:点连通度和边连通度反映了图的连通程度点连通度和边连通度反映了图的连通程度,k(G)和和(G)的值越大的值越大,说明图的连通性越好说明图的连通性越好.定理定理7-2.2 对任何一个图对任何一个图G 有有 k(G)(G)(G),其中其中k(G)是点连通度是点连通度,(G)是边连通度是边连通度,(G)是图的最小度是图的最小度.注注:下面的图中容易看出有下面的图中容易看出有 k(G)=2,(G)=3,(G)=4，这对定理这对定理7-2.2的结论也给出一个例证的结论也给出一个例证.证明证明 (1)若若G不连通或为平凡图不连通或为平凡图,则则 k(G)(G)0 (G).(2)若若G为完全图为完全图Kn,则则 k(G)(G)(G)n1.(3)其它情况其它情况,先证先证 (G)(G).由于度数最小的结点关联的边都删除后由于度数最小的结点关联的边都删除后,必使得必使得G不再连通不再连通,所以所以(G)(G).再证再证 k(G)(G).当在当在G中删除构成边割集的中删除构成边割集的(G)条边后条边后,G不连通不连通.现将这现将这(G)条边中取自不同边的条边中取自不同边的k(k (G)个不同的端点删个不同的端点删除后除后,G亦不连通亦不连通.因此因此 k(G)(G).无向图的连通性的思维形式注记图无向图的连通性的思维形式注记图 无向图无向图 所有所有 顶点顶点 连通连通 u v 存在路存在路 连通图连通图 删删 子图不连通子图不连通 删真子集删真子集 子图连通子图连通 删删 子图不连通子图不连通 删真子集删真子集 子图连通子图连通 顶点顶点 边边 点割集点割集 边割集边割集 点连通度点连通度 边连通度边连通度 定义定义5.在有向图在有向图G=中中,若从结点若从结点u到结点到结点v有一条路有一条路 相通相通,则称从结点则称从结点u到结点到结点v可达可达.三、有向图的连通性三、有向图的连通性 规定每个结点到自身总是规定每个结点到自身总是可达可达的的.注意注意:有向图上的有向图上的可达性可达性,是结点集上的二元关系是结点集上的二元关系,它是自反它是自反的和传递的的和传递的,但是一般来说不是对称的但是一般来说不是对称的.故可达性不是等价关系故可达性不是等价关系.定义定义6.若在一个有向图中从结点若在一个有向图中从结点 u 到到v 可达可达,则称从结点则称从结点 u 到结点到结点v的最短路的长度为结点的最短路的长度为结点 u 到结点到结点v的的距离距离(或短程线或短程线),它满足下列性质它满足下列性质:记为记为d.如果从结点如果从结点u 到到v不可达不可达,则记则记 d=.注意注意:1.当当u可达可达v,且且v也可达也可达u时时,d(u,v)不一定等于不一定等于d(v,u).(1)d(u,v)0;(2)d(u,u)=0;(3)d(u,v)+d(v,w)d(u,w).2.把把 max(,),Dd u v u vV称为图称为图G的的直径直径.例例3.d(v1,v2)2,d(v2,v1)1.d(v1,v3)4,d(v3,v1)2.定义定义7-2.6 在在简单有向图简单有向图G中中，2)若若G的的任一对结点间任一对结点间都是相互可达的都是相互可达的,则称图则称图G是是强连通的强连通的;3)如果在图如果在图G中略去边的方向后中略去边的方向后,G成为连通的无向图成为连通的无向图,则称图则称图G是是弱连通的弱连通的.1)若任何一对结点间若任何一对结点间,至少有一个结点到另一个结点是可达至少有一个结点到另一个结点是可达的的,则称则称G是是单侧连通的单侧连通的;注注:强连通的也一定是单侧连通和弱连通的强连通的也一定是单侧连通和弱连通的.单向连通的一定是弱连通的单向连通的一定是弱连通的,但其逆均不真但其逆均不真.例例3 强连通强连通 单侧连通单侧连通 单侧连通单侧连通 弱连通弱连通 非连通图非连通图 定理定理 7-2.4 一个有向图一个有向图G是强连通的是强连通的,当且仅当当且仅当G中有一个中有一个回路回路,它至少包含每个结点一次它至少包含每个结点一次.证明证明:(充分性充分性)如如G 中有一回路中有一回路,它至少通过每个结点一次它至少通过每个结点一次,则则G中任意两个结点相互可达中任意两个结点相互可达,故故G是强连通的是强连通的.(必要性必要性)如有向图如有向图G是强连通的是强连通的,则任意两个结点相互可达则任意两个结点相互可达.设设Vv1,v2,vn,i 为为vi 到到vi+1的路的路,n 为为vn 到到v1的路的路,则则 1、2、n1、n 所围成的回路至少通过每个结点一次所围成的回路至少通过每个结点一次.定义定义 7-2.7 在在简单有向图简单有向图中中,具有强连通性质的具有强连通性质的最大子图最大子图 称为称为强分图强分图(强连通分支强连通分支);具有单侧连通性质的具有单侧连通性质的最大子图最大子图称为称为单侧分图单侧分图(单侧连通分支单侧连通分支);具有弱连通性质的具有弱连通性质的最大子图最大子图称为称为弱分图弱分图(弱连通分支弱连通分支).v4 v2 v3 v1 v5 由由1,2,3,4,5,6,7,8形成的诱导子图都是强分图形成的诱导子图都是强分图 由由1,2,3,4,5,5,6,7,8形成的诱导子图都是单侧分图形成的诱导子图都是单侧分图 由由1,2,3,4,5,6,7,8形成的诱导子图都是弱分图形成的诱导子图都是弱分图 证明证明 (1)设设vV,S是是G中所有与中所有与v相互可达的结点集合，相互可达的结点集合，由由S诱导的子图是诱导的子图是G的一个强分图的一个强分图,且包含结点且包含结点v.(2)若结点若结点v 位于两个不同的强分图位于两个不同的强分图S1和和S2中中,则则S1中每个结点中每个结点 与与v相互可达相互可达,v与与S2中每个结点也相互可达中每个结点也相互可达,于是于是S1中任一结点与中任一结点与S2中任一结点相互可达中任一结点相互可达,与与S1和和S2是强分图矛盾是强分图矛盾.所以所以,G的任一结点恰位于一个强分图中的任一结点恰位于一个强分图中.定理定理7-2.5 有向图有向图G=中中,它的每一个结点位于且只位它的每一个结点位于且只位于一个强分图中于一个强分图中.有向图的连通性的思维形式注记图有向图的连通性的思维形式注记图 有有 向向 图图 单侧连通单侧连通 强连通强连通 弱连通弱连通 无向图无向图 连通连通 略去方向略去方向 可可 达达 任意顶点任意顶点 至少有一个顶点至少有一个顶点 到另一个顶点到另一个顶点 充要条件充要条件 小小 结结 1.本节要熟悉如下术语本节要熟悉如下术语(23个个)：路、路、路的长度、路的长度、迹、迹、回路、回路、通路、通路、圈、圈、连通、连通、连通分支、连通分支、点割集、点割集、连通图、连通图、割点、割点、点连通度、点连通度、边割集、边割集、边连通度、边连通度、割边、割边、单侧连通、单侧连通、强连通、强连通、强分图、强分图、弱连通、弱连通、单侧分图、单侧分图、2.掌握掌握5个定理个定理,一个推论一个推论.可达、可达、弱分图弱分图.闭迹、闭迹、无向图无向图 有向图有向图 连连通通 可达可达 连通分支连通分支 无无向向连连通通图图 割点割点 点割集点割集 点连通度、边连通度点连通度、边连通度 割边割边 边割集边割集 始点始点 终点终点 图图 回路回路 路路 存在路存在路 k(G)(G)图的连通性的知识逻辑结构图图的连通性的知识逻辑结构图 有有向向连连通通图图 强连通强连通 强分图强分图 单侧连通单侧连通 单侧分图单侧分图 弱连通弱连通 弱分图弱分图