离散数学图论课件.ppt

1、l图论的内容十分丰富，应用相当广泛。许多学科图论的内容十分丰富，应用相当广泛。许多学科诸如诸如、计算机科、计算机科学等，都以图作为工具来解决实际问题和理论问题。学等，都以图作为工具来解决实际问题和理论问题。l它是它是等课程的先修内容。学习时应掌握等课程的先修内容。学习时应掌握好图论的好图论的、；善于把实；善于把实际问题际问题的问题，然后用图论的方法解决问的问题，然后用图论的方法解决问题。题。1 1、哥尼斯堡七桥问题、哥尼斯堡七桥问题2 2、环球周游问题、环球周游问题3 3、供应问题、供应问题l问：能否从某地出发，通过每桥恰好一次，走遍了七桥 后又返回到原处？l瑞士数学家在1736年发表了一篇论

2、文讨论这个问题，指出这个问题无解。普雷格尔河ABDCl问题转化成：图G中从某一结点出发找出一条路，它通过每条边恰好一次后回到原出发结点。l欧拉在这篇论文中提出了一条简单准则，确定七桥问题是不能解的。边代表桥每个点代表陆地l1859年，爱尔兰数学家哈密尔顿哈密尔顿爵士提出“环球周游”问题。l他用一个正十二面体的20个顶点代表世界上20个大城市(图(a)，这个正十二面体同构于一个平面图(图(b)。l要求旅游者能否找到沿着正十二面体的棱，从某个顶点(即城市)出发，经过每个顶点(即每座城市)恰好一次，然后回到出发顶点?这便是著名的问题。费城伦敦北京巴黎柏林不论怎么画，总有交叉点工工厂厂1 1工工厂厂2

3、 2工工厂厂3 3矿矿山山1 1矿矿山山2 2矿矿山山3 3每条每条边边代表一条专用代表一条专用l有三个工厂和三个矿山，要从每个工厂到每个矿山各修一条专用铁路。这些铁路能否在同一个平面上并且？l图论中把这样的图称为K3,3。平面图中将看到该问题无解。一、图论研究的对象：自然界和人类社会中包含二元关系二元关系的系统。二、图论研究的方法：1 1、将一个系统抽象为、将一个系统抽象为 +构成的图。构成的图。点表示点表示，边表示事物之间的，边表示事物之间的。2 2、根据图的、根据图的进行分析。进行分析。因此，图论中的因此，图论中的与人们通常熟悉的与人们通常熟悉的是不同的。是不同的。1 1、哥尼斯堡七桥问

4、题、哥尼斯堡七桥问题2 2、环球周游问题、环球周游问题3 3、供应问题、供应问题路与回路欧拉图与汉密尔顿图平面图对偶图与着色图的矩阵表示树与生成树一、定义：一个图是一个三元组,其中：V(G)=v1,v2,vn是一个非空的结点集合，E(G)=e1,e2,em是边集合，G是边 到结点（无序偶或有序偶）集合上的。即：对于任一个边对于任一个边ei E，都有，都有V中的一个点对中的一个点对(vi,vj)或或 与之对应与之对应。例1：G=，其中：V(G)=a,b,c,d,e,E(G)=e1,e2,e3,e4,e5,e6,a ab bc cd de ee1e2e3e4e5e6G(e1)=,G(e2)=,G(

5、e3)=,G(e4)=,G(e5)=,G(e6)=。1.1.与无序结点对相关联的边。与无序结点对相关联的边。2.2.与有序结点对相关联的边。与有序结点对相关联的边。3.3.关联于同一个结点的两条边。关联于同一个结点的两条边。4.4.连接同一对结点间的多条边。连接同一对结点间的多条边。5.5.关联同一结点的一条边。关联同一结点的一条边。6.6.关联一条边的两个结点。关联一条边的两个结点。7.7.不与任何结点相关联的结点。不与任何结点相关联的结点。abcde二、其它概念a零图零图bce平凡图平凡图二、其它概念8.8.仅由孤立结点组成的图仅由孤立结点组成的图9.9.仅由一个孤立结点构成的图仅由一个孤

6、立结点构成的图10.10.每一条边都是无向边的图每一条边都是无向边的图abcd无向图无向图11.11.每一条都是有向边的图每一条都是有向边的图12.12.即包括有向边也包括无向边的图即包括有向边也包括无向边的图13.13.含有平行边的图含有平行边的图14.14.不含有平行边和环的图不含有平行边和环的图15.15.每一对结点间都有边相连的每一对结点间都有边相连的有向图，简单图有向图，简单图c ca ab b多重图多重图/混合图混合图a ab bc cd d.e e混合图混合图a ab bc cK3K3无向完全图无向完全图a ab bc c二、其它概念16.16.与该结点相关联的边的数目与该结点相

7、关联的边的数目(每个环在其对应的结点上每个环在其对应的结点上度数增加度数增加2),2),记作deg(v)或d(v)；17.17.一个结点一个结点 射出的边的数目。射出的边的数目。记作18.18.射入一个结点射入一个结点 的边的数目。的边的数目。记作19.19.度数最大的点的度数度数最大的点的度数,记作:(G)=max d(v)|v V20.20.度数最小的点的度数度数最小的点的度数,记作:(G)=min d(v)|vV 点点a a的出度为的出度为1 1点点b b的入度为的入度为2 2 点点c c的度数为的度数为5 5 此图的最大度为此图的最大度为5 5（点（点c c的度数）的度数）此图的最小度

8、为此图的最小度为0 0（点（点e e的度数）的度数）二、其它概念abcde K K3 3无向完全图无向完全图a ab bc c21.21.在无向完全图中，给每条边确定一个方向后成为的图在无向完全图中，给每条边确定一个方向后成为的图K K3 3有向完全图有向完全图1 1a ab bc cK K3 3有向完全图有向完全图2 2a ab bc c二、其它概念任何图中，结点度数的总和等于边数的两倍，即：任何图中，结点度数的总和等于边数的两倍，即：deg(v)=2|E|deg(v)=2|E|，v v V V每条边关联两个点，每个边给每个点贡献的度数为每条边关联两个点，每个边给每个点贡献的度数为1 11

9、1条边条边-2-2个点个点22个度数。个度数。a ab bc cd d图图Ge ea ae ed de e边数边数度数度数1212n2n n2n 所以，度数的总和为边数所以，度数的总和为边数的两倍。的两倍。任何图中，度数为奇数的结点必是偶数个。任何图中，度数为奇数的结点必是偶数个。V为图为图G的结点集合，的结点集合，和和分别是分别是G中中和和的结点集合，根据定理的结点集合，根据定理1，有：，有：deg(v)v V1+deg(v)v V2=deg(v)v V=2|E|由于由于 deg(v)v V2 为偶数之和，必为偶数，而为偶数之和，必为偶数，而2|E|为偶数，为偶数，而而 deg(v)v V1

10、 为为|V1|个奇数相加之和，所以个奇数相加之和，所以|V1|必为偶数，即必为偶数，即:度数为奇数的结点必是偶数个。度数为奇数的结点必是偶数个。a ab bc cd de ef f图图G具有具有2个奇数点个奇数点聚会中成员之间相互握手，则与奇数个人握手的人数一定聚会中成员之间相互握手，则与奇数个人握手的人数一定是一个偶数，为什么？是一个偶数，为什么？解：采用解：采用结点结点表示表示人人，结点之间用，结点之间用边边相连，表示握手关系，相连，表示握手关系，1条边条边表示表示1次握手，通过这种方式，可以抽象成为一个次握手，通过这种方式，可以抽象成为一个简单无向图简单无向图，则与奇数个人握手的人对应的

11、结点的度数为则与奇数个人握手的人对应的结点的度数为奇数奇数，所以由定理，所以由定理2，可知此人数必为可知此人数必为偶数偶数。简单无向图简单无向图人人人人握手握手握手握手任何有向图中，所有点的入度之和等于所有点的出度之和。任何有向图中，所有点的入度之和等于所有点的出度之和。在有向图在有向图G中，每中，每一条有向边一条有向边对应一个对应一个入度入度和一个和一个出度出度，若一个若一个具有一个具有一个入度入度或或出度出度，则必关联一条有向边，即：边，则必关联一条有向边，即：边与与入度入度/出度出度是一一对应的；是一一对应的；a ab bc cd de ef f入度之和为入度之和为7=7=出度之和出度之

12、和 =边数边数a ab b1个个入入度度1个个出出度度每个每个的一个的一个入度入度/出度出度都是由一条边贡献的，也是一一对应的。都是由一条边贡献的，也是一一对应的。所以，有向图中各所以，有向图中各入度入度之和等于边数，各之和等于边数，各出度出度之和也等之和也等于边数，因此：于边数，因此：deg(v)-+v V=deg(v)+v V=|E|设图G有n个结点，n+1条边，证明G中至少有一个结点度数大于等于3。证明：假设所有结点度数都小于等于2。由于结点的度数总和：d(vi)=2|E|=2n 即：2(n+1)=2n，矛盾，故至少有一个结点度数大于等于3。a ab bc cd de ef fa ab

13、bc cabcdefn个结点的无向完全图个结点的无向完全图Kn的边数为的边数为:1/2 n(n-1)。证明：给定任何一个无向完全图证明：给定任何一个无向完全图G，设其边数为，设其边数为|E|。图图G中每个点的度数为中每个点的度数为n-1，则总度数为，则总度数为n(n-1)，根据定理，根据定理1 deg(v)=2|E|=n (n-1)，得：，得：|E|=1/2 n(n-1)。无向完全图无向完全图K K4 4无向完全图无向完全图K K5 5解：可以采用解：可以采用n个结点表示个结点表示n个药箱，放相同药的两个药箱对应结个药箱，放相同药的两个药箱对应结点之间连一条边，通过这种方式，可以得到一个点之间

14、连一条边，通过这种方式，可以得到一个Kn无向完全无向完全图，所以药的种类就是图，所以药的种类就是Kn的边数，有的边数，有1/2 n(n-1)种不同的药。种不同的药。药药箱箱1 1药药箱箱2 2药药箱箱i i药药箱箱k k药药箱箱3 3药药箱箱n nK Kn n无向完全图无向完全图定义定义:给定一个图给定一个图G，由，由和所有能使和所有能使G成为成为的的组成的图，称为组成的图，称为G的相对于完全图的补图，记做的相对于完全图的补图，记做G图图G G图图GG定义定义:设图设图G=,如果有图如果有图G1=,满足满足E1 E,V1 V,则称：则称：G1为为G的子图，若的子图，若G1包括包括G的所有结点，

15、则该子图称为的所有结点，则该子图称为G的生成子图。的生成子图。(a)(c)生成子图生成子图(d)生成子图生成子图(b)子图但不是生成子图子图但不是生成子图定义定义:G=是图G=的子图，若给定另外一个图G=使得E=E-E，且V中仅包含E的边所关联的结点，则称G是子图G图G的。G=G=G=G=是是G相对于相对于G的补图的补图那个是那个是G”相对于相对于G的补图的补图?定义定义:是否一样？是否一样？在图的定义中，强调的是、以及与点的，既没有涉及到联结两个结点的边的、和，也没有给出结点的或者规定。因此，给定的两个图，在它们的图形表示中（即在用小圆圈表示结点和用直线或曲线表示联结两个结点的边的图解中）可

16、能看起来很不一样，但实际上却是表示同一个图。因而，需要引入两图的同构概念。定义：设图G=和G=。若存在双射 g:V V，且e=(vi,vj)(或)是G的一条边，当且仅当e=(g(vi),g(vj)(或)是G的一条边，则称G与G同构，记为G1G2。由定义可以看出，两图同构的充要条件是：。例如：同构同构根据图的同构定义，可以给出图同构的必要条件如下：(1)结点数目相等；(2)边数相等；(3)度数相同的结点数目相等。同构同构根据图的同构定义，可以给出图同构的必要条件如下：(1)结点数目相等；(2)边数相等；(3)度数相同的结点数目相等。但这仅仅是必要条件而不是充分条件。例如：不同构不同构一、定义：一

17、个图是一个三元组,其中：V=v1,v2,vn是一个非空的结点集合，E=e1,e2,em是边集合，是边 到结点（无序偶或有序偶）集合上的。即：对于任一个边对于任一个边ei E，都有，都有V中的一中的一个点对个点对(vi,vj)或或 与之对应与之对应。三元组简写为G=。二、其它定义：u无向边、有向边、邻接边、平行边、环无向边、有向边、邻接边、平行边、环u邻接点、孤立结点邻接点、孤立结点u零图、平凡图、无向图、有向图、混合图、多重图、简单图、完全图零图、平凡图、无向图、有向图、混合图、多重图、简单图、完全图、有向完全图有向完全图u结点度数、出度、入度、图的最大度、图的最小度u子图、补图子图、补图u图

18、的同构图的同构三、定理1 1、任何图中，结点任何图中，结点等于等于的的2 2、任何图中，、任何图中，必是必是个。个。3 3、任何有向图中，所有点的、任何有向图中，所有点的所有点的所有点的。4 4、n n个结点的个结点的K Kn n的边数为的边数为:1/2 :1/2 n(n-1)n(n-1)。图的基本概念欧拉图与汉密尔顿图平面图对偶图与着色图的矩阵表示树与生成树 图论中，常常考虑从一个图论中，常常考虑从一个结点出发结点出发，沿，沿着一些着一些边连续移动边连续移动而达到另一个而达到另一个指定结点指定结点，这种依次由这种依次由点点和和边边组成的组成的序列序列就形成了就形成了路路的的概念。概念。路路与

19、与回路回路无向图无向图的的连通性连通性有向图有向图的的连通性连通性给定图给定图G=,v0,v1,vn V,e0,e1,en E,其中其中ei是关联于结点是关联于结点vi-1和和vi的边，则交替序列的边，则交替序列v0e1v1 e2,en vn 称为联结称为联结v0到到vn的的路路。若若v0vn，则这条路称为，则这条路称为回路回路。若一条路中所有边若一条路中所有边e0,e1,en均不相同，称为均不相同，称为迹迹；若一条路中所有点若一条路中所有点v0,v1,vn均不相同，称为均不相同，称为通路通路；除除v0vn外其余结点均不相同的路，称为外其余结点均不相同的路，称为圈圈。由定义可知，由定义可知，必

20、是必是，反之不一定成立。，反之不一定成立。的的可由其可由其表示。表示。路：路：v1 v1 e2 e2 v3 v3 v2 v2 v3 v3 e4 e4 v2 v2 e6 e6 v5 v5 e7 e7 v3v3：迹：迹：v5 v5 e8e8 v4 v4 e5e5 v2 v2 e6e6 v5 v5 e7e7 v3 v3 e4e4 v2v2v1v2v3v4v5e6e5e4e3e2e1e7e8路：点边序列路：点边序列 v1v2v3v4v5e6e5e4e3e2e1e7e8迹：边各不相同迹：边各不相同通路：通路：v4 e8 v5 e6 v2 e1 v1 e2 v3 圈：圈：e1 v1 e2 v3 e7 v5

21、 e6 v1v2v5e6e5e4e3e2e1e7e8通路通路v1v2v3v4v5e6e5e4e3e2e1e7e8圈圈vjvj+1vsvivk-1vk设在这条路中有设在这条路中有 l 条边，如果条边，如果l n-1，则命题得证。，则命题得证。否则，否则，l n-1，此路中必有此路中必有l+1个结点，设为个结点，设为 vj vj+1 vi vk 在一个具有在一个具有n n个结点的图中，如果从结点个结点的图中，如果从结点v vj j到结点到结点v vk k存在存在一条路，则从结点一条路，则从结点v vj j到结点到结点v vk k必然存在一条不多于必然存在一条不多于n-1n-1条边的路。条边的路。则

22、在这条路中必有一个结点设为则在这条路中必有一个结点设为vs不止一次出现。不止一次出现。去掉从去掉从vs到到vs的这些边后，这仍然是一条从的这些边后，这仍然是一条从vj到到vk的一条路，但边数少了，的一条路，但边数少了，如此重复进行，直到此序列中没有重复点，则可得到一个结点数目小于如此重复进行，直到此序列中没有重复点，则可得到一个结点数目小于等于等于n的点边序列，此序列就是一个长度不多于的点边序列，此序列就是一个长度不多于n-1的路。的路。vsvs+1在一个具有在一个具有n n个结点的图中，如果从结点个结点的图中，如果从结点vjvj到到结点结点vkvk存在一条路，则必然存在一条从存在一条路，则必

23、然存在一条从vjvj到到vkvk边数小于边数小于n n的通路。的通路。vjvj+1vsvk-1vkvs+1a ab bc cd de ee e1 1e e2 2e e3 3f fg g在无向图中，结点在无向图中，结点u u和结点和结点v v之间若存在一条路，则称结点之间若存在一条路，则称结点u u和和v v是是连通的连通的(结点结点u u到到u u本身规定为连通的本身规定为连通的)。点点a a到点到点d d有一条路有一条路:a:a e e1 1 b b e e2 2 c c e e3 3 d d，a a与与d d是连通的是连通的点点d d到点到点g g没有路，没有路，d d与与g g是不连通的

24、是不连通的39中，结点u和结点v之间若存在一条路，则称结点u和v是连通的。(结点u到u本身规定为连通的)。结点之间的连通性是结点集合V上的等价关系。该等价关系必可对结点 集V作出一个划分V1,Vm，使得两个结点vj和vk是连通的当且仅当 它们属于同一个Vi。G的连通子图G(V1)，G(V2)，G(Vm)称为图G的连通分支，而图G的 连通分支数记为W(G)；若图G只有一个连通分支，则称G是连通图。a ab bc cd de ee e1 1e e2 2e e3 3f fg ga a与与d d是连通的是连通的,d d与与g g是不连通的是不连通的G定义关系定义关系R=|a,b V,在在G中，中，a与

25、与b连通连通R=,此等价关系此等价关系R决定了决定了V的一个划分：的一个划分：S=a,b,c,d,e,f则可生成则可生成个图个图G的子图，如下：的子图，如下：a ab bc cd de ef f图图G=abG(V1)c cd de eG(V2)f fG(V3)a ab bc cd de e有一个连通分支有一个连通分支,为为连通图连通图不是连通图！不是连通图！G对于对于，常常由于删除了图中的，常常由于删除了图中的或或而而了图的了图的。l删除结点v，即把v以及与v关联的边都删去；l删除边e，仅需删去该边。例如：上面几个图删去点或边后，图变为不连通的。上面几个图删去点或边后，图变为不连通的。删除结点

26、删除结点d da ab bc ce e删除边删除边e ea ab bc cd de ee ea ab bc ce e设G=为连通图，若有点集V1V，使图G删除了V1的所有结点后，所得子图是不连通的，而删除了V1的任何后，所得到的子图仍是连通图，则称V1是G的一个。若某个构成一个，则称该结点为。为了产生一个不连通图需要删去的点的最少数目称为图G的，记为k(G)，即k(G)=min|V1|V1是G的点割集u采用点连通度在一定程度上表示图连通性的强弱；采用点连通度在一定程度上表示图连通性的强弱；u点连通度越大，说明连通性越好点连通度越大，说明连通性越好;u若若W(G)1,则则k(G)=?；有割点的连

27、通图k(G)=?。a ab bc cd de ef f1.a,b为一个点割集为一个点割集 （）2.a为一个点割集为一个点割集 （）3.a,b,f为一个点割集为一个点割集 （）4.a,f为一个点割集为一个点割集 （）5.f 为一个点割集为一个点割集 （）图图G删除了删除了V1的所有结点后，所得到的子图是不连通的，而删除了的所有结点后，所得到的子图是不连通的，而删除了V1的的任何真子集后，图仍然是连通的，则称任何真子集后，图仍然是连通的，则称V1是是G的一个点割集。的一个点割集。设G=为连通图，若有边集E1E，使图G删除了E1的所有边后，所得子图是不连通的，而删除了E1的任何真子集后，所得到的子图

28、仍是连通图，则称E1是G的一个。若某条边构成一个边割集，则称该边为（桥）。为了产生一个不连通图需要删去的边的最少数目称为图G的，记为(G)，即 (G)=min|E1|E1是G的边割集 a ab bc cd de ef fe e6 6e e5 5e e4 4e e3 3e e2 2e e1 1e e7 7e e8 8a ab bc cd de ee e6 6e e5 5e e4 4e e3 3e e2 2e e1 1e e7 7e e8 8e e9 9e1为割边或桥为割边或桥e4 e7 e8为割边集为割边集每一个每一个的所有关联边是否必然包含一个的所有关联边是否必然包含一个约定：约定：平凡图的边

29、连通度平凡图的边连通度=0。即即(平凡图)=0。为什么每一个结点的所有关联边必然包含一个为什么每一个结点的所有关联边必然包含一个证明：给定结点为证明：给定结点为v，v关联的边的集合设为关联的边的集合设为Ev=e1,e2,em。1、若、若Ev中存在桥中存在桥ei，则，则ei Ev是一个边割集是一个边割集;2、否则，转向、否则，转向3；3、任选两个边：、任选两个边：ei,ej,则共有则共有1/2 n(n-1)个组合，个组合，逐个验证每一个逐个验证每一个ei,ej是否构成边割集，若有，是否构成边割集，若有，则第一个满足边割集条件的则第一个满足边割集条件的ei,ej Ev是是一个边割集，结束；否则，转

30、向一个边割集，结束；否则，转向4；4、任选、任选3个边：个边：ei,ej,ek，过程同，过程同3；若没有，再任选；若没有，再任选4,5,n个边。个边。5、若上述过程都没有找到边割集，则、若上述过程都没有找到边割集，则Ev Ev必然是一个边割集。必然是一个边割集。命题得证：一个结点的所有关联边必然包含一个命题得证：一个结点的所有关联边必然包含一个。a ab bc cd de ee e6 6e e5 5e e4 4e e3 3e e2 2e e1 1e e7 7e e8 8e e9 9对于任何一个无向图对于任何一个无向图G，有：，有：k(G)(G)(G)，即，即连通度连通度 连通度连通度 G的的。

31、1、若、若G不连通不连通,则则k(G)=(G)=0，(G)0，上式成立；，上式成立；2、若、若G连通，连通，首先证明首先证明若若G是平凡图，则是平凡图，则(G)=0=(G)，满足，满足(G)(G)若若G不是平凡图，设结点不是平凡图，设结点u为度数最小的点，为度数最小的点，u的关联边集的关联边集合为合为E=e1,e2,em，则，则deg(u)=(G)=m。因为每一个结点的所有关联边必然包含一个因为每一个结点的所有关联边必然包含一个，设，设u包含的包含的边割集为边割集为Eg，所以，所以|Eg|(G)，即：，即：(G)|Eg|(G)。uv 若若G中有一个桥，则中有一个桥，则k(G)=(G)=1，成立

32、；成立；若没有桥，则若没有桥，则(G)2。设有一个边割集。设有一个边割集E1=e1,e2,ek，满足：，满足：(G)=|E1|=k,则在图则在图G中删除中删除E1中的中的k-1条边后，条边后，G仍然是连通的，剩仍然是连通的，剩余余一个桥设为一个桥设为ei,此边关联此边关联(u,v)点对。对于所删除的点对。对于所删除的k-1中的每个边都选中的每个边都选择择一个不同于一个不同于u,v的端点，设共有的端点，设共有m个，且个，且m最多等于最多等于k-1个，即个，即m (G)-1,删除这删除这m个点，至少删除个点，至少删除(G)-1条边，若删除这条边，若删除这m个点后：个点后：1、，则这，则这m个点中必

33、然包含个点中必然包含1个点割集。即：个点割集。即：k(G)m (G)-1 (G)，则再删除，则再删除u或或v，从而就删除，从而就删除m+1个点，其中个点，其中删删除除u或或v后，就是把剩余最后一个边就是桥也删除了，后，就是把剩余最后一个边就是桥也删除了，G必然变为不连必然变为不连通。通。即即m+1个点中必然包含个点中必然包含1个点割集。即：个点割集。即：k(G)m+1 (G)+1-1=(G)综上所述，综上所述，k(G)(G)证明完毕。证明完毕。uvs e1e2 tei对于任何一个图对于任何一个图G，有：，有：k(G)(G)(G)，即，即连通度连通度 连通度连通度 G的的。uvk(G)=2；(G

34、)=3；(G)=4满足：满足：k(G)(G)(G)一、交替序列交替序列v0e1v1 e2,en vn 称为联结称为联结v0到到vn的的路路。若若v0vn，则这条路称为，则这条路称为回路回路。迹、通路、圈迹、通路、圈二、中，结点之间的连通性是集合V上的等价关系。该等价关系对应结点集V的一个划分V1,Vm，使得两个结点vj和vk是连通的当且仅当它们属于同一个Vi。G的连通子图G(V1)，G(V2)，G(Vm)称为图G的连通分支，而图G的连通分支数记为W(G)；若图G只有一个连通分支，则称G是连通图。三、设G=为连通图，若有点集V1V，使图G删除了V1的所有结点后，所得子图是不连通的，而删除了V1的

35、任何后，所得到的子图仍是连通图，则称V1是G的一个。若某个构成一个，则称该结点为。为了产生一个不连通图需要删去的点的最少数目称为图G的，记为k(G)，即k(G)=min|V1|V1是G的点割集a ab bc cd de ef fuv四、设G=为连通图，若有边集E1E，使图G删除了E1的所有边后，所得子图是不连通的，而删除了E1的任何真子集后，所得到的子图仍是连通图，则称E1是G的一个。若某条边构成一个边割集，则称该边为（桥）。为了产生一个不连通图需要删去的边的最少数目称为图G的，记为(G)，即 (G)=min|E1|E1是G的边割集 a ab bc cd de ef fe e6 6e e5 5

36、e e4 4e e3 3e e2 2e e1 1e e7 7e e8 8a ab bc cd de ee e6 6e e5 5e e4 4e e3 3e e2 2e e1 1e e7 7e e8 8e e9 9e1为割边或桥为割边或桥e4 e7 e8为割边集为割边集对于任何一个图对于任何一个图G，有：，有：k(G)(G)(G)，即，即连通度连通度 连通度连通度 G的的。uvk(G)=2；(G)=3；(G)=4满足：满足：k(G)(G)(G)53一个连通一个连通G中的结点中的结点v是割点的充分必要条件是割点的充分必要条件是存在两个结点是存在两个结点s,t，使得结点，使得结点s和和t的每一条路都经

37、过的每一条路都经过v。证明：若结点v是G=的一个割点，设删去v得到子图G，则G中至少包含两个连通分支G1=，G2=。任取sV1，t V2，G为连通图，s,t在G中存在路:C1,C2,Ck。则每一条路必然通过v。假设Ci不经过v，则删除v后，s,t仍然可以通过Ci保持连通，s,t在两个连通分支中，所以，假设错误。Ci必通过结点v。故s,t之间任何一条路都通过v。若连通图G中某两个结点s和t的每一条路都通过v，则删去v后，得子图G，在G中这两个结点s,t无路相连，即不连通，于是G不连通，故v是G的割点。54设设G是是n个结点的个结点的简单图简单图，如果在，如果在G中每对结点的度数中每对结点的度数之

38、和大于等于之和大于等于n-1，则，则G是连通的。是连通的。假设G不连通，则G中有k个连通分支G1,Gi,Gj,Gk（k=2），设结点数分别为n1,ni,nj,nk，任取viGi，vj Gj，Gi,Gj都是简单图，deg(vi)=ni-1，deg(vj)=nj-1。ni+nj=n，deg(vi)+deg(vj)=ni-1+nj-1=ni+nj-2=n-1矛盾。所以，G是连通的55设G=是，从结点u到v有一条路，则称从u可达v；否则称不可达。可达关系是V中满足自反性和传递性的二元关系。如果u可达v，那么u到v中所有路中最短路的长度（边数）称作结点u和v之间的距离，记作d，满足下面性质：d 0；其中

39、，d =0；d+d d；若u,v可达，v,u可达时，d 不一定等于 d；u到v不可达，记为d=；D=max d称作图的直径。56在G中：如果任意一对结点之间相互可达，则称G是强连通的。任何一对结点间，若至少从一个顶点到另一个顶点是可达的，则称G是单向连通的；若将G看作无向图是连通的，则称G是弱连通的；例如：57一个有向图是一个有向图是的，当且仅当的，当且仅当G中有一个回路，中有一个回路，它至少包含每个结点一次。它至少包含每个结点一次。若有向图G=是强连通的 则任意两个结点u,v都是相互可达的。故u,v之间必可作k个回路（k=Cuv1,Cuv2,Cuvk,其中必有一个回路经过图中的所有结点。若不

40、然，sV，所有Cuvi都不包含s，则s肯定在另一条回路中中。因为G为强连通图，所以，u和m是相互可达的，即可以组成回路：，而该回路必然是中的1个，而且也包含s，但这与假设矛盾，所以，必然存在1个回路包含每个结点至少1次。若G中有一回路，至少包含每个结点一次，则G中任意两点都是相互可达的，故G是强连通的。58设G是有向图G的具有某种性质的子图，若无其他具有这种性质且真包含G的子图，则称G是具有该性质的极大子图。极大强连通子图G称为G的强分图；极大单向连通子图G称为G的单侧分图；极大弱连通子图G称为G的弱分图。例如：v1v3v2v5v4v1v2v4v3强分图:v1,v2,v3,v4v5单侧分图和弱

41、分图：v1,v2,v3,v4,v5强分图:v1,v2,v3,v4单侧分图：v1,v2,v3,v1,v3,v4弱分图：v1,v2,v3,v459在有向图在有向图G=中，它的每一个结点位于且仅位于中，它的每一个结点位于且仅位于一个强分图中。一个强分图中。1）证每一个结点必位于一个强分图中设v是G中任一结点，G1G1是G中所有与v相互可达的结点，以及只关联这些结点的所有边构成的子图子图，显然是包含v的一个。v是任意的，故每个结点必位于一个强分图中。2）证每一个结点只位于一个强分图中假设v位于两个不同的强分图G1,G2中，通过v，G1的每个结点与G2的每个结点相互可达，这与G1是强分图矛盾。综上所述，v包含在唯一的强分图中。6053,8v 作业作业