《图的基本概念》ppt课件

1、1第十四章图的根本概念第十四章图的根本概念第四部分：图论第四部分：图论2七桥问题七桥问题q问题问题q寻觅走遍哥尼斯堡寻觅走遍哥尼斯堡Knigsberg城的城的7座桥，且只许走过每座桥一座桥，且只许走过每座桥一次，最后又回到原出发点次，最后又回到原出发点q求解求解q1736年瑞士大数学家欧拉年瑞士大数学家欧拉LeonhardEuler发表了关于发表了关于“哥尼斯堡七桥问题的论文哥尼斯堡七桥问题的论文图论的第一篇论文。他指出图论的第一篇论文。他指出从一点出发不反复的走遍七桥，从一点出发不反复的走遍七桥，最后又回到原来出发点是不可以最后又回到原来出发点是不可以的。的。3图论图论 图论是近年来开展迅速

2、而又运用广泛的一图论是近年来开展迅速而又运用广泛的一门新兴学科。它最早来源于一些数学游戏的门新兴学科。它最早来源于一些数学游戏的难题研讨，如难题研讨，如1736年欧拉年欧拉L.Euler)所处置所处置的哥尼斯堡七桥问题。以及在民间广为流传的哥尼斯堡七桥问题。以及在民间广为流传的一些游戏问题：例如迷宫问题、棋盘上马的一些游戏问题：例如迷宫问题、棋盘上马的行走道路问题的行走道路问题4棋盘上马的行走道路问题棋盘上马的行走道路问题q 在中国象棋中，马走在中国象棋中，马走“日字，即每步从日字，即每步从 12 矩形的一矩形的一个顶点跳到相对的顶点。如图，马从个顶点跳到相对的顶点。如图，马从M3，2一次只一

3、次只能跳到能跳到A、B、C、D、E、F、G、H中的任何一个位置中的任何一个位置。q 问题：马能否从棋盘上恣意一点出发，不反复、不脱漏问题：马能否从棋盘上恣意一点出发，不反复、不脱漏地走遍整个棋盘即每一点都走到并且只到一次？地走遍整个棋盘即每一点都走到并且只到一次？ 5棋盘上马的行走道路问题棋盘上马的行走道路问题q 将马目前所在位置涂成白色，用涂色的方法，将棋盘上的点分为黑、白相间的两类6周游世界各国的问题周游世界各国的问题q 英国数学家哈密顿于1859年以游戏的方式提出：把一个正十二面体的二十个顶点看成二十个城市，要求找出一条经过每个城市恰好一次而回到出发点的道路。这条道路就称“哈密顿圈。一百

4、多年来，对哈密顿问题的研讨，促进了图论的开展。 7四色猜测四色猜测q问题：任何一张地图只用问题：任何一张地图只用四种颜色就能使具有共同四种颜色就能使具有共同边境的国家着上不同的颜边境的国家着上不同的颜色色q用数学言语表示，即：用数学言语表示，即：“将平面恣意地细分为不相将平面恣意地细分为不相重叠的区域，每一个区域重叠的区域，每一个区域总可以用总可以用1，2，3，4这四这四个数字之一来标志，而不个数字之一来标志，而不会使相邻的两个区域得到会使相邻的两个区域得到一样的数字一样的数字 8图论图论q图论不断开展，它在处置运筹学，网络图论不断开展，它在处置运筹学，网络实践，信息论，控制论，博奕论以及计实

5、践，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出算机科学等各个领域的问题时，显示出越来越大的作用越来越大的作用9第十四章图的根本概念第十四章图的根本概念 第一节：图第一节：图 第二节：通路、回路、图的连通性第二节：通路、回路、图的连通性第三节：图的矩阵表示和运算第三节：图的矩阵表示和运算 10第一节：图第一节：图q 无序积：设无序积：设A，B为恣意的两个集合，称为恣意的两个集合，称q a,b | aA且且bBq 为为A与与B的无序积，记做的无序积，记做A&Bq 无向图：一个无向图无向图：一个无向图G是一个二重组是一个二重组, 其其中中V(G)为有限非空结点或叫顶点集合

6、为有限非空结点或叫顶点集合, E(G)是边是边的集合，它是无序积的集合，它是无序积V&V的多重子集，其元素为无的多重子集，其元素为无向边，简称边。向边，简称边。q 有向图：一个有向图有向图：一个有向图G是一个二重组是一个二重组, 其其中中V(G)为有限非空结点或叫顶点集合为有限非空结点或叫顶点集合, E(G)是边是边的集合，它是笛卡儿乘积的集合，它是笛卡儿乘积VV的多重子集，其元素的多重子集，其元素为有向边，简称边。为有向边，简称边。q 11下面定义一些专门名词：下面定义一些专门名词：通常用通常用G G表示无向图，表示无向图，D D表示有向图，但表示有向图，但G G也可以泛也可以泛指图

