《离散数学7-1图概念7-2路与回路.ppt》由会员分享，可在线阅读，更多相关《离散数学7-1图概念7-2路与回路.ppt（60页珍藏版）》请在金锄头文库上搜索。
1、离离 散散 数数 学学Discrete Mathematics 山东科技大学山东科技大学信息科学与工程学院信息科学与工程学院1第七章第七章 图论图论n图论是近年来发展迅速而又应用广泛的图论是近年来发展迅速而又应用广泛的一门学科。本章主要讲授图论的基本概念一门学科。本章主要讲授图论的基本概念和定理。和定理。n图图论论：数数据据结结构构、操操作作系系统统、编编译译原原理理、计算机网络原理的基础计算机网络原理的基础n要要求求：熟熟练练掌掌握握图图的的基基本本概概念念和和定定理理并并能够进行简单应用。能够进行简单应用。27-1 图的基本概念图的基本概念本节要熟悉下列概念（本节要熟悉下列概念（26个）：
2、个）：图、图、 无向边、无向边、 有向边、有向边、 起始结点、起始结点、 终止结点、终止结点、无向图、无向图、有向图、有向图、 混合图、混合图、邻接点、邻接点、 邻接边、邻接边、孤立结点、孤立结点、零图、零图、平凡图、平凡图、结点的度数、结点的度数、图的图的最大度、最小度、最大度、最小度、结点的入度、结点的入度、 结点的出度、结点的出度、平行边、平行边、简单图、简单图、 完全图、完全图、补补图、图、 子子图、图、生成子图、生成子图、 子图的相对于图的补图、子图的相对于图的补图、图的图的同构同构多重图、多重图、3n图的定义图的定义n点的度数点的度数n特殊的图特殊的图n图同构图同构7-1 图的基本
3、概念图的基本概念4一、图的定义一、图的定义 定义定义7-1.1 图图（graph）G由一个三元组由一个三元组表示，其中：表示，其中： 非空集合非空集合V(G)=v1,v,v2 2, , ,v vr r 称为图称为图G的的结点集结点集，其成员其成员vi(i=1,2,r)称为称为结点结点或或顶点顶点（nodes or vertices）；）； 集合集合 E(G)=e1,e2,es 称为图称为图G的的边集边集，其成员，其成员ej(j=1,2,s)称为称为边边(edges)。 函数函数 G ：E(G)(V(G),V(G) ，称为边与顶点的称为边与顶点的关联映射关联映射（associatve mappi
4、ng） 5例例1：G=其中其中V(G)=a，b，c，d，E(G)=e1，e2，e3，e4，e5，e6， G(e1)=(a，b)， G(e2)=(a，c)， G(e3)=(b，d)， G(e4)=(b，c)， G(e5)=(d，c)， G(e6)=(a，d)abcde1e2e3e4e5e6 若把若把图中的边图中的边ej看作看作总是和两个结点关联，那么一个图亦简记总是和两个结点关联，那么一个图亦简记为为G= ，其中非空集合其中非空集合V称为图称为图G的的结点集结点集，集合，集合 E称为图称为图G的的边集边集。 若若边边ej与结点无序偶与结点无序偶(vj,vk)关联，那么称该边为无向边。关联，那么称
5、该边为无向边。 若若边边ej与结点序偶与结点序偶关联，那么称该边为有向边。关联，那么称该边为有向边。起始结点起始结点终止结点终止结点6例例2：G=其中其中V(G)=a，b，c，d，E(G)=e1，e2，e3，e4，e5，e6， G(e1)=(a，b)， G(e2)=(a，c)， G(e3)=(b，d)， G(e4)=(b，c)， G(e5)=(d，c)， G(e6)=(a，d)一个图与结点、连接结点的边、边与结点的关联有关。72、有向边、有向边&无向边无向边n无向边：如果无向边：如果E中边中边ei对应对应V中的结点对是无中的结点对是无序的序的(u，v)称称ei是无向边，记是无向边，记ei=(u
6、，v)，称，称u，v是是ei的两个端点。的两个端点。n有向边：如果有向边：如果ei与结点有序对与结点有序对相对应，相对应，称称ei是有向边，记是有向边，记ei=，称，称u为为ei的始点，的始点，v为为ei的终点。的终点。83、图的分类：、图的分类：无向图：每条边均为无向边的图称为无向图。无向图：每条边均为无向边的图称为无向图。有向图：每条边均为有向边的图称为有向图。有向图：每条边均为有向边的图称为有向图。混合图：有些边是无向边，有些边是有向边的图混合图：有些边是无向边，有些边是有向边的图称为混合图。称为混合图。V1v1v4v5v1v2v3v4V2V3V4(a)无向无向图图(b)有向有向图图(
7、c ) 混合图混合图(孤立点孤立点)v2v3环环94、点和边的关联：如、点和边的关联：如ei=(u，v)或或ei=称称u，v与与ei关联。关联。5、点与点的相邻：关联于同一条边的结点称为邻接、点与点的相邻：关联于同一条边的结点称为邻接点。点。6、边与边的邻接：关联于同一结点的边称为邻接、边与边的邻接：关联于同一结点的边称为邻接边。边。7、孤立结点：不与任何结点相邻接的结点称为孤、孤立结点：不与任何结点相邻接的结点称为孤立结点。立结点。8、零图：仅有孤立结点的图。、零图：仅有孤立结点的图。9、平凡图：仅有一个孤立结点的图。、平凡图：仅有一个孤立结点的图。1110、自回路、自回路(环环)：关联于同
8、一结点的边称为自回：关联于同一结点的边称为自回路，或称为环。路，或称为环。11、平行边：在有向图中，始点和终点均相同的边、平行边：在有向图中，始点和终点均相同的边称为平行边，无向图中若两点间有多条边，称这些称为平行边，无向图中若两点间有多条边，称这些边为平行边，两点间平行边的条数称为边的重数。边为平行边，两点间平行边的条数称为边的重数。12n图的定义图的定义n点的度数点的度数n特殊的图特殊的图n图同构图同构7-1 图的基本概念图的基本概念13二、点的度数二、点的度数1、点的度数的定义、点的度数的定义定义定义7-1.2：在图：在图G=，v V，与，与结点结点v关联的边数称为关联的边数称为该点的度
9、数，记为该点的度数，记为deg(v)。孤立结点的度数为孤立结点的度数为0。2、出度与入度出度与入度定义定义7-1.3：在：在有向图有向图中，中，v V，n以以v为始点的边数称为该结点的出度，记作为始点的边数称为该结点的出度，记作deg+(v);n以以v为终点的边数称为该结点的入度，记作为终点的边数称为该结点的入度，记作deg-(v)。显然有显然有deg(v)=deg+(v)+deg-(v)14如：如：G1是无向图，是无向图，deg(v1)=3，deg(v2)=1G2是有向图，是有向图，deg+(v1)=3，deg-(v1)=2，deg(v1)=5，v1v2G1v1v3v4v2G2153、最大度
10、和最小度：、最大度和最小度：图图G最大度记为最大度记为 (G)=maxdeg(v)|v V(G)，最小度数记为最小度数记为 (G)=mindeg(v)|v V(G)。4、定理定理7-1.1：每个图中，结点度数总和等于边数的两倍。：每个图中，结点度数总和等于边数的两倍。即即 deg(v)=2|E| v V 该定理又称该定理又称握手定理握手定理证明证明 因为每条边必关联两个结点，而一条边给予关联因为每条边必关联两个结点，而一条边给予关联的每个结点的度数为的每个结点的度数为1。因此在。因此在每个图中，结点度数总每个图中，结点度数总和等于边数的两倍。和等于边数的两倍。16 5、定理、定理7-1.2 在
11、任何在任何在任何在任何图中图中, 度数为奇数的结点必度数为奇数的结点必定是偶数个。定是偶数个。 证明：设证明：设G G中奇数度结点集合为中奇数度结点集合为V V1 1, ,偶数度结点集合偶数度结点集合为为V V2 2，则有：则有： deg(v)+ deg(v) = deg(v) =2|E| v V1 v V2 v V由于由于 deg(v)是是偶数偶数之和必为偶数，而之和必为偶数，而2|E|是偶数，是偶数， v V2故得故得 deg(v)是偶数，而各个是偶数，而各个deg(vi) (vi V1 )是是奇数奇数， v V1这就要求偶数个这就要求偶数个deg(vi)求和，即求和，即|V V1 1|是
12、偶数。是偶数。 176、定理、定理7-1.3：在任何有向图中，所有结点的入度：在任何有向图中，所有结点的入度之和等于所有结点的出度之和之和等于所有结点的出度之和， 且均等于边数且均等于边数。证明证明 因为每一条有向边必对应一个入度和一个因为每一条有向边必对应一个入度和一个出度，若一个结点具有一个入度或出度，则必关出度，若一个结点具有一个入度或出度，则必关联一条有向边，所以联一条有向边，所以有向图中，各结点入度之和有向图中，各结点入度之和等于边数，各结点出度之和也等于边数等于边数，各结点出度之和也等于边数 。因此，。因此，在任何有向图中，所有结点的入度之和等于所有在任何有向图中，所有结点的入度之
13、和等于所有结点的出度之和。结点的出度之和。18n图的定义图的定义n点的度数点的度数n特殊的图特殊的图n图同构图同构7-1 图的基本概念图的基本概念19三、特殊的图三、特殊的图1、多重图、多重图定义定义7-1.4：含有平行边的图称为多重图。：含有平行边的图称为多重图。2、简单图：不含平行边和环的图称为简单图。、简单图：不含平行边和环的图称为简单图。3、完全图、完全图定义定义7-1.5：简单图：简单图G=中，若每一对结点中，若每一对结点间均有边相连，则称该图为完全图。间均有边相连，则称该图为完全图。有有n个结点的无向完全图记为个结点的无向完全图记为Kn。无向完全图：每一条边都是无向边无向完全图：每
14、一条边都是无向边 不含有平行边和环不含有平行边和环 每一对结点间都有边相连每一对结点间都有边相连20如果在如果在Kn中，对每一条边任意确定一个方向，则称中，对每一条边任意确定一个方向，则称该图为该图为n个结点的有向完全图。个结点的有向完全图。显然它的边数为显然它的边数为n(n-1)/2。 定理定理7-1.4 在任何在任何在任何在任何图中图中, n个结点的无向完全图个结点的无向完全图Kn的边数为的边数为n(n-1)/2。 证明：证明： n个结点中任取两个结点的组合数为个结点中任取两个结点的组合数为 Cn2 = = n(n-1)/2故的边数为故的边数为 |E| = n(n-1)/2 215、相对于
15、完全图的补图相对于完全图的补图定义定义7-1.6：给定一个简单图：给定一个简单图G，由，由G中所有结点和所有能使中所有结点和所有能使G成为完全图的添加边组成的图，称为成为完全图的添加边组成的图，称为G的相对于完全图的补的相对于完全图的补图，或简称为图，或简称为G的补图，记为的补图，记为 G。即。即G=， G=，其中其中E2=(u，v)u，v V，(u，v) E1。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全图完全图K5(b)图图G(c)图图G的补图的补图G226、子图、子图定义定义7-1.7：设图：设图G=，如果有图如果有图G=，且，且E E，V V，则称则称G为为G
16、的的子图。子图。 当当V=V时，则称时，则称G为为G的生成子图。的生成子图。例如，下图，例如，下图， 图图(b)的的G和图和图(c)的的G 都是图都是图(a)的的K5的子图。的子图。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全图完全图K5(b)图图G(c)图图G的补图的补图G237、相对于图相对于图G的补图的补图定义定义7-1.8：设设G=是是G=的子图，若的子图，若给定另一给定另一个图个图G”=使得使得E”=E-E，且，且V”中仅包含中仅包含E”的边所关的边所关联的结点，则称联的结点，则称G”是子图是子图G相对于图相对于图G的补图。的补图。例如，上图例如，上图(b)
17、的的G是图是图(c)的的G 相对于图相对于图(a)的的K5的补图。的补图。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全图完全图K5(b)图图G(c)图图G的补图的补图G24n图的定义图的定义n点的度数点的度数n特殊的图特殊的图n图同构图同构7-1 图的基本概念图的基本概念25四、同构四、同构定义定义7-1.9：设图：设图G=及图及图G=，如果存在一一对应的映射如果存在一一对应的映射g：VV且且e=(vi，vj)(或或)是是G的一条边，当且仅当的一条边，当且仅当e=(g(vi)，g(vj)(或或)是是G的一条边，的一条边，则则称称G与与G同构，记作同构，记作G G。26
18、两图同构的一些必要条件：两图同构的一些必要条件：1.结点数目相同；结点数目相同；2.边数相等；边数相等；3.度数相同的结点数目相等。度数相同的结点数目相等。以上几个条件不是两个图同构的充分条件。以上几个条件不是两个图同构的充分条件。见见279页图页图7-1.10同构必须是结点和边分别存在一一对应。同构必须是结点和边分别存在一一对应。27作业n279页:(5)（6）287-2 路与回路路与回路 在现实世界中，常常要考虑这样的问题：如在现实世界中，常常要考虑这样的问题：如何从一个图中的给定结点出发，沿着一些边连续何从一个图中的给定结点出发，沿着一些边连续移动而达到另一指定结点，这种依次由点和边组移
19、动而达到另一指定结点，这种依次由点和边组成的序列，就形成了路的概念。成的序列，就形成了路的概念。29学习本节要熟悉如下术语(22个)：路、路的长度、迹、回路、通路、圈、连通、连通分支、点割集、连通图、割点、点连通度、边割集、边连通度、割边、可达、单侧连通、 强连通、强分图、弱连通、弱分图、单侧分图掌握5个定理，一个推论。30n路路n无向图的连通性无向图的连通性n有向图的连通性有向图的连通性7-2 路与回路路与回路31一、路一、路 定义定义7-2.1 给定给定给定给定图图G=,设设 v0,v1,vn V， e1,en E, 其中其中ei是关联于结点是关联于结点vi-1,vi的边，交替序列的边，交
20、替序列v0e1v1e2envn称为结点称为结点v0到到vn的的路路（path） 。 v0和和vn分别称为路的分别称为路的起点起点和和终点终点，边的数目边的数目n称作路的称作路的长度长度。当当v0=vn时，这条路称作时，这条路称作回路回路 。若一条路中所有的边若一条路中所有的边e1, , en均不相同均不相同,称作称作迹迹 。若一条路中所有的结点若一条路中所有的结点v0, v1, vn均不相同均不相同,称作称作通路通路 。闭的通路闭的通路,即除即除v0=vn之外之外,其余结点均不相同的路其余结点均不相同的路,称作称作圈圈。32例如例如路：路：v1e2v3e3v2e3v3e4v2e6v5e7v3迹
21、：迹：v5e8v4e5v2e6v5e7v3e4v2通路：通路：v4e8v5e6v2e1v1e2v3圈：圈：v2e1v1e2v3e7v5e6v233n在简单图中一条路在简单图中一条路v0e1v1e2envn，由它的结由它的结点序列点序列v0，v1，vn确定，所以简单图的路，确定，所以简单图的路，可由其结点序列表示。可由其结点序列表示。n在有向图中，结点数大于在有向图中，结点数大于1的一条路亦可由边的一条路亦可由边序列序列e1e2en表示。表示。34 定理定理7-2.1 在一个具有在一个具有在一个具有在一个具有n个结点的图中，如果从结个结点的图中，如果从结点点vj到结点到结点vk存在一条路，则从结
22、点存在一条路，则从结点vj到结点到结点vk必存在必存在一条不多于一条不多于n-1条边的条边的路路。 证明思路：多于证明思路：多于n-1条边的路中必有重复出现的结条边的路中必有重复出现的结点，反复删去夹在两个重复结点之间的边之后，剩余点，反复删去夹在两个重复结点之间的边之后，剩余的边数不会超过的边数不会超过n-1条边条边。 35 定理定理7-2.1的证明的证明 如果从结点如果从结点vj到到vk存在一条路，该路上的结点存在一条路，该路上的结点序列是序列是vjvivk，如果在这条中有如果在这条中有l条边，则序列条边，则序列中必有中必有 l+1个个结点，若结点，若ln-1，则，则必有结点必有结点vs，
23、它在，它在序列中不止出现一次，即必有结点序列序列中不止出现一次，即必有结点序列vjvsvsvk，在路中，在路中去掉从去掉从vs到到vs的的这些边，仍这些边，仍是是vj到到vk的一条路，但此路比原来的路边数要少，的一条路，但此路比原来的路边数要少，如此重复进行下去，必可得到一条从如此重复进行下去，必可得到一条从vj到到vk的不多的不多于于n-1条边的路。条边的路。36 定理定理7-2.1 在一个具有在一个具有在一个具有在一个具有n个结点的图中，如果从结个结点的图中，如果从结点点vj到结点到结点vk存在一条路，则从结点存在一条路，则从结点vj到结点到结点vk必存在必存在一条不多于一条不多于n-1条
24、边的条边的路路。 推论推论 在一个具有在一个具有在一个具有在一个具有n个结点的图中，如果从结点个结点的图中，如果从结点vj到结点到结点vk存在一条路，则从结点存在一条路，则从结点vj到结点到结点vk必存在一条必存在一条边数小于边数小于n的的通路通路。37如在图如在图7-2.1中有中有5个结点。个结点。 v1到到v3的一条路为：的一条路为：v1e2v3e3v2e3v3e4v2e6v5e7v3此路中有此路中有6条条边，去掉边，去掉e3有路有路v1e2v3e4v2e6v5e7v3有有4条边。条边。v1到到v3最短的路为最短的路为v1e2v338n路路n无向图的连通性无向图的连通性n有向图的连通性有向
25、图的连通性7-2 路与回路路与回路39二、无向图的连通性：二、无向图的连通性：1、连通、连通 定义定义7-2.2 在无向在无向在无向在无向图图G中，如果从结点中，如果从结点u和结点和结点v之间若之间若存在一条路，则称结点存在一条路，则称结点u和结点和结点v是是连通的连通的（connected） 。 结点之间的连通性是结点集结点之间的连通性是结点集V上的等价关系，对上的等价关系，对应该等价关系，必可将作出一个划分，把应该等价关系，必可将作出一个划分，把V分成非空分成非空子集子集V1, V2, , Vm,使得两个结点使得两个结点vj和和vk是连通的，是连通的，当且仅当它们属于同一个当且仅当它们属于
26、同一个Vi 。把子图把子图G(V1) , G(V2) , , G(Vm)称为图称为图G的的连通分支连通分支（connected components）,图图G的连通分支数记为的连通分支数记为W(G) 。40412、连通图、连通图 定义定义7-2.3：若图：若图G只有一个连通分支，则称只有一个连通分支，则称G是连通图。是连通图。 显然在连通图中，任意两个结点之间必是连显然在连通图中，任意两个结点之间必是连通的。通的。42对于连通图，常常由于删除了图中的点或边，而影响了对于连通图，常常由于删除了图中的点或边，而影响了图的连通性。图的连通性。n n删除结点删除结点删除结点删除结点：所谓在图中删除：所
27、谓在图中删除：所谓在图中删除：所谓在图中删除结点结点v，即是把即是把v以及与以及与v关关联的边都删除。联的边都删除。删除边删除边删除边删除边：所谓在图中删除某条边所谓在图中删除某条边所谓在图中删除某条边所谓在图中删除某条边，即是把该边删除。，即是把该边删除。 v3v2v1v6v4(a)v5v5v1v2v3v6v4(c)ev3v2v6v4(b)v5e433、割点、割点定义定义7-2.4 设无向设无向设无向设无向图图G =是是连通图连通图,若有结点集若有结点集V1 V,使图使图G中中删除了删除了删除了删除了V1的所有结点后的所有结点后的所有结点后的所有结点后, ,所得到的子所得到的子所得到的子所得
28、到的子图是不连通图图是不连通图图是不连通图图是不连通图, ,而删除了而删除了而删除了而删除了V1的任何真子集后的任何真子集后的任何真子集后的任何真子集后, ,所得到所得到所得到所得到的子图仍是的子图仍是的子图仍是的子图仍是连通图连通图,则称则称V1是是G的一个的一个点割集点割集(cut-set of nodes) 。若某一个点构成一个点割集，则称该若某一个点构成一个点割集，则称该点为割点。点为割点。sabcdabcdba44点连通度：是为了产生一个不连通图需要删去的点的最点连通度：是为了产生一个不连通图需要删去的点的最少数目，也称为连通度，记为少数目，也称为连通度，记为k(G) 。即即k(G)
29、=min|V1| V1是是G的点割集的点割集 称为图称为图G的的点连通度点连通度(1)若若G是平凡图，则是平凡图，则V1= ，k(G)=0(2)k(Kn)=n-1(3)若图存在割点，则若图存在割点，则k(G)=1(4)规定非连通图的连通度规定非连通图的连通度k(G)=0v5v1v2v3v4v5v1v3v4点割集点割集V1=v2454、割边、割边 定义定义7-2.5 设无向设无向设无向设无向图图G =是是连通图连通图,若有边若有边集集E1 E E，使图使图 G中中删除了删除了删除了删除了E1的所有边后，所得到的的所有边后，所得到的的所有边后，所得到的的所有边后，所得到的子图是不连通图，而删除了子
30、图是不连通图，而删除了子图是不连通图，而删除了子图是不连通图，而删除了E1的任何真子集后，所得的任何真子集后，所得的任何真子集后，所得的任何真子集后，所得到的子图仍是到的子图仍是到的子图仍是到的子图仍是连通图，则称连通图，则称E1是是G的一个的一个边割集边割集(cut-set of edges) 。若某一条边就构成一个边割集，若某一条边就构成一个边割集，则称该边为则称该边为割边割边或或桥桥。 割边割边e使图使图G满足满足W(G-e)W(G) 。46 边边边边连通度连通度(edge-connectivity) (G)定义定义：非平：非平凡图的边连通度为凡图的边连通度为 (G)=min |E1|
31、| E1是是G G的边割集的边割集 边连通度边连通度 (G)是为了产生一个不连通图需要删是为了产生一个不连通图需要删去的边的最少数目。去的边的最少数目。(1)若若G是平凡图则是平凡图则E1= ，(G)=0(2)若若G存在割边，则存在割边，则 (G)=1， (3)规定非连通图的边连通度为规定非连通图的边连通度为 (G)=0475、定理定理7-2.2 对于任何一个对于任何一个对于任何一个对于任何一个图图G,有有k(G) (G)(G) 。在在7-2.2节定义了图节定义了图的的最小度：最小度： (G)=min(deg(v)，v V) 下面的定理给出了点连通度下面的定理给出了点连通度k(G) 、边连通度
32、边连通度 (G)和图的和图的最小度最小度 (G)之间的关系。之间的关系。282页图7- 2.3(a)k(G)=1,(G)=1,(G)=2282页图7- 2. 4k(G)=1,(G)=2,(G)=248证明：证明： 若若G不连通，则不连通，则k(G)= (G)=0，故上式成立。故上式成立。 若若G连通，连通，可分两步证明上式也成立：可分两步证明上式也成立： 1)先证明先证明 (G) (G)： 如果如果G是平凡图，则是平凡图，则 (G)=0 (G)， 若若G是非平凡图，则因每一结点的所有关联边必含一是非平凡图，则因每一结点的所有关联边必含一个边割集，个边割集，(因因 (G)=mindeg(v)|v
33、 V，设，设u V使的使的deg(u)=(G)，与，与u相关联的相关联的 条边必包含一个边割集，至条边必包含一个边割集，至少这少这 条边删除使图不连通。条边删除使图不连通。)故故 (G) (G)。5、定理定理7-2.2 对于任何一个对于任何一个对于任何一个对于任何一个图图G,有有k(G) (G)(G) 。492)再证再证k(G) (G)：(a)设设 (G)=1，即，即G有一割边，显然这时有一割边，显然这时k(G)=l，上式成立。上式成立。(b)设设 (G)2，则必可删去某则必可删去某 (G)条边，使条边，使G不连通，而删去不连通，而删去其中其中 (G)-1条边，它仍是连通的，且有一条桥条边，它
34、仍是连通的，且有一条桥e=(u，v)。对对 (G)-1条边中的每一条边都选取一个不同于条边中的每一条边都选取一个不同于u，v的端点，把的端点，把这些端点删去则必至少删去这些端点删去则必至少删去 (G)-1条边。若这样产生的图是不条边。若这样产生的图是不连通的，则连通的，则k(G) (G)-1 (G)，若这样产生的图是连通的，若这样产生的图是连通的，则则e仍是桥，此时再删去仍是桥，此时再删去u或或v就必产生一个不连通图，故就必产生一个不连通图，故k(G) (G)。由由1)和和2)得得k(G) (G) (G)。506.定理定理7-2.3 一个一个一个一个连通连通连通连通无向图无向图G的结点的结点v
35、是割点的充分必要条是割点的充分必要条件是存在两个结点件是存在两个结点u和和w,使得结点使得结点u和和w的每一条路都通过的每一条路都通过v 。 证明思路：证明思路： 1) 先证先证:v是割点是割点存在结点存在结点u和和w的每条路都通过的每条路都通过v 若若v是连通图是连通图G=割点，设删去割点，设删去v得到的子图得到的子图G , 则则G至少至少包含两个连通分支包含两个连通分支G1=和和G2= 。任取任取u V1，w V2，因为因为G是连通的，故在是连通的，故在G中必有一条连结中必有一条连结u和和w的路的路C，但但u和和w在在G中属于两个不同的连通分支，故中属于两个不同的连通分支，故u和和w必不连
36、通，因此必不连通，因此C必必须通过须通过v，故故u和和w之间的任意一条路都通过之间的任意一条路都通过v 。 2)再证再证:存在结点存在结点u和和w的每条路都通过的每条路都通过v v是割点是割点 若连通图若连通图G中的某两个结点的每一条路都通过中的某两个结点的每一条路都通过v，则删去则删去v得到子得到子图图G ，在，在G中这两个结点必然不连通，故中这两个结点必然不连通，故v是图是图G的割点。的割点。 51n路路n无向图的连通性无向图的连通性n有向图的连通性有向图的连通性7-2 路与回路路与回路52三、有向图的连通性：三、有向图的连通性：1、可达：、可达： 在无向图在无向图G中，从结点中，从结点u
37、到到v若存在一条路，则若存在一条路，则称结点称结点u到结点到结点v是可达的。是可达的。有向图的可达性：有向图的可达性：对于任何一个有向对于任何一个有向对于任何一个有向对于任何一个有向图图G=, 从从结点结点u u和到结点和到结点v v有一条路有一条路,称为从称为从u u可达可达v v。 可达性可达性(accesible),是结点集上的二元关系，是结点集上的二元关系，它是自反的和传递的，但是一般来说不是对称的。它是自反的和传递的，但是一般来说不是对称的。故可达性不是等价关系。故可达性不是等价关系。53 如果如果u可达可达v，它们之间可能不止一条路，在所有这它们之间可能不止一条路，在所有这些路中，
38、最短路的长度称为些路中，最短路的长度称为u和和v之间的距离（或短程线）之间的距离（或短程线），记作，记作d，它满足下列性质：它满足下列性质：nd0nd =0nd + d d 有关距离的概念对无向图也适用，把有关距离的概念对无向图也适用，把 D=max d, u,vV称作图的直径。称作图的直径。 如果从如果从u到到v是不可达的是不可达的，则通常写成则通常写成 d =注意：当注意：当u可达可达v，且，且v也也可达可达u时，时， d 不一定等于不一定等于d 542、定义定义7-2.6 n n 在简单有向在简单有向在简单有向在简单有向图图G中，任何一对结点中，任何一对结点间，至少有一个间，至少有一个
39、结点到另一个结点是可达的，则称这个图是结点到另一个结点是可达的，则称这个图是单侧连通单侧连通的的 。n如果对于图如果对于图G中的任何一对结点两者之间是相互可中的任何一对结点两者之间是相互可达的，则称这个图是达的，则称这个图是强连通强连通的。的。n如果在图如果在图G中略去边的方向，将它看成无向图后，中略去边的方向，将它看成无向图后，图是连通的，则称该图为图是连通的，则称该图为弱连通弱连通的。的。55显然，强连通图显然，强连通图单侧连通图单侧连通图弱连通图。而逆推均弱连通图。而逆推均不成立。不成立。v2v3v4v1(a)强连通强连通v2v3v4v1(b)单侧连通单侧连通v2v3v4v1(c)弱连通
40、弱连通56证明：充分性：如证明：充分性：如G中有一条有向回路，经过每一中有一条有向回路，经过每一点至少一次，则点至少一次，则G中任意两点中任意两点u，v V，u可以沿着可以沿着该有向回路的一部分的而到达该有向回路的一部分的而到达v，则，则G是强连通图。是强连通图。3、定理、定理7-2.4：一个有向图是强连通的充分必要条：一个有向图是强连通的充分必要条件是件是G有一个回路，它至少包含每个结点一次。有一个回路，它至少包含每个结点一次。必要性：任取必要性：任取u，v V，图，图G是强连通图，则是强连通图，则uv有有有向路，有向路，vu也有有向路，则也有有向路，则uvu构成了一个构成了一个有向回路，如
41、果该有向回路没有包含有向回路，如果该有向回路没有包含w，而，而uw，wu均有有向路，则均有有向路，则uvuwu又是一个有向又是一个有向回路，一直下去可以将图中所有的点均包含进去。回路，一直下去可以将图中所有的点均包含进去。574、定义、定义7-2.7：在简单有向图中，：在简单有向图中，n具有具有强连通强连通性质的性质的最大最大子图子图，称为强分图；，称为强分图；n具有单侧连通性质的最大子图，称为单侧分图；具有单侧连通性质的最大子图，称为单侧分图；n具有弱连通性质的最大子图，称为弱分图。具有弱连通性质的最大子图，称为弱分图。v4v2v3v1(b)v4v2v3v1(a)v558 定理定理7-2.5 在有向图在有向图在有向图在有向图G=中，它的每一个结点中，它的每一个结点中，它的每一个结点中，它的每一个结点位于且只位于一个强分图中。位于且只位于一个强分图中。位于且只位于一个强分图中。位于且只位于一个强分图中。证明思路：证明思路： 1 1) )先证先证: :每一个结点每一个结点每一个结点每一个结点必必位于一个强分图中。位于一个强分图中。位于一个强分图中。位于一个强分图中。 2)2)再证再证: :每一个结点每一个结点每一个结点每一个结点只只位于一个强分图中。位于一个强分图中。位于一个强分图中。位于一个强分图中。 59 作业n286287： (2)(3)(4)60
