时期图的基本概念ppt课件

资源描述

《时期图的基本概念ppt课件》由会员分享，可在线阅读，更多相关《时期图的基本概念ppt课件（76页珍藏版）》请在金锄头文库上搜索。

1、本章内容本章内容14.1 14.1 图图14.2 14.2 通路与回路通路与回路14.3 14.3 图的连通性图的连通性14.4 14.4 图的矩阵表示图的矩阵表示14.5 14.5 图的运算图的运算根本要求根本要求作业作业14.1 14.1 图的根本概念图的根本概念q图的定义图的定义q图的一些概念和规定图的一些概念和规定q简单图和多重图简单图和多重图q顶点的度数与握手定理顶点的度数与握手定理q图的同构图的同构q完全图与正那么图完全图与正那么图q子图与补图子图与补图无序无序无序无序积积与多重集合与多重集合与多重集合与多重集合 q设A A，B B为恣意的两个集合，称恣意的两个集合，称a,b|aA

2、bBa,b|aAbB为A A与与B B的无序的无序积，记作作A&BA&B。q可将无序可将无序积中的无序中的无序对a,ba,b记为(a,b)(a,b)，并且允，并且允许a ab b。q无无论a,ba,b能否相等，均有能否相等，均有(a,b)(a,b)(b,a)(b,a)，因此，因此A&BA&BB&AB&A。q元素可以反复出元素可以反复出现的集合称的集合称为多重集合或者多重集，某元多重集合或者多重集，某元素反复出素反复出现的次数称的次数称为该元素的反复度。元素的反复度。q例如例如在多重集合在多重集合a,a,b,b,b,c,da,a,b,b,b,c,d中，中，q a,b,c,d a,b,c,d的反

3、复度分的反复度分别为2,3,1,12,3,1,1。定定义14.1 14.1 一个无向一个无向图是一个有序的二元是一个有序的二元组V,E,记作作G G，其中，其中1 1VV称称为顶点集，其元素称点集，其元素称为顶点或点或结点。点。2 2E E称称为边集，它是无序集，它是无序积V&VV&V的多重子集，其元素称的多重子集，其元素称为无向无向边，简称称边。定定义14.2 14.2 一个有向一个有向图是一个有序的二元是一个有序的二元组VE，记作作D D，其中，其中1 1VV称称为顶点集，其元素称点集，其元素称为顶点或点或结点。点。2 2E E为边集，它是笛卡儿集，它是笛卡儿积VVVV的多重子集，其元素

4、称的多重子集，其元素称为有向有向边，简称称边。无向无向无向无向图图和有向和有向和有向和有向图图阐明阐明q可以用图形表示图，即用小圆圈或实心点表示顶可以用图形表示图，即用小圆圈或实心点表示顶点，用顶点之间的连线表示无向边，用有方向的连线点，用顶点之间的连线表示无向边，用有方向的连线表示有向边。表示有向边。例例例例14.114.114.114.1例例14.1 (1) 14.1 (1) 给定无向图给定无向图G G，其中，其中 V Vv1,v2,v3,v4,v5v1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v

5、E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5). 5). (2) (2) 给定有向图给定有向图D=D=，其中，其中 V Va,b,c,da,b,c,d，E E,。画出画出G G与与D D的图形。的图形。图图图图的一些概念和的一些概念和的一些概念和的一些概念和规规规规定定定定qG G表示无向图，但有时用表示无向图，但有时用G G泛指图泛指图( (无向的或有向的无向的或有向的) )。qD D只能表示有向图。只能表示有向图。qV(G)V(G)，E(G)E(G)分别表示分别表示G G的顶点集和边集。的顶点集和边集。q假设假设|V(G

6、)|V(G)|n n，那么称，那么称G G为为n n阶图。阶图。q假设假设|V(G)|V(G)|与与|E(G)|E(G)|均为有限数，那么称均为有限数，那么称G G为有限图。为有限图。 q假设边集假设边集E(G)E(G)，那么称，那么称G G为零图，此时，又假设为零图，此时，又假设G G为为n n阶图，阶图，那么称那么称G G为为n n阶零图，记作阶零图，记作NnNn，特别地，称，特别地，称N1N1为平凡图。为平凡图。 q在图的定义中规定顶点集在图的定义中规定顶点集V V为非空集，但在图的运算中能够产为非空集，但在图的运算中能够产生顶点集为空集的运算结果，为此规定顶点集为空集的图为空生顶点集为

7、空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记为图，并将空图记为。标定图与非标定图、基图标定图与非标定图、基图 q将图的集合定义转化成图形表示之后，常用将图的集合定义转化成图形表示之后，常用ekek表示无向边表示无向边(vi,vj)(vi,vj)或有向边或有向边，并称顶点或边用字母标定，并称顶点或边用字母标定的图为标定图，否那么称为非标定图。的图为标定图，否那么称为非标定图。q将有向图各有向边均改成无向边后的无向图称为原来图的将有向图各有向边均改成无向边后的无向图称为原来图的基图。基图。q易知标定图与非标定图是可以相互转化的，任何无向图易知标定图与非标定图是可以相互转化的，任何无

8、向图G G的各边均加上箭头就可以得到以的各边均加上箭头就可以得到以G G为基图的有向图。为基图的有向图。关联与关联次数、环、孤立点关联与关联次数、环、孤立点 q设G G为无向无向图，ekek(vi,vj)E(vi,vj)E，q称称vi,vjvi,vj为ekek的端点，的端点，ekek与与vivi或或ekek与与vjvj是彼此相关是彼此相关联的。的。q假假设vivjvivj，那么称，那么称ekek与与vivi或或ekek与与vjvj的关的关联次数次数为1 1。q假假设vivivjvj，那么称，那么称ekek与与vivi的关的关联次数次数为2 2，并称，并称ekek为环。q恣意的恣意的vlVvl

9、V，假，假设vlvivlvi且且vlvjvlvj，那么称，那么称ekek与与vlvl的关的关联次数次数为0 0。 q设D D为有向有向图，ekekEE，q称称vi,vjvi,vj为ekek的端点。的端点。q假假设vivivjvj，那么称，那么称ekek为D D中的中的环。q无无论在无向在无向图中中还是在有向是在有向图中，无中，无边关关联的的顶点均称点均称为孤立孤立点。点。相邻与邻接相邻与邻接 q设无向无向图G GVE，vivi，vjVvjV，ekek，elEelE。q假假设etEetE，使得，使得etet(vi(vi，vj)vj)，那么称，那么称vivi与与vjvj是相是相邻的。的。q假假设

10、ekek与与elel至少有一个公共端点，那么称至少有一个公共端点，那么称ekek与与elel是相是相邻的。的。 q设有向有向图D DVE，vivi，vjVvjV，ekek，elEelE。q假假设etEetE，使得，使得etetvivj，那么称，那么称vivi为etet的始的始点，点，vjvj为etet的的终点，并称点，并称vivi邻接到接到vjvj，vjvj邻接于接于vivi。q假假设ekek的的终点点为elel的始点，那么称的始点，那么称ekek与与elel相相邻。邻域邻域q设无向无向图G GVE，vVvV，q称称u|uV(u,v)Euvu|uV(u,v)Euv为v v的的邻域，域，记做做N