7、。指图。V(G)V(G)，E(G)E(G)分别表示分别表示G G的顶点集和边集。的顶点集和边集。|V(G)|,|E(G)|V(G)|,|E(G)|分别表示分别表示G G的顶点数和边数，的顶点数和边数， 假设假设|V(G)|V(G)|n n，那么称，那么称G G为为n n阶图。阶图。假设假设|V(G)|,|E(G)|V(G)|,|E(G)|均为有限数，那么称均为有限数，那么称G G为有限为有限图。图。假设图假设图G G中，边集为空，那么称之为零图，中，边集为空，那么称之为零图， 假设假设G G为为n n阶图，那么称之为阶图，那么称之为n n阶零图，记为阶零图，记为NnNn， N1 N1称为平凡图

8、。称为平凡图。4 4顶点集为空的图记为空图。顶点集为空的图记为空图。第一节：图第一节：图12一些定义一些定义5称顶点或边用字母标定的图为标定图，否那么称顶点或边用字母标定的图为标定图，否那么成为非标定图。另外，将有向边改为无向边后的成为非标定图。另外，将有向边改为无向边后的图称为原图的基图。图称为原图的基图。6设设G=为无向图，为无向图，ek=(vi,vj)E,那么称那么称vi,vj为为ek的端点，的端点， ek与与vi或或ek与与vj是彼此关联的。是彼此关联的。 假设假设vivj，那么称，那么称ek与与vi或或ek与与vj的关联次数为的关联次数为1， 假设假设vi=vj，那么称，那么称ek与

9、与vi的关联次数为的关联次数为2，并称为，并称为环。恣意的环。恣意的vlV，假设，假设vlvi且且vlvj，那么称，那么称ek与与vl的关联次数为的关联次数为0。13一些定义一些定义7设无向图设无向图G=，vi,vjV， ek,elE。假。假设存在设存在etE，使得，使得et=(vi,vj)，那么称，那么称vi与与vj是相是相邻的。假设邻的。假设ek与与el至少有一个公共端点，那么称至少有一个公共端点，那么称ek与与el是相邻的。是相邻的。 有向图有向图D=，vi,vjV，ek,elE 。假设存。假设存在在etE，使得，使得et=，那么称，那么称vi为为et的始点，的始点，vj为为et的终点，

10、并称的终点，并称vi邻接到邻接到vj，vj邻接于邻接于vi，假，假设设ek的终点为的终点为el的始点，那么称的始点，那么称ek与与el相邻。相邻。14一些定义一些定义8设无向图设无向图G=，对一切的，对一切的vV称称为为v的邻域，记为的邻域，记为NG(v)，并称并称NG(v) v为为v的闭邻域，记为的闭邻域，记为 。称称 为为v的关联集，记为的关联集，记为IG(v) 。设有向图设有向图G=，对一切的，对一切的vV ，称，称为为v的后继元素。称的后继元素。称为为v的先驱元素。称两者之并为的先驱元素。称两者之并为v的邻域，记为的邻域，记为ND(v) 。称称ND(v) v，v的闭邻域。的闭邻域。 |

11、( , )u uVu vEuvGN (v) |e eEev 与 相关联 |V,uuv uEuv |,u uVu vEuv 15一些定义一些定义定义定义14.3 在无向图中，关联一对顶点的无向边假设多在无向图中，关联一对顶点的无向边假设多于一条，那么称这些边为平行边，平行边的条数称于一条，那么称这些边为平行边，平行边的条数称为重数。为重数。 在有向图中，关联一对顶点的有向边假设多于一条，在有向图中，关联一对顶点的有向边假设多于一条，并且这些边的始点和终点一样，那么称这些边为平并且这些边的始点和终点一样，那么称这些边为平行边。行边。 含平行边的图称为多重图，即不含平行边也不含环含平行边的图称为多重

12、图，即不含平行边也不含环的图称为简单图。的图称为简单图。16一些定义一些定义非多重图称为线图。非多重图称为线图。由定义可见，简单图是没有环和平行边的图。由定义可见，简单图是没有环和平行边的图。 17一些定义一些定义定义定义14.4：在无向图中，恣意点其作为边的端点次数：在无向图中，恣意点其作为边的端点次数之和称为该点的度数，记为之和称为该点的度数，记为dG(v). 在有向图中，对于任何结点在有向图中，对于任何结点v，以，以v为始点的边的条为始点的边的条数，称为结点数，称为结点v的引出次数的引出次数(或出度或出度)，记作，记作d+(v)；以以v点为终点的边的条数称为点为终点的边的条数称为v的引入