11、G(v)NG(v)。q称称NG(v)vNG(v)v为v v的的闭邻域，域，记做做NG(v)NG(v)。q称称e|eEee|eEe与与v v相关相关联为v v的关的关联集，集，记做做IG(v)IG(v)。q设有向有向图D DVE，vVvV，q称称u|uVEuvu|uVEuv为v v的后的后继元集，元集，记做做+D(v)+D(v)。q称称u|uVEuvu|uVEuv为v v的先的先驱元集，元集，记做做-D(v)-D(v)。q称称+D(v)-D(v)+D(v)-D(v)为v v的的邻域，域，记做做ND(v)ND(v)。q称称ND(v)vND(v)v为v v的的闭邻域，域，记做做ND(v)ND(v)

12、。举举举举例例例例NG(v1) NG(v1) +D(d ) +D(d ) v2v2，v5v5NG(v1) v1v1，v2v2，v5v5IG(v1) IG(v1) e1e1，e2e2，e3 e3 c c-D(d ) -D(d ) aa，ccND(d ) ND(d ) aa，ccND(d ) ND(d ) aa，c c，dd简单图与多重图简单图与多重图定义定义14.3 14.3 在无向图中，关联一对顶点的无向边假设多于在无向图中，关联一对顶点的无向边假设多于1 1条，条，那么称这些边为平行边，平行边的条数称为重数。那么称这些边为平行边，平行边的条数称为重数。在有向图中，关联一对顶点的有向边假设多

13、于在有向图中，关联一对顶点的有向边假设多于1 1条，并且这些条，并且这些边的始点和终点一样边的始点和终点一样( (也就是它们的方向一样也就是它们的方向一样) )，那么称这些，那么称这些边为平行边。边为平行边。含平行边的图称为多重图。含平行边的图称为多重图。既不含平行边也不含环的图称为简单图。既不含平行边也不含环的图称为简单图。例如：在图例如：在图14.114.1中，中，(a)(a)中中e5e5与与e6e6是平行边，是平行边，(b)(b)中中e2e2与与e3e3是平行边，但是平行边，但e6e6与与e7e7不是平行边。不是平行边。(a)(a)和和(b)(b)两个图都不是简单图。两个图都不是简单图。

14、顶点的度数顶点的度数定定义14.4 14.4 设G G为一无向一无向图，vVvV，称，称v v作作为边的端点的端点次数之和次数之和为v v的度数，的度数，简称称为度，度，记做做 dG(v) dG(v)。在不在不发生混淆生混淆时，简记为d(v)d(v)。设D DVE为有向有向图，vVvV，称称v v作作为边的始点次数之和的始点次数之和为v v的出度，的出度，记做做d+D(v)d+D(v)，简记作作d+(v)d+(v)。称称v v作作为边的的终点次数之和点次数之和为v v的入度，的入度，记做做d -D(v)d -D(v)，简记作作d-(v)d-(v)。称称d+(v)+d-(v)d+(v)+d-(v

16、)-(D)mind-(v)|vV(D)mind-(v)|vV(D)q称度数称度数为1 1的的顶点点为悬挂挂顶点，与它关点，与它关联的的边称称为悬挂挂边。度度为偶数偶数( (奇数奇数) )的的顶点称点称为偶度偶度( (奇度奇度) )顶点。点。图的度数举例图的度数举例d(v1)4(留意，留意，环环提供提供2度度)，4，1，v4是是悬悬挂挂顶顶点，点，e7是是悬悬挂挂边边。d+(a)4，d-(a)1(环环e1提供出度提供出度1，提供入度，提供入度1)，d(a)4+15。5，3，+4 (在在a点到达点到达)+0(在在b点到达点到达)-3(在在b点到达点到达)-1(在在a和和c点到达点到达) 握手定理

17、握手定理定理定理14.1 14.1 设G G为恣意无向恣意无向图，V Vv1,v2,vnv1,v2,vn，|E|E|m m，那么，那么阐明明任何无向任何无向图中，各中，各顶点度数之和等于点度数之和等于边数的两倍。数的两倍。证明明G G中每条中每条边( (包括包括环) )均有两个端点，均有两个端点，所以在所以在计算算G G中各中各顶点度数之和点度数之和时，每条每条边均提供均提供2 2度，当然，度，当然，m m条条边，共提供，共提供2m2m度。度。定理定理14.2 14.2 设D D为恣意有向恣意有向图，V Vv1,v2,vnv1,v2,vn，|E|E|m m，那么，那么握手定理的推论握手定理

19、能否能够每个人恰好与其他人恰好与其他5 5个人意见一致？个人意见一致？解答：不能够。思索一个图，其中顶点代表人，假设两个人意见解答：不能够。思索一个图，其中顶点代表人，假设两个人意见一样，可用边衔接，所以每个顶点都是奇数度。存在奇数个度一样，可用边衔接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不能够的。数为奇数的图，这是不能够的。阐明：阐明：(1)(1)很多离散问题可以用图模型求解。很多离散问题可以用图模型求解。(2)(2)为了建立一个图模型，需求决议顶点和边分别代表什么。为了建立一个图模型，需求决议顶点和边分别代表什么。(3)(3)在一个图模型中，边经常代表两个顶点之间的关系。

20、在一个图模型中，边经常代表两个顶点之间的关系。度数列度数列设G G为一个一个n n阶无向无向图，V Vv1,v2,vnv1,v2,vn，称，称d(v1)d(v1)，d(v2)d(v2)，d(vn)d(vn)为G G的度数列。的度数列。对于于顶点点标定的无向定的无向图，它的度数列是独一的。，它的度数列是独一的。反之，反之，对于于给定的非定的非负整数列整数列d dd1,d2,dnd1,d2,dn，假，假设存在存在V Vv1,v2,vnv1,v2,vn为顶点集的点集的n n阶无向无向图G G，使得，使得d(vi)d(vi)didi，那，那么称么称d d是可是可图化的。化的。特特别地，假地，假设所得所

21、得图是是简单图，那么称，那么称d d是可是可简单图化的。化的。类似地，似地，设D D为一个一个n n阶有向有向图，V Vv1,v2,vnv1,v2,vn，称，称d(v1)d(v1)，d(v2)d(v2)，d(vn)d(vn)为D D的度数列，另外称的度数列，另外称d+(v1)d+(v1)，d+(v2)d+(v2)，d+(vn)d+(vn)与与d-(v1)d-(v1)，d-(v2)d-(v2)，d-(vn)d-(vn)分分别为D D的出度列和入度列。的出度列和入度列。度数列举例度数列举例按按顶点的点的标定定顺序，度数列序，度数列为4,4,2,1,34,4,2,1,3。按字母按字母顺序，度数列，出

22、度列，入序，度数列，出度列，入度列分度列分别为5,3,3,35,3,3,34,0,2,14,0,2,11,3,1,21,3,1,2可图化的充要条件可图化的充要条件定理定理14.3 14.3 设非非负整数列整数列d d(d1(d1，d2d2，dn)dn)，那么，那么d d是可是可图化化的当且的当且仅当当证明明必要性。由握手定理必要性。由握手定理显然得然得证。充分性。由知条件可知，充分性。由知条件可知，d d中有偶数个奇数度点。中有偶数个奇数度点。奇数度点两两之奇数度点两两之间连一一边，剩余度用，剩余度用环来来实现。5331定理定理14.314.3的证明的证明由握手定理可知必然性由握手定理可知必