13、次数的引入次数(或入度或入度)，记作记作d(v)；结点的；结点的v的引入次数和引出次数之和称的引入次数和引出次数之和称为为v的次数度数，用的次数度数，用d (v)表示。表示。由定义可见由定义可见:度数度数d (v)d+(v)d(v)。定义：最大度，最小度，最大出度，最大入度，最小定义：最大度，最小度，最大出度，最大入度，最小入度，最小出度，悬挂点，悬挂边入度，最小出度，悬挂点，悬挂边18例例1例：例： d (a)(引入引入)+(引出引出)=5 db dc d1 d2 d3 以后为了表达方便，以后为了表达方便，我们将具有我们将具有n个结点个结点和和m条边的图简称为条边的图简称为n,m图图19握手

14、定理握手定理定理定理14.114.1握手定理：设握手定理：设G G是是n, mn, m无向图，它的顶无向图，它的顶点集合点集合v1,v2,vnv1,v2,vn，于是有，于是有1()2niidvm111()2,()()nnniiiiiidvmdvdvm证明：证明：在无向图中引入一条边，总的次数增，在无向图中引入一条边，总的次数增，假设有假设有m m条边，那么总次数为条边，那么总次数为2m2m。此定理也可推行到有向图和混合图此定理也可推行到有向图和混合图定理定理14.1 14.1 在有向图中，那么为：在有向图中，那么为：20例例 2 d da a， d db b， d dc c， d dd d,

15、, m m，2m2mdd d d + + + + 21例例 3例：假设图有例：假设图有n n个顶点个顶点, ,n+1n+1条边，那么条边，那么中至少有一个顶点的度数中至少有一个顶点的度数。证明：设中有证明：设中有n n个结点分别为个结点分别为v1,v2,vnv1,v2,vn，那么由握手定理：那么由握手定理： d dvivin+1n+1而顶点的平均度数为：而顶点的平均度数为： d dvivi(n+1)/n=2+1/n2 (n+1)/n=2+1/n2 顶点中至少有一个顶点的度数顶点中至少有一个顶点的度数22握手定理的推论握手定理的推论推论：在图中，度数为奇数的顶点必定有偶数个。推论：在图中，度数为

16、奇数的顶点必定有偶数个。 证 明 ： 设 度 数 为 偶 数 的 顶 点 有证 明 ： 设 度 数 为 偶 数 的 顶 点 有 n 1n 1 个个 , , 记 为记 为vei(i=1,2,n1),vei(i=1,2,n1),度数为奇数的顶点有度数为奇数的顶点有n2n2个，记为个，记为voi(i=1,2,n2)voi(i=1,2,n2)。由上一定理得。由上一定理得由于度数为偶数的各顶点次数之和为偶数。所以前一由于度数为偶数的各顶点次数之和为偶数。所以前一项度数为偶数；假设项度数为偶数；假设n2n2为奇数，那么第二项为奇数，为奇数，那么第二项为奇数，两项之和将为奇数，但这与上式矛盾。故两项之和将为

17、奇数，但这与上式矛盾。故n2n2必为偶必为偶数。数。问题：能否在一个部门的问题：能否在一个部门的2525个人中间，由于意见不同，个人中间，由于意见不同，每个人恰好与每个人恰好与5 5个人意见一致？个人意见一致？121112()()()nnnieioiiiimd vd vd v23可图化、可简单图化可图化、可简单图化 设设G=为一个为一个n阶无向图，阶无向图，Vv1,v2,vn，称称d(v1),d(v2)d(vn) 为为G的度数列。对于顶点标的度数列。对于顶点标定的无向图，它的度数列是独一的。定的无向图，它的度数列是独一的。 反之，对于给定的非负整数列反之，对于给定的非负整数列d=(d1,d2,

18、dn),假假设存在以设存在以Vv1,v2,vn为顶点集的为顶点集的n阶无向阶无向图图G，使得，使得d(vi)=di，那么称，那么称d是可图化的。是可图化的。 特别的，假设所得图是简单图，那么称特别的，假设所得图是简单图，那么称d是可简单是可简单图化的。图化的。24可图化的判别定理可图化的判别定理定理定理14.3 14.3 设非负整数列设非负整数列d=(d1,d2,dn), d=(d1,d2,dn), 那么那么d d是可是可图化的当且仅当图化的当且仅当 证明：必要性显然证明：必要性显然 充分性：构造性证明充分性：构造性证明定理定理14.4 14.4 设设G G为恣意为恣意n n阶无向简单图，那么

19、阶无向简单图，那么(G) n-(G) n-1 110(mod 2)niid25可图化可图化q 例：判别以下各非负整数列哪些是可图化的？哪些是可简单图化的？q (5,5,4,4,2,1)q (5,4,3,2,2)q (3,3,3,1)q (d1,d2,dn), d1d2dn1, 且 为偶数q (4,4,3,3,2,2)1niid26同构的定义同构的定义定义定义14.5：设，和：设，和，是两是两个图，假设存在从到个图，假设存在从到一双射函数：一双射函数：，使，使得对恣意的得对恣意的a,bV,a,b E当且仅当当且仅当g(a),g(b) ，并且并且a,b和和g(a),g(b)有一样的重数，那么称有一

20、样的重数，那么称和同构。和同构。讨论定义：讨论定义：1和是同构的和是同构的,它们的顶点必需是一一对应的；它们的顶点必需是一一对应的；2且对无向图而言，还要坚持顶点之间的邻接关系和边且对无向图而言，还要坚持顶点之间的邻接关系和边的重数；的重数；3且对有向图而言，不但要坚持顶点之间的邻接关系，且对有向图而言，不但要坚持顶点之间的邻接关系，而且还应坚持边的方向和边的重数。而且还应坚持边的方向和边的重数。图的同构关系可以看作是全体图集合上的二元关系，并且此图的同构关系可以看作是全体图集合上的二元关系，并且此关系是等价关系。关系是等价关系。27例例4例：例： 存在一双射函数存在一双射函数:1,2,3,4