23、然性显然。然。下面下面证明充分性。明充分性。由知条件可知，由知条件可知，d d中有中有2k(0kn/2)2k(0kn/2)个奇数，个奇数，无妨无妨设它它们为d1d1，d2d2，dkdk，dk+1dk+1，dk+2dk+2，d2kd2k。可用多种方法做出可用多种方法做出n n阶无向无向图G G，V Vv1,v2,vnv1,v2,vn。比如比如边集如下集如下产生：在生：在顶点点vrvr与与vr+kvr+k之之间连边，r r1,2,k1,2,k。假假设didi为偶数，令偶数，令d di ididi，假，假设didi为奇数，令奇数，令d di idi-1di-1，得得d d(d(d1 1，d d2 2

24、，d dn)n)，那么，那么d di i均均为偶数。偶数。再在再在vivi处做出做出d di/2i/2条条环,i,i1,n1,n，将所得各将所得各边集合在一同集合在一同组成成E E，那么，那么G G的度数列的度数列为d d。其其实，didi为偶数偶数时，d(vi)d(vi)2d2di/2i/22di/22di/2didi，当当didi为奇数奇数时，d(vi)d(vi)1+2d1+2di/2i/21+d1+di i1+di-11+di-1didi，这就就证明了明了d d是可是可图化的。化的。可图化举例可图化举例由定理由定理14.314.3立刻可知，立刻可知，(3,3,2,1)(3,3,2,1)

25、，(3,2,2,1,1)(3,2,2,1,1)等是不可图化的，等是不可图化的，(3,3,2,2)(3,3,2,2)，(3,2,2,2,1)(3,2,2,2,1)等是可图化的。等是可图化的。定理定理14.414.4定理定理14.4 14.4 设G G为恣意恣意n n阶无向无向简单图，那么，那么(G)n-1(G)n-1。证明明由于由于G G既无平行既无平行边也无也无环，所以所以G G中任何中任何顶点点v v至多与其他的至多与其他的n-1n-1个个顶点均相点均相邻，于是于是d(v)n-1d(v)n-1，由于，由于v v的恣意性，所以的恣意性，所以(G)n-1(G)n-1。例例14.2 14.2

26、判判别以下各非以下各非负整数列哪些是可整数列哪些是可图化的？哪些是可化的？哪些是可简单图化的？化的？(1) (5,5,4,4,2,1)(1) (5,5,4,4,2,1)不可不可图化。化。(2) (5,4,3,2,2)(2) (5,4,3,2,2)可可图化，不可化，不可简单图化。假化。假设它可它可简单图化，化，设所得所得图为G G，那么，那么(G)(G)max5,4,3,2,2max5,4,3,2,25 5，这与定理与定理14.414.4矛盾。矛盾。例例14.214.2(3) (3,3,3,1)(3) (3,3,3,1)可图化，不可简单图化。假设该序列可以简单图化，可图化，不可简单图化。假设该

27、序列可以简单图化，设设G GVE以该序列为度数列。以该序列为度数列。无妨设无妨设V Vv1,v2,v3,v4v1,v2,v3,v4且且 d(v1) d(v1)d(v2)d(v2)d(v3)d(v3)3,d(v4)3,d(v4)1 1，由于由于d(v4)d(v4)1 1，因此，因此v4v4只能与只能与v1v1，v2v2，v3v3之一相邻，之一相邻，于是于是v1v1，v2v2，v3v3不能够都是不能够都是3 3度顶点，这是矛盾的，度顶点，这是矛盾的，因此因此(3)(3)中序列也不可简单图化。中序列也不可简单图化。 (4) (d1,d2,dn)(4) (d1,d2,dn)，d1d2dn1 d1d2d