21、a3,a4,a2,a1，其中：顶点的一一对应：其中：顶点的一一对应： g(1)= a3; g(2)= a4; g(3)= a2; g(4)= a1;边的一一对应：边的一一对应： g; g; g; g28例例 5例例:下面给出二个无向图，试求出同构函数下面给出二个无向图，试求出同构函数：1,2,3,4,5,6 a1,a2,a3,a4,a5,a6边的对应为：边的对应为：g(i,j)(g(i),g(j)ai,aj29同构的性质同构的性质两图同构的必要条件：两图同构的必要条件：1顶点数相等；顶点数相等；2边数相等；边数相等；3度数一样的顶点数相等。度数一样的顶点数相等。但这不是充分条件。如以以下图但这

22、不是充分条件。如以以下图30完全图完全图定义定义14.6：在个顶点的有向图：在个顶点的有向图G=中，假设每中，假设每个顶点都邻接到其他的个顶点都邻接到其他的n-1个顶点，又邻接于其他个顶点，又邻接于其他的的n-1个顶点，那么称个顶点，那么称G为有向完全图；在个顶为有向完全图；在个顶点的无向图点的无向图G=中，每二个顶点之间均有一中，每二个顶点之间均有一条边衔接，那么称条边衔接，那么称G为无向完全图。为无向完全图。31特殊图特殊图定义定义14.714.7：一切顶点均具有同样度数的简单无向图：一切顶点均具有同样度数的简单无向图为正那么图，各顶点的度数均为为正那么图，各顶点的度数均为k k时称为时称

23、为k k正那正那么图。么图。32子图的定义子图的定义定义定义14.8:设设=,=是二个图，是二个图， (a)假设假设，那么称，那么称是的子是的子图；图； (b)假设假设，并且，并且，那么称，那么称是的真子图；是的真子图； (c)假设假设，,那么称那么称是的生成是的生成子图支撑子图。子图支撑子图。 (d)假设子图假设子图G中没有孤立顶点，中没有孤立顶点，G由由E独一确独一确定，那么称定，那么称G为由边集为由边集E导出的子图。导出的子图。 (e)假设在子图假设在子图G中，对中，对中的恣意二顶点中的恣意二顶点u,v，当当u,vE时有时有u,vE，那么，那么G由由独一确独一确定，此时称定，此时称G为由

24、顶点集为由顶点集导出的子图。导出的子图。33例例 6例：图如下例：图如下 的真子图的真子图 生成子图：生成子图： E=,导出的子图由V=a,b,d,e导出的子图34例例 7例例 画出画出4 4阶阶3 3边的一切非同构的无向简单图。边的一切非同构的无向简单图。解：由握手定理可知，该无向简单图各顶点度数之和解：由握手定理可知，该无向简单图各顶点度数之和为为6 6，最大度小于或等于，最大度小于或等于3 3。于是所求无向简单图的。于是所求无向简单图的度数列应满足的条件是，将度数列应满足的条件是，将6 6分成分成4 4个非负数，每个个非负数，每个整数均大于等于整数均大于等于0 0且小于等于且小于等于3

25、3，并且奇数的个数为，并且奇数的个数为偶数。有三种情况偶数。有三种情况3 3，1 1，1 1，1 1；2 2，2 2，1 1，1 1；2 2，2 2，2 2，0 0将每种度数列一切非同构的图都画出来即可得所要求将每种度数列一切非同构的图都画出来即可得所要求的全部非同构图。的全部非同构图。35补图补图定义定义14.9:设无向简单图设无向简单图G= 有有n个顶点，无向个顶点，无向简单图简单图H= 也有同样的顶点，而也有同样的顶点，而E是是由由n个顶点的完全图的边删去个顶点的完全图的边删去E所得，那么图所得，那么图H称为图称为图G的补图。的补图。 自补图：自补图：H与与G同构同构36例例 8例：试画

26、出例：试画出5个顶点三条边和个顶点三条边和5个顶点七条边的简单个顶点七条边的简单无向图。无向图。解：解： 5个顶点三条边的图个顶点三条边的图5个顶点七条边的图为个顶点七条边的图为5顶点三条边的补图顶点三条边的补图37图的操作图的操作关于图的四种操作：关于图的四种操作：1删去中的一条边删去中的一条边e；2删去中的一个顶点即是删去顶点和与删去中的一个顶点即是删去顶点和与有关联的一切边。有关联的一切边。3设边设边e=(u,v)E，用，用Ge表示从表示从G中删除中删除e后，将后，将e的两个端点的两个端点u,v用一个新的顶点用一个新的顶点w替代，使替代，使w关联关联e以外以外u,v关联的一切边，称为关联

27、的一切边，称为e的收缩。的收缩。4设设u,vV，用，用G(u,v)表示在表示在u,v之间加一条边之间加一条边(u,v)，称为新加边。，称为新加边。38第十四章图的根本概念第十四章图的根本概念 第二节：通路、回路、图的连通性第二节：通路、回路、图的连通性 3914.2 通路和回路通路和回路定义定义14.11: 在有向图中，从某一顶点出发经过某些点在有向图中，从某一顶点出发经过某些点边交替序列到达终点，此序列称为通路。边交替序列到达终点，此序列称为通路。而经过的各条边之间没有一样的通路称为简单通路。而经过的各条边之间没有一样的通路称为简单通路。假设通路中顶点各不一样且边也各不一样，那么称假设通路中

28、顶点各不一样且边也各不一样，那么称为初级通路或途径。为初级通路或途径。假设通路的起点和终点重合，称此通路为回路。没假设通路的起点和终点重合，称此通路为回路。没有一样边的回路称为简单回路，没有一样边也没有一样边的回路称为简单回路，没有一样边也没有一样点除起始点和终止点外的回路称为圈。有一样点除起始点和终止点外的回路称为圈。4014.2 通路和回路通路和回路讨论：讨论：1从一个顶点到某一顶点的通路假设有的话从一个顶点到某一顶点的通路假设有的话不一定是独一的；不一定是独一的；2通路的表示方法：通路的表示方法：(a)边点序列表示法：边点序列表示法： 设，为一有向图，设，为一有向图，viV，那么通路可，

29、那么通路可以表示成：以表示成：v1,e1,v2,e2,v3,vk-1,en,vk(b)也可仅用边的序列表示也可仅用边的序列表示(c)顶点表示法顶点表示法(在简单图中在简单图中)： v1, v2 , vk (3)无向图中的以上术语的定义完全类似，不再反复。无向图中的以上术语的定义完全类似，不再反复。41例例 1例：给出有向图例：给出有向图,求起始于求起始于,终止于的通路。终止于的通路。 P1=(1,2,3)=(,) P2=(1,2,3,4,3) P3=(1,4,3) P4=(1,2,4,1,2,3) P5=(1,2,4,1,4,3) P6=(1,1,2,3),可见：可见：1从从1到到3有无限条通

30、路，有无限条通路，中间有回路；中间有回路；2上例中的上例中的P1 ，P2， P3， P5为简单通路。为简单通路。42通路的性质通路的性质定义定义:通路通路P中边的条数称为通路中边的条数称为通路P的长度路长。的长度路长。长度为长度为0的通路定义为一个单独的顶点。的通路定义为一个单独的顶点。定理定理14.5:设图，是中的顶点数设图，是中的顶点数即，假设从即，假设从v1到到v2(v1v2)有一条有一条通路，那么从通路，那么从v1到到v2有一条长度不大于有一条长度不大于n-1的通路。的通路。 推论推论:设图，是中的顶点数设图，是中的顶点数即，假设从即，假设从v1到到v2(v1v2)有一条有一条通路，那

31、么从通路，那么从v1到到v2有一条长度不大于有一条长度不大于n-1的初级的初级通路途径。通路途径。43通路和回路的性质通路和回路的性质定理定理14.6：在阶图中，从：在阶图中，从vi到到vi假设存在一条回路假设存在一条回路的话，那么从的话，那么从vi到到vi一定存在一条长度小于或等于一定存在一条长度小于或等于的回路。的回路。推论：在阶图中，从推论：在阶图中，从vi到到vi假设存在一条简单回路假设存在一条简单回路的话，那么从的话，那么从vi到到vi一定存在一条长度小于或等于一定存在一条长度小于或等于的初级回路。的初级回路。44通路和回路通路和回路q例：例：q 1. 无向完全图无向完全图Knn3中

32、有几种非同构中有几种非同构的圈？的圈？q 2. 无向完全图无向完全图K3的顶点依次标定为的顶点依次标定为a，b，c. 在定义意义下在定义意义下K3中有多少中有多少 不同的长度为不同的长度为3的圈的圈？q 4514.3 图的连通性图的连通性定义定义14.12：设无向图：设无向图=，且，且vi,vjV，假设，假设从从vi到到vj存在一条通路的话，那么称存在一条通路的话，那么称vi，vj是连通是连通的。普通以为的。普通以为vi到本身是连通的。到本身是连通的。由定义可见：连通的概念与由定义可见：连通的概念与vi到到vj之间的通路多少、之间的通路多少、通路长度、是什么样的通路没有任何关系。通路长度、是什

33、么样的通路没有任何关系。4614.3 图的连通性图的连通性连通性一定满足：连通性一定满足：自反性：自反性： vi到到vi一定是连通的。一定是连通的。可传送性：可传送性： vi到到vj连通，连通，vj到到vk连通，那么连通，那么vi到到vk连通。连通。对于有向图而言，既不一定对称，也不一定对于有向图而言，既不一定对称，也不一定反对称。反对称。 假设假设vi到到vj存在一条通路的话，那么存在一条通路的话，那么vj到到vi未必存未必存在一条通路。在一条通路。连通性对无向图满足自反、对称和可传送性连通性对无向图满足自反、对称和可传送性 47连通图连通图定义定义14.12：对于无向图中的任何顶点来讲，假

34、设任：对于无向图中的任何顶点来讲，假设任何二个顶点是相互连通的，那么称此图是连通的，何二个顶点是相互连通的，那么称此图是连通的，否那么称为非连通图或分别图。否那么称为非连通图或分别图。48连通分支连通分支定义定义14.13：设无向图：设无向图G=，V关于顶点之间的关于顶点之间的连通关系的商集连通关系的商集V/=V1,V2, Vk，Vi为等为等价类，称导出子图价类，称导出子图GVi(i=1,2,k)为为G的连通分的连通分支，连通分支数支，连通分支数k常记为常记为p(G)。一个无向图或者是一个连通图，或者是由假设干个一个无向图或者是一个连通图，或者是由假设干个连通分支组成连通分支组成49间隔间隔定

35、义定义14.14: 在无向图在无向图G=中，从顶点中，从顶点vi到到vj最短最短通路短程线的长度，叫做从通路短程线的长度，叫做从vi到到vj的间隔，记的间隔，记为为d(vi, vj) 。假设从。假设从vi到到vj不存在通路，那么不存在通路，那么d(vi, vj) =留意：在无向图中，有以下性质：留意：在无向图中，有以下性质：1) d(vi, vj) 0 2) d(vi, vi) = 03) d(vi, vj)=d(vj, vi) 4) d(vi, vj) +d(vj, vk) d(vi, vk) 50点割集、割点点割集、割点q定义定义14.15 设无向图设无向图 G= 。假设存在。假设存在 使