28、n1 且且为偶数。偶数。可可图化，不可化，不可简单图化。化。例例14.214.2(5) (4,4,3,3,2,2) (5) (4,4,3,3,2,2) 可简单图化。以下图中两个可简单图化。以下图中两个6 6阶无向简单图都以阶无向简单图都以(5)(5)中序列为中序列为度数列。度数列。图的同构图的同构定定义14.5 14.5 设G1G1，G2G2为两个无向两个无向图，假假设存在双射函数存在双射函数f f：V1V2V1V2，对于于vi,vjV1vi,vjV1，(vi,vj)E1(vi,vj)E1当且当且仅当当(f(vi),f(vj)E2(f(vi),f(vj)E2，并且并且(vi,vj)(vi,

29、vj)与与(f(vi),f(vj)(f(vi),f(vj)的重数一的重数一样，那么称那么称G1G1与与G2G2是同构的，是同构的，记做做G1G2G1G2。阐明明(1) (1) 类似地，可以定似地，可以定义两个有向两个有向图的同构。的同构。(2) (2) 图的同构关系看成全体的同构关系看成全体图集合上的二元关系。集合上的二元关系。(3) (3) 图的同构关系是等价关系。的同构关系是等价关系。(4) (4) 在在图同构的意同构的意义下，下，图的数学定的数学定义与与图形表示形表示是一一是一一对应的。的。图的同构举例图的同构举例彼得森彼得森(Petersen)(Petersen)图完全图完全图定定

30、义14.6 14.6 设G G为n n阶无向无向简单图，假，假设G G中每个中每个顶点均与其他的点均与其他的n-n-1 1个个顶点相点相邻，那么称，那么称G G为n n阶无向完全无向完全图，简称称n n阶完全完全图，记做做Kn(n1)Kn(n1)。设D D为n n阶有向有向简单图，假，假设D D中每个中每个顶点都点都邻接到其他的接到其他的n-1n-1个个顶点，又点，又邻接于其他的接于其他的n-1n-1个个顶点，那么称点，那么称D D是是n n阶有向完全有向完全图。设D D为n n阶有向有向简单图，假，假设D D的基的基图为n n阶无向完全无向完全图KnKn，那么，那么称称D D是是n n阶竞

31、赛图。完全图举例完全图举例n阶阶无向完全无向完全图图的的边边数数为为：n(n-1)/2n阶阶有向完全有向完全图图的的边边数数为为：n(n-1)n阶竞赛图阶竞赛图的的边边数数为为：n(n-1)/2K53 3阶阶有向完全有向完全图图4 4阶竞赛图阶竞赛图正那么图正那么图定定义14.7 14.7 设G G为n n阶无向无向简单图，假，假设vV(G)vV(G)，均有，均有d(v)d(v)k k，那么称，那么称G G为k-k-正那么正那么图。举例例n n阶零零图是是0-0-正那么正那么图n n阶无向完全无向完全图是是(n-1)-(n-1)-正那么正那么图彼得森彼得森图是是3-3-正那么正那么图阐明明n

32、 n阶k-k-正那么正那么图中，中，边数数m mkn/2kn/2。当当k k为奇数奇数时，n n必必为偶数。偶数。子图子图定定义14.8 14.8 设G G，G GV 为两个两个图( (同同为无向无向图或同或同为有向有向图) )，假，假设V V V V且且E E E E，那么称，那么称G G是是G G的子的子图，G G为G G 的母的母图，记作作G G G G。假假设V V V V或或E E E E，那么称，那么称G G 为G G的真子的真子图。假假设V V V V，那么称，那么称G G 为G G的生成子的生成子图。设G G为一一图，V1V1V V且且V1V1，称以，称以V1V1为顶点集，以

33、点集，以G G中两个端点都在中两个端点都在V1V1中的中的边组成成边集集E1E1的的图为G G的的V1V1导出的子出的子图，记作作GV1GV1。设E1E1E E且且E1E1，称以，称以E1E1为边集，以集，以E1E1中中边关关联的的顶点点为顶点集点集V1V1的的图为G G的的E1E1导出的子出的子图，记作作GE1GE1。导出子图举例导出子图举例在上图中，设在上图中，设G G为为(1)(1)中图所表示，中图所表示，取取V1V1a,b,ca,b,c，那么，那么V1V1的导出子图的导出子图GV1GV1为为(2)(2)中图所示。中图所示。取取E1E1e1,e3e1,e3，那么，那么E1E1的导出子图的

34、导出子图GE1GE1为为(3)(3)中图所示。中图所示。例例14.314.3(1) (1) 画出画出4 4阶3 3条条边的一切非同构的无向的一切非同构的无向简单图。由握手定理可知，所画的无向由握手定理可知，所画的无向简单图各各顶点度数之和点度数之和为23236 6，最大度小于或等于，最大度小于或等于3 3。于是所求无向。于是所求无向简单图的度数列的度数列应满足足的条件是，将的条件是，将6 6分成分成4 4个非个非负整数，每个整数均大于或等于整数，每个整数均大于或等于0 0且且小于或等于小于或等于3 3，并且奇数的个数，并且奇数的个数为偶数。将偶数。将这样的整数列排出的整数列排出来只需下面三种情

35、况：来只需下面三种情况：(1) 2(1) 2，2 2，1 1，1 1(2) 3(2) 3，1 1，1 1，1 1(3) 2(3) 2，2 2，2 2，0 0 将每种度数列一切非同构的将每种度数列一切非同构的图都画出来即得所要求的全都画出来即得所要求的全部非同构的部非同构的图。对于于给定的正整数定的正整数n n和和m(mn(n-1)/2)m(mn(n-1)/2)，构造出一切非同构的构造出一切非同构的n n阶m m条条边的一切非同的一切非同构的无向构的无向( (有向有向) )简单图，这是目前是目前还没有没有处理的理的难题。例例14.314.3(2) (2) 画出画出3 3阶阶2 2条边的一切非

36、同构的有向简单图。条边的一切非同构的有向简单图。由握手定理可知，所画有向简单图各顶点度数之和为由握手定理可知，所画有向简单图各顶点度数之和为4 4，最，最大出度和最大入度均小于或等于大出度和最大入度均小于或等于2 2。度数列及入度出度列为。度数列及入度出度列为1,2,1入度列入度列为 0,1,1 0,1,1 或或 0,2,0 0,2,0 或或 1,0,1 1,0,1出度列出度列为 1,1,0 1,1,0 或或 1,0,1 1,0,1 或或 0,2,0 0,2,02,2,0入度列入度列为 1,1,0 1,1,0出度列出度列为 1,1,0 1,1,0定义定义14.914.9定定义14.9 14.9

37、设G G为n n阶无向无向简单图，以，以V V为顶点集，以一点集，以一切使切使G G成成为完全完全图KnKn的添加的添加边组成的集合成的集合为边集的集的图，称，称为G G的的补图，记作作G G。假假设图GGGG，那么称，那么称为G G是自是自补图。(1)(1)为自自补图(2)(2)和和(3)(3)互互为补图定义定义14.1014.10定定义14.10 14.10 设G G为无向无向图。(1)(1)设eEeE，用，用G-eG-e表示从表示从G G中去掉中去掉边e e，称，称为删除除e e。设E E E E，用，用G-E G-E 表示从表示从G G中中删除除E E 中一切的中一切的边，称，称为删

38、除除E E 。(2)(2)设vVvV，用，用G-vG-v表示从表示从G G中去掉中去掉v v及所关及所关联的一切的一切边，称，称为删除除顶点点v v。设V V V V，用，用G-V G-V 表示从表示从G G中中删除除V V 中一切中一切顶点，称点，称为删除除V V 。(3)(3)设边e e(u,v)E(u,v)E，用，用GeGe表示从表示从G G中中删除除e e后，将后，将e e的两个端点的两个端点u,vu,v用一个新的用一个新的顶点点w(w(或用或用u u或或v v充任充任w)w)替代，使替代，使w w关关联除除e e外外u,vu,v关关联的一切的一切边，称，称为边e e的收的收缩。(4)

39、(4)设u,vV(u,vu,vV(u,v能能够相相邻，也能，也能够不相不相邻) )，用，用G(u,v)(G(u,v)(或或G+(u,v)G+(u,v)表示在表示在u,vu,v之之间加一条加一条边(u,v)(u,v)，称，称为加新加新边。阐明明在收在收缩边和加新和加新边过程中能程中能够产生生环和平行和平行边。举例举例GGe5Ge1, e4Gv5Gv4, v5Ge514.2 14.2 通路与回路通路与回路定定义14.11 14.11 设G G为无无向向标定定图，G G中中顶点点与与边的的交交替替序序列列vi0ej1vi1ej2vi2ejivilvi0ej1vi1ej2vi2ejivil称称为vi0

40、vi0到到vilvil的的通通路路，其其中中，vir-vir-1,vir1,vir为ejrejr的的端端点点，r r 1 1，2 2，l l，vi0vi0，vilvil分分别称称为的的始点与始点与终点，点，中中边的条数称的条数称为它的它的长度。度。假假设vi0vi0vilvil，那么称通路，那么称通路为回路。回路。假假设的一切的一切边各异，那么称各异，那么称为简单通路，通路，又假又假设vi0vi0vilvil，那么称，那么称为简单回路。回路。假假设的的一一切切顶点点( (除除vi0vi0与与vijvij能能够一一样外外) )各各异异，一一切切边也也各各异异，那么称那么称为初初级通路或途径，通路

41、或途径，又假又假设vi0vi0vilvil，那么称，那么称为初初级回路或圈。回路或圈。将将长度度为奇数的圈称奇数的圈称为奇圈，奇圈，长度度为偶数的圈称偶数的圈称为偶圈。偶圈。关于通路与回路的阐明关于通路与回路的阐明q在初在初级通路与初通路与初级回路的定回路的定义中，仍将初中，仍将初级回路看成初回路看成初级通通路路( (途径途径) )的特殊情况，只是在运用中初的特殊情况，只是在运用中初级通路通路( (途径途径) )都是始都是始点与点与终点不一点不一样的，的，长为1 1的圈只能由的圈只能由环生成，生成，长为2 2的圈只的圈只能由平行能由平行边生成，因此在生成，因此在简单无向无向图中，圈的中，圈的

42、长度至少度至少为3 3。q假假设中有中有边反复出反复出现，那么称，那么称为复复杂通路，通路，q又假又假设vi0vi0vilvil，那么称，那么称为复复杂回路。回路。 q在有向在有向图中，通路、回路及分中，通路、回路及分类的定的定义与无向与无向图中非常中非常类似，似，只是要留意有向只是要留意有向边方向的一致性。方向的一致性。 q在以上的定在以上的定义中，将回路定中，将回路定义成通路的特殊情况，即回路也成通路的特殊情况，即回路也是通路，又初是通路，又初级通路通路( (回路回路) )是是简单通路通路( (回路回路) )，但反之不真。，但反之不真。通路和回路的简单表示法通路和回路的简单表示法(1)(1

43、)只用只用边的序列表示通路的序列表示通路( (回路回路) )。定。定义14.1114.11中的中的可以表示可以表示成成ej1 ,ej2 , ,ejlej1 ,ej2 , ,ejl。(2)(2)在在简单图中也可以只用中也可以只用顶点序列表示通路点序列表示通路( (回路回路) )。定。定义中中的的也可以表示成也可以表示成vi0 ,vi2 , ,vilvi0 ,vi2 , ,vil。(3)(3)为了写出非了写出非标定定图中的通路中的通路( (回路回路) )，可以先将非，可以先将非标定定图标成成标定定图，再写出通路与回路。，再写出通路与回路。(4)(4)在非在非简单标定定图中，当只用中，当只用顶点序列

44、表示不出某些通路点序列表示不出某些通路( (回回路路) )时，可在，可在顶点序列中参与一些点序列中参与一些边( (这些些边是平行是平行边或或环) )，可称，可称这种表示法种表示法为混合表示法。混合表示法。定理定理14.514.5定定理理14.5 14.5 在在n n阶图G G中中，假假设从从顶点点vivi到到vjvjvivjvivj存存在在通通路路，那么从那么从vivi到到vjvj存在存在长度小于或等于度小于或等于n-1n-1的通路。的通路。证明明设v0e1v1e2elvl(v0v0e1v1e2elvl(v0vi vi ,vl,vlvj)vj)为G G中中一一条条长度度为l l的的通路，通

45、路，假假设ln-1ln-1，那么，那么满足要求，足要求，否那么必有否那么必有l+1nl+1n，即，即上的上的顶点数大于点数大于G G中的中的顶点数，点数，于是必存在于是必存在k,s,0kslk,s,0ksl，使得，使得 vs vsvk,vk,即在即在上存在上存在vsvs到本身的回路到本身的回路Csk,Csk,在在上上删除除CskCsk上的一切上的一切边及除及除vsvs外的一切外的一切顶点，点，得得v0e1v1e2vkes+1 elvl ,v0e1v1e2vkes+1 elvl ,仍仍为vivi到到vjvj的通路，的通路，且且长度至少比度至少比减少减少1 1。假假设还不不满足足要要求求，那那么么

46、反反复复上上述述过程程，由由于于G G是是有有限限图，经过有限步后，必得到有限步后，必得到vivi到到vjvj长度小于或等于度小于或等于n-1n-1的通路。的通路。定理定理14.614.6推推论在在n n阶图G G中，假中，假设从从顶点点vivi到到vjvjvivjvivj存在通路，存在通路，那么那么vivi到到vjvj一定存在一定存在长度小于或等于度小于或等于n-1n-1的初的初级通路途径通路途径。定理定理14.6 14.6 在一个在一个n n阶图G G中，假中，假设存在存在vi vi 到本身的回路，那么到本身的回路，那么一定存在一定存在vi vi 到本身到本身长度小于或等于度小于或等

47、于n n的回路。的回路。推推论在一个在一个n n阶图G G中，假中，假设存在存在vi vi 到本身的到本身的简单回路，那么回路，那么一定存在一定存在vi vi 到本身到本身长度小于或等于度小于或等于n n的初的初级回路。回路。例例14.414.4例例14.4 14.4 无向完全无向完全图Kn(n3)Kn(n3)中有几种非同构的圈？中有几种非同构的圈？解答解答长度一度一样的圈都是同构的，的圈都是同构的，因此只需因此只需长度不同的圈才是非同构的，度不同的圈才是非同构的，易知易知Kn(n3)Kn(n3)中含中含长度度为3 3，4 4，n n的圈，的圈，所以所以Kn(n3)Kn(n3)中有中有n-

48、2n-2种非同构的圈。种非同构的圈。例例14.514.5例例14.5 14.5 无向完全图无向完全图K3K3的顶点依次标定为的顶点依次标定为a,b,ca,b,c。在定义意义下。在定义意义下K3K3中有多少个不同的圈？中有多少个不同的圈？解答解答在同构意义下，在同构意义下，K3K3中只需一个长度为中只需一个长度为3 3的圈。的圈。但在定义意义下，不同起点但在定义意义下，不同起点( (终点终点) )的圈是不同的，的圈是不同的，顶点间陈列顺序不同的圈也看成是不同的，顶点间陈列顺序不同的圈也看成是不同的，因此因此K3K3中有中有6 6个不同的长为个不同的长为3 3的圈：的圈：abca abca ，a

49、cba acba ，bacb bacb ，bcab bcab ，cabc cabc ，cbaccbac假设只思索起点假设只思索起点( (终点终点) )的差别，的差别，而不思索顺时针逆时针的差别，应有而不思索顺时针逆时针的差别，应有3 3种不同的圈，种不同的圈，当然它们都是同构的，画出图来只需一个。当然它们都是同构的，画出图来只需一个。 14.3 14.3 图的连通性图的连通性q无向图的连通性无向图的连通性q无向图中顶点之间的短程线及间隔无向图中顶点之间的短程线及间隔q无向图的连通程度：点割集、割点、边割集、割边、连通度无向图的连通程度：点割集、割点、边割集、割边、连通度q有向图的连通性及判别方

50、法有向图的连通性及判别方法q扩展途径法与极大途径扩展途径法与极大途径q二部图及其判别方法二部图及其判别方法无向图的连通性无向图的连通性定定义14.12 14.12 设无无向向图G G，u,vVu,vV，假假设u,vu,v之之间存存在在通通路，那么称路，那么称u,vu,v是是连通的，通的，记作作u uv v。 vVvV，规定定v vv v。无向无向图中中顶点之点之间的的连通关系通关系 u,vu,v| u,vV| u,vV且且u u与与v v之之间有通路有通路是自反的、是自反的、对称的、称的、传送的，因此是送的，因此是V V上的等价关系。上的等价关系。连通图与连通分支连通图与连通分支定定义1

51、4.13 14.13 假假设无向无向图G G是平凡是平凡图或或G G中任何两个中任何两个顶点都是点都是连通通的，那么称的，那么称G G为连通通图，否那么称，否那么称G G是非是非连通通图或分或分别图。阐明：完全明：完全图Kn(n1)Kn(n1)都是都是连通通图零零图Nn(n2)Nn(n2)都是分都是分别图。定定义14.14 14.14 设无向无向图G G，V V关于关于顶点之点之间的的连通关系通关系的商集的商集V/V/V1,V2,VkV1,V2,Vk，ViVi为等价等价类，称，称导出子出子图GViGVi(i(i1,2,k)1,2,k)为G G的的连通分支，通分支，连通分支数通分支数k k常常

52、记为p(G)p(G)。阐明明假假设G G为连通通图，那么，那么p(G)p(G)1 1。假假设G G为非非连通通图，那么，那么p(G)2p(G)2。在一切的在一切的n n阶无向无向图中，中，n n阶零零图是是连通分支最多的，通分支最多的，p(Nn)p(Nn)n n。无向图中顶点之间的短程线及间隔无向图中顶点之间的短程线及间隔定定义14.15 14.15 设u,vu,v为无向无向图G G中恣意两个中恣意两个顶点，假点，假设u uv v，称，称u,vu,v之之间长度最短的通路度最短的通路为u,vu,v之之间的短程的短程线，短程，短程线的的长度称度称为u,vu,v之之间的的间隔，隔，记作作d(u

53、,v)d(u,v)。当当u,vu,v不不连通通时，规定定d(u,v)d(u,v)。间隔有以下性隔有以下性质：(1)d(u,v)0(1)d(u,v)0，u uv v时，等号成立。，等号成立。(2)(2)具有具有对称性，称性，d(u,v)d(u,v)d(v,u)d(v,u)。(3)(3)满足三角不等式：足三角不等式： u,v,wV(G)u,v,wV(G)，那么，那么d(u,v)+d(v,w)d(u,w)d(u,v)+d(v,w)d(u,w)阐明：在完全明：在完全图Kn(n2)Kn(n2)中，任何两个中，任何两个顶点之点之间的的间隔都是隔都是1 1。在在n n阶零零图Nn(n2)Nn(n2)中，任

54、何两个中，任何两个顶点之点之间的的间隔都隔都为。如何定义连通度如何定义连通度q问题：如何定量地比：如何定量地比较无向无向图的的连通性的通性的强与弱？与弱？q点点连通度：通度：为了破坏了破坏连通性，至少需求通性，至少需求删除多少个除多少个顶点？点？q边连通度：通度：为了破坏了破坏连通性，至少需求通性，至少需求删除多少条除多少条边？q“破坏破坏连通性是指通性是指“变得更加不得更加不连通通。无向图的点割集无向图的点割集定定义14.16 14.16 设无向无向图G G，假，假设存在存在V V V V，且，且V V ，使得使得p(G-V p(G-V )p(G)p(G)，而，而对于恣意的于恣意的V V

55、V V ，均有，均有p(G-V p(G-V ) )p(G)p(G)，那么称，那么称V V 是是G G的点割集。的点割集。假假设V V 是是单元集，即元集，即V V vv，那么称，那么称v v为割点。割点。v2,v4,v3,v5v2,v4,v3,v5都是点割集都是点割集v3,v5v3,v5都是割点都是割点v1v1与与v6v6不在任何割集中。不在任何割集中。无向无向无向无向图图图图的的的的边边边边割集割集割集割集定定义14.1714.17设无向无向图G G，假，假设存在存在E E E E，且，且E E ，使得，使得p(G-E p(G-E )p(G)p(G)，而，而对于恣意的于恣意的E E E E

56、，均有，均有p(G-p(G-E E ) )p(G)p(G)，那么称，那么称E E是是G G的的边割集，或割集，或简称称为割集。割集。假假设E E 是是单元集，即元集，即E E ee，那么称，那么称e e为割割边或或桥。 e6,e5,e2,e3,e1,e2,e3,e6,e5,e2,e3,e1,e2,e3,e4,e1,e4,e1,e3,e2,e4e4,e1,e4,e1,e3,e2,e4 都是割集，都是割集，e6,e5e6,e5是是桥。点连通度点连通度定定义14.1814.18设G G为无向无向连通通图且且为非完全非完全图，那么称，那么称 K(G)K(G)min|V min|V |V |V 为G

57、G的点割集的点割集为G G的点的点连通度，通度，简称称连通度。通度。阐明明连通度是通度是为了了产生一个不生一个不连通通图需求需求删去的点的最少数目。去的点的最少数目。规定完全定完全图Kn(n1)Kn(n1)的点的点连通度通度为n-1n-1，规定非定非连通通图的点的点连通度通度为0 0，假假设K(G)kK(G)k，那么称，那么称G G是是k-k-连通通图，k k为非非负整数。整数。阐明明K(G)K(G)有有时简记为K K。上例中上例中图的点的点连通度通度为1 1，此，此图为1-1-连通通图。K5K5的点的点连通度通度K K4 4，所以，所以K5K5是是1-1-连通通图，2-2-连通通图，3-

58、3-连通通图，4-4-连通通图。假假设G G是是k-k-连通通图k1k1那么在那么在G G中中删除任何除任何k-1k-1个个顶点后，所点后，所得得图一定一定还是是连通的。通的。边连通度边连通度定定义14.19 14.19 设G G是无向是无向连通通图，称，称 (G )(G )min|E min|E | E | E 是是G G的点割集的点割集为G G的的边连通度。通度。规定非定非连通通图的的边连通度通度为0 0。假假设(G)r(G)r，那么称，那么称G G是是r r 边- -连通通图。阐明明 (G) (G)也可以也可以简记为。假假设G G是是 r r 边- -连通通图，那么在，那么在G G

59、中恣意中恣意删除除r-1r-1条条边后，所得后，所得图依然是依然是连通的。通的。完全完全图KnKn的的边连通度通度为n-1n-1，因此，因此KnKn是是r r边- -连通通图，0rn-10rn-1。图14.814.8中中图的的边连通度通度1 1，它只能是，它只能是1 1边- -连通通图。例例14.614.6求所示各图的点连通度，边连通度，并指出它们各是几连通图及求所示各图的点连通度，边连通度，并指出它们各是几连通图及几边连通图。最后将它们按点连通程度及边连通程度排序。几边连通图。最后将它们按点连通程度及边连通程度排序。K4K3K2K1K=1 =2K2K0K0例例14.614.6的解答的解答设第

60、第i i个个图的点的点连通度通度为KiKi，边连通度通度为ii，I I1,2,81,2,8。容易看出，容易看出，K1K1114 4，K2K2223 3，K3K3332 2，K4K4441 1， K5=1 5=2 K5=1 5=2，K6K6662 2，K7K7770 0，K8K8880 0。(1)(1)是是k-k-连通通图，k k边- -连通通图，k k1,2,3,41,2,3,4。(2)(2)是是k-k-连通通图，k k边- -连通通图，k k1,2,31,2,3。(3)(3)是是k-k-连通通图，k k边- -连通通图，k k1,21,2。(4)(4)是是1-1-连通通图，1 1边- -连通

61、通图。(5)(5)是是1-1-连通通图，k k边- -连通通图，k k1,21,2。(6)(6)是是k-k-连通通图，k k边- -连通通图，k k1,21,2。(7)(7)是是0-0-连通通图，0 0边- -连通通图。(8)(8)是是0-0-连通通图，0 0边- -连通通图。点点连通程度通程度为(1)(2)(3)(1)(2)(3)(6)(4)(6)(4)(5)(7)(5)(7)(8)(8)。边连通程度通程度为(1)(2)(3)(1)(2)(3)(5)(5)(6)(4)(7)(6)(4)(7)(8)(8)。定理定理14.714.7定理定理14.7 14.7 对于任何无向于任何无向图G G，有，

62、有 K(G)(G)(G)K(G)(G)(G)例例14.7 (1)14.7 (1)给出一些无向出一些无向简单图，使得，使得 K K。 (2) (2)给出一些无向出一些无向简单图，使得，使得 K K。解答解答 (1) n (1) n阶无向完全无向完全图KnKn和和n n阶零零图NnNn都都满足要求。足要求。(2)(2)在两个在两个Kn(n4)Kn(n4)之之间放置一个放置一个顶点点v v，使，使v v与两个与两个KnKn中的每一个中的每一个的恣意两个不同的的恣意两个不同的顶点相点相邻，所得，所得简单图满足要求。足要求。由于由于这样的的图中有一个割点，所以点中有一个割点，所以点连通度通度为1 1，又

63、由于无又由于无桥，而有两条，而有两条边组成的成的边割集，所以割集，所以边连通度通度为2 2，当当n n4 4时，3 3，当，当n5n5时，4 4。有向图的连通性有向图的连通性定定义14.20 14.20 设D D为一一个个有有向向图。vi,vjVvi,vjV，假假设从从vivi到到vjvj存在通路，那么称存在通路，那么称vivi可达可达vjvj，记作作vivjvivj，规定定vivi总是可达本身的，即是可达本身的，即vivivivi。假假设vivjvivj且且vjvivjvi，那那么么称称vivi与与vjvj是是相相互互可可达达的的，记作作vi vi vj vj。规定定vivivivi。阐明

64、明与与都都是是V V上上的的二二元元关关系系，并并且且不不难看看出出是是V V上上的的等等价价关系。关系。定定义14.21 14.21 设D D为有有向向图，vi,vjVvi,vjV，假假设vivjvivj，称称vivi到到vjvj长度最短的通路度最短的通路为vivi到到vjvj的短程的短程线，短程短程线的的长度度为vivi到到vjvj的的间隔，隔，记作作d d 。阐明明与与无无向向图中中顶点点vivi与与vjvj之之间的的间隔隔d(vi,vj)d(vi,vj)相相比比，dd除无除无对称性外，具有称性外，具有d(vi,vj)d(vi,vj)所具有的一切性所具有的一切性质。连通图连通图定

65、定义14.22 14.22 设D D为一个有向一个有向图。假。假设D D的基的基图是是连通通图，那，那么称么称D D是弱是弱连通通图，简称称为连通通图。假假设vi,vjVvi,vjV，vivjvivj与与vjvivjvi至少成立其一，那么称至少成立其一，那么称D D是是单向向连通通图。假假设均有均有vi vi vj vj，那么称，那么称D D是是强连通通图。阐明明强连通通图一定是一定是单向向连通通图，单向向连通通图一定是弱一定是弱连通通图。强连通通图单向向连通通图弱弱连通通图强连通图与单向连通图的断定定理强连通图与单向连通图的断定定理定定理理14.8 14.8 设有有向向图D D，V Vv

66、1,v2,vnv1,v2,vn。D D是是强连通通图当当且且仅当当D D中存在中存在经过每个每个顶点至少一次的回路。点至少一次的回路。证明明充分性充分性显然。然。下面下面证明必要性。明必要性。由由D D的的强连通性可知，通性可知，vivi+1vivi+1，i i1,2,n-11,2,n-1。设ii为vivi到到vi+1vi+1的通路。的通路。又又由由于于vnv1vnv1，设nn为vnvn到到v1v1的的通通路路，那那么么1,2,n-1,2,n-1,n1,n所所围成的回路成的回路经过D D中每个中每个顶点至少一次。点至少一次。定定理理14.9 14.9 设D D是是n n阶有有向向图，D D

67、是是单向向连通通图当当且且仅当当D D中中存存在在经过每个每个顶点至少一次的通路。点至少一次的通路。证明明略。略。问题设有有向向图D D是是单向向连通通图，但但不不是是强连通通图，问在在D D中中至至少少加加几条几条边所得所得图D D 就能成就能成为强连通通图？扩展途径法扩展途径法 q设G G为n n阶无向无向图，EE，设ll为G G中一条途径，中一条途径，q假假设此途径的始点或此途径的始点或终点与通路外的点与通路外的顶点相点相邻，就将它，就将它们扩到通路中来。到通路中来。q继续这一一过程，直到最后得到的通路的两个端点不与通程，直到最后得到的通路的两个端点不与通路外的路外的顶点相点相邻为止

68、。止。q设最后得到的途径最后得到的途径为l+k(l+k(长度度为l l的途径的途径扩展成了展成了长度度为l+kl+k的途径的途径) )，称，称l+kl+k为“极大途径，极大途径，q称运用此种方法称运用此种方法证明明问题的方法的方法为“扩展途径法。展途径法。q有向有向图中可以中可以类似地似地讨论，只，只须留意，在每步留意，在每步扩展中展中坚持有持有向向边方向的一致性。方向的一致性。关于极大途径的阐明关于极大途径的阐明q由某条路经扩展出的极大途径不独一。由某条路经扩展出的极大途径不独一。q极大途径不一定是图中最长的途径。极大途径不一定是图中最长的途径。例例14.814.8例例14.8 14.8 设

69、G G为n nn4n4阶无向无向简单图，(G)3(G)3。证明明G G中存在中存在长度大于或等于度大于或等于4 4的圈。的圈。证明明无妨无妨设G G是是连通通图，否那么，由于，否那么，由于G G的各的各连通分支的最小度通分支的最小度也都大于或等于也都大于或等于3 3，因此可，因此可对它的某个它的某个连通分支通分支进展展讨论。设u,vu,v为G G中恣意两个中恣意两个顶点，由点，由G G是是连通通图，因此，因此u,vu,v之之间存在通存在通路，由定理路，由定理14.514.5的推的推论可知，可知，u,vu,v之之间存在途径，用存在途径，用“扩展途径展途径法法扩展展这条途径，条途径，设最后得到

70、的最后得到的“极大途径极大途径为llv0v1vlv0v1vl，易知，易知l3l3。假假设v0v0与与vlvl相相邻，那么，那么l(v0,vl)l(v0,vl)为长度大于或等于度大于或等于4 4的圈。的圈。否那么，由于否那么，由于d(v0)(G)3d(v0)(G)3，因此，因此v0v0除与除与ll上的上的v1v1相相邻外，外，还存在存在ll上的上的顶点点vk(k1)vk(k1)和和vt(kvt(kt t l )l )与与v0v0相相邻，那么，那么v0v1vkvtv0v0v1vkvtv0为一个圈且一个圈且长度大于或等于度大于或等于4 4，见图。二部图二部图定定义14.23 14.23 设G G为

71、一一个个无无向向图，假假设能能将将V V分分成成V1V1和和V2(V1V2V2(V1V2V,V1V2V,V1V2) )，使使得得G G中中的的每每条条边的的两两个个端端点点都都是是一一个个属属于于V1V1，另另一一个个属属于于V2V2，那那么么称称G G为二二部部图或或称称二二分分图，偶，偶图等，称等，称V1V1和和V2V2为互互补顶点子集。点子集。常将二部常将二部图G G记为。假假设G G是是简单二二部部图，V1V1中中每每个个顶点点均均与与V2V2中中一一切切顶点点相相邻，那么称那么称G G为完全二部完全二部图，记为Kr,sKr,s，其中，其中r r|V1|V1|，s s|V2|V2|。

72、阐明明n n阶零零图为二部二部图。二部图举例二部图举例K6的子的子图图K6的子的子图图K3,3K2,3K3,3K2,3二部图的断定定理二部图的断定定理定理定理14.10 14.10 一个无向一个无向图G G是二部是二部图当且当且仅当当G G中无奇数中无奇数长度的回路。度的回路。证明明必要性。必要性。假假设G G中无回路，中无回路，结论显然成立。然成立。假假设G G中有回路，只需中有回路，只需证明明G G中无奇圈。中无奇圈。设C C为G G中恣意一圈，令中恣意一圈，令C Cvi1vi2vilvi1vi1vi2vilvi1，易知，易知 l2 l2。无妨无妨设vi1V1vi1V1，那么必有，那么必

73、有vilV-V1=V2vilV-V1=V2，而而l l必必为偶数，于是偶数，于是C C为偶圈，偶圈，由由C C的恣意性可知的恣意性可知结论成立。成立。二部图的断定定理二部图的断定定理充分性。充分性。无妨无妨设G G为连通通图，否那么可，否那么可对每个每个连通分支通分支进展展讨论。设v0v0为G G中恣意一个中恣意一个顶点，令点，令V1V1v|vV(G)d(v0,v)v|vV(G)d(v0,v)为偶数偶数 V2V2v|vV(G)d(v0,v)v|vV(G)d(v0,v)为奇数奇数易知，易知，V1V1,V2,V2,V1V2,V1V2，V1V2V1V2V(G)V(G)。下面只需下面只需证明明V1V

74、1中恣意两中恣意两顶点不相点不相邻,V2,V2中恣意两点也不相中恣意两点也不相邻。假假设存在存在vi,vjV1vi,vjV1相相邻，令，令(vi,vj)(vi,vj)e e，设v0v0到到vi,vjvi,vj的短程的短程线分分别为i,ji,j，那么它那么它们的的长度度d(v0,vi),d(v0,vj)d(v0,vi),d(v0,vj)都是偶数，都是偶数，于是于是ijeije中一定含奇圈，中一定含奇圈，这与知条件矛盾。与知条件矛盾。类似可似可证，V2V2中也不存在相中也不存在相邻的的顶点，于是点，于是G G为二部二部图。14.4 14.4 图的矩阵表示图的矩阵表示定定义14.24 14.24 设

75、无向无向图G G，V Vv1,v2,vnv1,v2,vn，E Ee1,e2,eme1,e2,em，令，令mijmij为顶点点vivi与与边ejej的关的关联次数，那么称次数，那么称(mij)nm(mij)nm为G G的关的关联矩矩阵，记作作M(G)M(G)。有向图的关联矩阵有向图的关联矩阵定定义14.25 14.25 设有向有向图D D中无中无环，V Vv1,v2,vnv1,v2,vn，E Ee1,e2,eme1,e2,em，令，令那么称那么称(mij)nm(mij)nm为D D的关的关联矩矩阵，记作作M(D)M(D)。有向图的邻接矩阵有向图的邻接矩阵定定义14.26 14.26 设有向有向

76、图D D，V Vv1,v2,vnv1,v2,vn，E Ee1,e2,e1,e2,，emem，令，令aij(1)aij(1)为顶点点vivi邻接到接到顶点点vjvj边的条数，的条数，称称(aij(1)nn(aij(1)nn为D D的的邻接矩接矩阵，记作作A(D)A(D)，或，或简记为A A。有向图的可达矩阵有向图的可达矩阵定定义14.27 14.27 设D D为有向有向图。V Vv1,v2,vnv1,v2,vn，令，令 pij1 vi 1 vi 可达可达 vj vj0 0 否那么否那么称称(pij)nn(pij)nn为D D的可达矩的可达矩阵，记作作P(D)P(D)，简记为P P。 14.5 1

77、4.5 图的运算图的运算定定义14.28 14.28 设G1G1，G2G2为两个两个图。假假设V1V2V1V2，那么称，那么称G1G1与与G2G2是不交的。是不交的。假假设E1E2E1E2，那么称，那么称G1G1与与G2G2是是边不交的或不交的或边不重的。不重的。阐明：不交的明：不交的图，必然是，必然是边不交的，但反之不真。不交的，但反之不真。图的运算图的运算定定义14.29 14.29 设G1G1，G2G2为不含孤立点的两个不含孤立点的两个图它它们同同为无向无向图或同或同为有向有向图。(1)(1)称以称以E1E2E1E2为边集，以集，以E1E2E1E2中中边关关联的的顶点点组成的集合成的集

78、合为顶点集的点集的图为G1G1与与G2G2的并的并图，记作作G1G2G1G2。(2)(2)称以称以E1-E2E1-E2为边集，以集，以E1-E2E1-E2中中边关关联的的顶点点组成的集合成的集合为顶点集的点集的图为G1G1与与G2G2的差的差图，记作作G1-G2G1-G2。 (3)(3)称以称以E1E2E1E2为边集，以集，以E1E2E1E2中中边关关联的的顶点点组成的集合成的集合为顶点集的点集的图为G1G1与与G2G2的交的交图，记作作G1G2G1G2。 (4)(4)称以称以E1E2E1E2为边集集为集合之集合之间的的对称差运算，以称差运算，以E1E2E1E2中中边关关联的的顶点点组成的集合

79、成的集合为顶点集的点集的图为G1G1与与G2G2的的环和，和，记作作G1G2G1G2。定义定义14.2914.29的阐明的阐明(1)(1)假假设G1G1G2G2，那么，那么G1G2G1G2G1G2G1G2G1(G2)G1(G2)G1-G2G1-G2G2-G1G2-G1G1G2G1G2这就是在就是在图的定的定义中中给出空出空图概念的概念的缘由。由。 (2)(2)当当G1G1与与G2G2边不重不重时，G1G2G1G2G1-G2G1-G2G1G1G2-G1G2-G1G2G2G1G1G2G2G1G2 G1G2 (3)(3)图之之间环和的定和的定义也可以用并、交、差也可以用并、交、差给出，即出，即G1

80、G2G1G2(G1G2)-(G1G2)(G1G2)-(G1G2)根本要求根本要求q了解与图的定义有关的诸多概念，以及它们之间的相互关系。了解与图的定义有关的诸多概念，以及它们之间的相互关系。q深化了解握手定理及其推论的内容，并能熟练地运用它们。深化了解握手定理及其推论的内容，并能熟练地运用它们。q深化了解图同构、简单图、完全图、正那么图、子图、补图、深化了解图同构、简单图、完全图、正那么图、子图、补图、二部图等概念及其它们的性质和相互关系，并能熟练地运用这二部图等概念及其它们的性质和相互关系，并能熟练地运用这些性质和关系。些性质和关系。q深化了解通路与回路的定义、相互关系及其分类，掌握通路与深化了解通路与回路的定义、相互关系及其分类，掌握通路与回路的各种不同的表示方法。回路的各种不同的表示方法。q了解无向图的点连通度、边连通度等概念及其之间的关系，并了解无向图的点连通度、边连通度等概念及其之间的关系，并能熟练地求出给定的较为简单的图的点连通度与边连通度。能熟练地求出给定的较为简单的图的点连通度与边连通度。q了解有向图连通性的概念及其分类，掌握判别有向连通图类型了解有向图连通性的概念及其分类，掌握判别有向连通图类型的方法。的方法。作业作业

展开阅读全文

时期图的基本概念ppt课件

最新文档