36、得使得p(G-V) p(G)，且有恣意的均有，且有恣意的均有p(G-V) =p(G)，那么称，那么称V为为G的点割集。假的点割集。假设是单个点，那么称割点。设是单个点，那么称割点。q定义定义14.16 设无向图设无向图 G= 。假设存在。假设存在 使得使得p(G-E) p(G)，且有恣意的均有，且有恣意的均有p(G-E) =p(G)，那么称，那么称E为为G的边割集。假的边割集。假设是单个边，那么称割边或者桥。设是单个边，那么称割边或者桥。q点连通度点连通度k-连通图连通图 q 留意：假设留意：假设G是是k-连通图，那么在连通图，那么在G中删除任何中删除任何k-1个顶点后，所得图一定还是连通的个

37、顶点后，所得图一定还是连通的q边连通度边连通度 r边边-连通图连通图VV VV EE EE 51点连通度、边连通度的关系点连通度、边连通度的关系q对于任何无向图G，有)()()(GGG52间隔间隔定义定义14.19：设有向图：设有向图=，且，且vi,vjV，假设，假设从从vi到到vj存在一条通路的话，那么称存在一条通路的话，那么称vi可达可达vj。普。普通以为通以为vi到本身是可达的。假设到本身是可达的。假设vi可达可达vj并且并且vj可可达达vi，那么称，那么称vi,vj相互可达。相互可达。定义定义14.20: 在有向图在有向图G=中，从顶点中，从顶点vi到到vj最短最短通路短程线的长度，叫

38、做从通路短程线的长度，叫做从vi到到vj的间隔，记的间隔，记为为d(vi, vj) 。假设从。假设从vi到到vj不存在通路，那么不存在通路，那么d(vi, vj) =。53连通性连通性定义定义14.22：在有向图中，它的基图假设是连通的，那：在有向图中，它的基图假设是连通的，那么称此有向图为弱连通的；假设图中任何顶点偶对么称此有向图为弱连通的；假设图中任何顶点偶对中至少有一点到另一顶点是可达的，那么称此图是中至少有一点到另一顶点是可达的，那么称此图是单向连通的；假设任两顶点均是相互可达的，那么单向连通的；假设任两顶点均是相互可达的，那么称是强连通的。称是强连通的。讨论定义：讨论定义：1强连通的

39、一定是单向连通的和弱连通的；强连通的一定是单向连通的和弱连通的；2单向连通的一定是弱连通的；单向连通的一定是弱连通的；3弱连通的既可以不是单向连通的，更可以不是弱连通的既可以不是单向连通的，更可以不是强连通的。强连通的。54连通性连通性 强连通的强连通的 单向连通的弱连通的单向连通的弱连通的55图的连通性图的连通性定理定理14.8 设有向图设有向图D=，Vv1,v2,vn 。D是强连通图当且仅当是强连通图当且仅当D中存在经过每个顶点至少中存在经过每个顶点至少一次的回路。一次的回路。证明：充分性显然证明：充分性显然必要性构造性证明必要性构造性证明定理定理14.9 设设D是是n阶有向图。阶有向图。

40、D是单向连通图当且仅是单向连通图当且仅当当D中存在经过每个顶点至少一次的通路。中存在经过每个顶点至少一次的通路。56二部图二部图定义定义14.23:14.23:假设无向图的顶点集假设无向图的顶点集V V分成两个子集分成两个子集X,Y,(X,Y,(即满足即满足XY=,XY=V),XY=,XY=V),使得使得G G中恣意一边中恣意一边的两个端点分属于的两个端点分属于X X和和Y,Y,那么称那么称G G为二部图为二部图,X,X和和Y Y称称为互补顶点子集为互补顶点子集, ,常记图为常记图为G=G=。 定义定义: :假设二部图假设二部图G=G=中中X X的每个顶点与的每个顶点与Y Y的每的每个顶点都有

41、且只需一条边相关联个顶点都有且只需一条边相关联, ,称称G G为完全二部为完全二部图图, ,记为记为Km,n,Km,n,其中其中|X|=m,|Y|=n|X|=m,|Y|=n。57例例4 abxyza x y z b 子集子集X=a,b,Y=x,y,z,这是一个二部图。这是一个二部图。这是完全二部图这是完全二部图K2,3。58二部图二部图此两图均是此两图均是K3,3因此是同构的因此是同构的 定理定理14.10:无向图无向图G是二部图的充要条件是是二部图的充要条件是G的一切的一切回路的长度均为偶数。回路的长度均为偶数。59第十四章图的根本概念第十四章图的根本概念 第三节：图的矩阵表示和运算第三节：

42、图的矩阵表示和运算 60图的矩阵表示图的矩阵表示矩阵是研讨图的有关性质的最有效的工具之一，矩阵是研讨图的有关性质的最有效的工具之一，可运用图的矩阵运算求出图的通路、回路和其可运用图的矩阵运算求出图的通路、回路和其它一些性质。它一些性质。前面讨论图的图解表示法的优点是直观，但缺陷前面讨论图的图解表示法的优点是直观，但缺陷是：是：1在结点较多时，用图表示非常繁杂，甚至没在结点较多时，用图表示非常繁杂，甚至没法表示；法表示；2计算机中难以储存。计算机中难以储存。本节讨论用矩阵表示图能较好的抑制以上二大缺本节讨论用矩阵表示图能较好的抑制以上二大缺陷。陷。 61图的矩阵表示图的矩阵表示定义定义14.23

43、 设无向图设无向图G，V=v1,v2,vn，E=e1,e2,em，令，令mij为顶点为顶点vi与边与边ej的关联的关联次数，那么称次数，那么称(mij)nm为为G的关联矩阵，记做的关联矩阵，记做M(G)。1 M(G)每列元素之和均为每列元素之和均为2。2 M(G)第第i行元素之和为行元素之和为vi的度数。的度数。3各顶点的度数之和等于边数的各顶点的度数之和等于边数的2倍倍4第第j列与第列与第k列一样当且仅当边列一样当且仅当边ej和和ek是平行边。是平行边。5 当且仅当当且仅当vi是孤立点是孤立点10mijjm62图的矩阵表示图的矩阵表示定义定义14.24 设有向图设有向图D中无环，中无环，V=

44、v1,v2,vn，E=e1,e2,em，令令mij 1 vi为为ej的始点的始点 0 vi与与ej不关联不关联 1 vi为为ej的终点的终点那么称那么称(mij)nm为为G的关联矩阵，记做的关联矩阵，记做M(D)。1M(D)中一切元素之和为中一切元素之和为0。2M(D)中，中，-1的个数等于的个数等于+1的个数，都等于边数的个数，都等于边数m。3第第i行中，行中，+1的个数等于的个数等于d+(vi)，-1的个数等于的个数等于d-(vi)。4平行边所对应的列一样。平行边所对应的列一样。63图的矩阵表示图的矩阵表示定义定义14.25：设：设D，是有向图，其中，是有向图，其中V=v1,v2,vn，并

45、假定各结点曾经有从，并假定各结点曾经有从v1到到vn的陈列次序。定义一个的陈列次序。定义一个nn的矩阵的矩阵A，并把其中各，并把其中各元素元素aij表示成：表示成： aij = vi邻接到邻接到 vj 边的条数边的条数那么称矩阵那么称矩阵A为图为图G的邻接矩阵。的邻接矩阵。例：设图例：设图D，如以以下图所示，其中，如以以下图所示，其中 V=v1,v2, v3,v4 64图的矩阵表示图的矩阵表示讨论定义：讨论定义：1假设图假设图D的邻接矩阵中的元素为的邻接矩阵中的元素为0和和1，又称为，又称为布尔矩阵。布尔矩阵。2图图D的邻接矩阵中的元素的次序是无关紧要的，的邻接矩阵中的元素的次序是无关紧要的，

46、只需进展行和行、列和列的交换，那么可得到一只需进展行和行、列和列的交换，那么可得到一样的矩阵。样的矩阵。65图的矩阵表示图的矩阵表示3当有向图中的有向边表示关系时，邻接矩阵就当有向图中的有向边表示关系时，邻接矩阵就是关系矩阵；是关系矩阵；假设图是自反的，那么主对角线的元素均为假设图是自反的，那么主对角线的元素均为1；假设图是对称的，那么对于假设图是对称的，那么对于i和和j有有aij=aji，主对角线，主对角线的元素不论。的元素不论。66图的矩阵表示图的矩阵表示4零图的邻接矩阵称为零矩阵，即矩阵中的一切零图的邻接矩阵称为零矩阵，即矩阵中的一切元素均为元素均为0；5在有向图的邻接矩阵中：在有向图的

47、邻接矩阵中：行中行中1的个数就是行中相应顶点的出度的个数就是行中相应顶点的出度列中列中1的个数就是列中相应顶点的入度的个数就是列中相应顶点的入度d+(1)=1,d-(1)=2 d+(2)=2,d-(2)=2 d+(3)=3,d-(3)=1 d+(4)=1,d-(4)=267qA(D)中一切元素之和为中一切元素之和为D中长度为中长度为1的通路的的通路的条数条数q对角线元素之和为对角线元素之和为D中长度为中长度为1的回路的条数的回路的条数q思索：思索：A(D)的的n次幂表示什么？次幂表示什么？图的矩阵表示图的矩阵表示68图的矩阵表示图的矩阵表示*矩阵的计算有向图中：矩阵的计算有向图中： 设：设： ， A69令令nknjinjikjikijijaaaaaaccCAAA1112,其含义为：其含义为：假设假设ai1a1j1，那么表，那么表示有示有i1j长度为长度为2的通路；的通路；A2表示表示i和和j之间具有长度之间具有长度为为2的不同通路的条数，的不同通路的条数，A3表示表示i和和j之间具有长度为之间具有长度为3的不同通路的条数，的不同通路的条数，A4表示表示i和和j之间具有长度为之间具有长度为4的不同通路的条数。的不同通路的条数。70例例2A3A