《第十四部分图的基本概念教学课件》由会员分享，可在线阅读，更多相关《第十四部分图的基本概念教学课件（79页珍藏版）》请在金锄头文库上搜索。
1、1第十四章图的基本概念第十四章图的基本概念第四部分：图论第四部分：图论2七桥问题七桥问题q问题问题v寻找走遍哥尼斯堡寻找走遍哥尼斯堡（Knigsberg）城的）城的7座桥，且只座桥，且只许走过每座桥一次，最后又回到许走过每座桥一次，最后又回到原出发点原出发点q求解求解v1736年瑞士大数学家欧拉年瑞士大数学家欧拉（LeonhardEuler）发表了关于）发表了关于“哥尼斯堡七桥问题哥尼斯堡七桥问题”的论文的论文（图论的第一篇论文）。他指出（图论的第一篇论文）。他指出从一点出发不重复的走遍七桥，从一点出发不重复的走遍七桥，最后又回到原来出发点是不可能最后又回到原来出发点是不可能的。的。3图论图论
2、 图论是近年来发展迅速而又应用广泛的一图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于一些数学游戏的门新兴学科。它最早起源于一些数学游戏的难题研究，如难题研究，如1736年欧拉（年欧拉（L.Euler)所解决的所解决的哥尼斯堡七桥问题。以及在民间广为流传的哥尼斯堡七桥问题。以及在民间广为流传的一些游戏问题：例如迷宫问题、棋盘上马的一些游戏问题：例如迷宫问题、棋盘上马的行走路线问题行走路线问题4棋盘上马的行走路线问题棋盘上马的行走路线问题q在中国象棋中，马走在中国象棋中，马走“日日”字，即每步从字，即每步从 12 矩形的一矩形的一个顶点跳到相对的顶点。如图，马从个顶点跳到相对的顶点。
3、如图，马从M（3，2）一次只）一次只能跳到能跳到A、B、C、D、E、F、G、H中的任何一个位置。中的任何一个位置。q问题：问题：马能否从棋盘上任意一点出发，不重复、不遗漏马能否从棋盘上任意一点出发，不重复、不遗漏地走遍整个棋盘（即每一点都走到并且只到一次）？地走遍整个棋盘（即每一点都走到并且只到一次）？ 5棋盘上马的行走路线问题棋盘上马的行走路线问题q将马目前所在位置涂成白色，用涂色的方法，将棋将马目前所在位置涂成白色，用涂色的方法，将棋盘上的点分为黑、白相间的两类盘上的点分为黑、白相间的两类6环游世界各国的问题环游世界各国的问题q英国数学家哈密顿于英国数学家哈密顿于1859年以游戏的形式提出
4、：年以游戏的形式提出：把一个把一个正十二面体的二十个顶点看成二十个城市，要求找出一正十二面体的二十个顶点看成二十个城市，要求找出一条经过每个城市恰好一次而回到出发点的路线。条经过每个城市恰好一次而回到出发点的路线。这条路这条路线就称线就称“哈密顿圈哈密顿圈”。一百多年来，对哈密顿问题的研。一百多年来，对哈密顿问题的研究，促进了图论的发展。究，促进了图论的发展。 7四色猜想四色猜想q问题：问题：任何一张地图只用任何一张地图只用四种颜色就能使具有共同四种颜色就能使具有共同边界的国家着上不同的颜边界的国家着上不同的颜色色q用数学语言表示，即：用数学语言表示，即：“将平面任意地细分为不相将平面任意地细
5、分为不相重叠的区域，每一个区域重叠的区域，每一个区域总可以用总可以用1，2，3，4这四这四个数字之一来标记，而不个数字之一来标记，而不会使相邻的两个区域得到会使相邻的两个区域得到相同的数字相同的数字” 8图论图论q图论不断发展，它在解决运筹学，网络图论不断发展，它在解决运筹学，网络理论，信息论，控制论，博奕论以及计理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出算机科学等各个领域的问题时，显示出越来越大的作用越来越大的作用9第十四章图的基本概念第十四章图的基本概念 第一节：图第一节：图 第二节：通路、回路、图的连通性第二节：通路、回路、图的连通性第三节：图的矩阵表示和运算第
6、三节：图的矩阵表示和运算 10第一节：图第一节：图q无序积：无序积：设设A，B为任意的两个集合，称为任意的两个集合，称 a,b | aA且且bB为为A与与B的无序积，记做的无序积，记做A&Bq无向图：无向图：一个无向图一个无向图G是一个二重组是一个二重组, 其其中中V(G)为有限非空结点（或叫顶点）集合为有限非空结点（或叫顶点）集合, E(G)是边是边的集合，它是的集合，它是无序积无序积V&V的多重子集，其元素为无向的多重子集，其元素为无向边，简称边。边，简称边。q有向图：有向图：一个有向图一个有向图G是一个二重组是一个二重组, 其其中中V(G)为有限非空结点（或叫顶点）集合为有限非空结点（或
7、叫顶点）集合, E(G)是边是边的集合，它是的集合，它是笛卡儿乘积笛卡儿乘积VV的多重子集，其元素为的多重子集，其元素为有向边，简称边。有向边，简称边。 11下面定义一些专门名词：下面定义一些专门名词：（）通通常常用用G G表表示示无无向向图图，D D表表示示有有向向图图，但但G G也也可可以以泛泛指指 图图 。 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阶图阶图
8、。（）若（）若|V(G)|,|E(G)|V(G)|,|E(G)|均为有限数，则称均为有限数，则称G G为为有限图有限图。（）若图（）若图G G中，边集为空，则称之为中，边集为空，则称之为零图零图， 若若G G为为n n阶图，则称之为阶图，则称之为n n阶零图，记为阶零图，记为N Nn n， N N1 1称为称为平凡图平凡图。（4 4）顶点集为空的图记为顶点集为空的图记为空图空图。第一节：图第一节：图12一些定义一些定义（5）称称顶顶点点或或边边用用字字母母标标定定的的图图为为标标定定图图，否否则则成成为为非非标标定定图图。另另外外，将将有有向向边边改改为为无无向向边边后后的的图图称为原图的称为
9、原图的基图基图。（6）设设G=为为无无向向图图，ek=(vi,vj)E,则则称称vi,vj为为ek的的端点端点， ek与与vi或或ek与与vj是是彼此关联彼此关联的。的。 若若vivj，则称，则称ek与与vi或或ek与与vj的关联次数为的关联次数为1， 若若vi=vj，则则称称ek与与vi的的关关联联次次数数为为2，并并称称为为环环。任任意意的的vlV，若若vlvi且且vlvj，则则称称ek与与vl的的关关联联次次数为数为0。13一些定义一些定义（7）设设无无向向图图G=，vi,vjV， ek,elE。若若存存在在etE，使使得得et=(vi,vj)，则则称称vi与与vj是是相相邻邻的的。若若
10、ek与与el至至少少有有一一个个公公共共端端点点，则则称称ek与与el是是相相邻邻的。的。 有有向向图图D=，vi,vjV，ek,elE 。若若存存在在etE，使使得得et=，则则称称vi为为et的的始始点点，vj为为et的的终终点点，并并称称vi邻邻接接到到vj，vj邻邻接接于于vi，若若ek的的终点为终点为el的始点，则称的始点，则称ek与与el相邻。相邻。14一些定义一些定义（8）设）设无向图无向图G=，对所有的，对所有的vV称称为为v的的邻域邻域，记为，记为NG(v)，并称并称NG(v) v为为v的的闭邻域闭邻域，记为，记为 。称称 为为v的的关联集关联集，记为，记为IG(v) 。设设
11、有向图有向图G=，对所有的，对所有的vV ，称，称为为v的的后继元素后继元素。称。称为为v的的先驱元素先驱元素。称两者之并为。称两者之并为v的的邻域邻域，记为，记为ND(v) 。称称ND(v) v，v的的闭邻域闭邻域。15一些定义一些定义定定义义14.3 在在无无向向图图中中，关关联联一一对对顶顶点点的的无无向向边边如如果果多多于于一一条条，则则称称这这些些边边为为平平行行边边，平平行行边边的的条条数数称称为为重重数。数。 在在有有向向图图中中，关关联联一一对对顶顶点点的的有有向向边边如如果果多多于于一一条条，并并且且这这些些边边的的始始点点和和终终点点相相同同，则则称称这这些些边边为为平平行
12、行边边。 含含平平行行边边的的图图称称为为多多重重图图，即即不不含含平平行行边边也也不不含含环环的的图称为图称为简单图简单图。16一些定义一些定义非多重图称为非多重图称为线图线图。由定义可见，简单图是没有环和平行边的图由定义可见，简单图是没有环和平行边的图。 17一些定义一些定义定定义义14.4：在在无无向向图图中中，任任意意点点其其作作为为边边的的端端点点次次数数之和称为该点的之和称为该点的度数度数，记为，记为dG(v). 在在有有向向图图中中，对对于于任任何何结结点点v，以以v为为始始点点的的边边的的条条数数，称称为为结结点点v的的引引出出次次数数(或或出出度度)，记记作作d+(v)；以以
13、v点点为为终终点点的的边边的的条条数数称称为为v的的引引入入次次数数(或或入入度度)，记记作作d(v)；结结点点的的v的的引引入入次次数数和和引引出出次次数数之之和和称称为为v的次数（度数），用的次数（度数），用d (v)表示。表示。由定义可见由定义可见:度数度数d (v)d+(v)d(v)。定定义义：最最大大度度，最最小小度度，最最大大出出度度，最最大大入入度度，最最小小入度，最小出度，悬挂点，悬挂边入度，最小出度，悬挂点，悬挂边18例例1例：例： d (a)(引入引入)+(引出引出)=5 d（b） d（c） d（1） d（2） d（3） 以后为了叙述方便，以后为了叙述方便，我们将具有我们将
14、具有n个结点个结点和和m条边的图简称为条边的图简称为（n,m）图）图19握手定理握手定理定理定理14.114.1（握手定理握手定理）：）：设设G是（是（n, m）无向图，）无向图，它的顶它的顶点集合点集合v1,v2,vn，于是有，于是有证明：证明：在无向图中引入一条边，总的次数增，在无向图中引入一条边，总的次数增，若有若有m m条边，则总次数为条边，则总次数为2m2m。（此定理也可推广到有向图和混合图）（此定理也可推广到有向图和混合图）定理定理14.1 14.1 在有向图中，则为：在有向图中，则为：20例例 2 d d（a a），）， d d（b b），）， d d（c c），）， d d（d
15、 d）, , m m，2m2mdd dd + + + + 21例例 3例：若图有例：若图有n n个顶点个顶点, ,（n+1n+1）条边，则中至）条边，则中至少有一个顶点的度数少有一个顶点的度数。证证明明：设设中中有有n n个个结结点点分分别别为为v v1 1,v,v2 2, , ,v vn n，则则由握手定理：由握手定理： dd（v vi i）（）（n+1n+1）而顶点的平均度数为：而顶点的平均度数为： d d（v vi i）(n+1)/n=2+1/n2 (n+1)/n=2+1/n2 顶点中至少有一个顶点的度数顶点中至少有一个顶点的度数22握手定理的推论握手定理的推论推论：推论：在图中，度数为
16、奇数的顶点必定有偶数个。在图中，度数为奇数的顶点必定有偶数个。 证明：设度数为偶数的顶点有证明：设度数为偶数的顶点有n n1 1个个, ,记为记为v veiei(i(i=1,2,=1,2,n n1 1),),度数为奇数的顶点有度数为奇数的顶点有n n2 2个，记为个，记为v voioi(i(i=1,2,=1,2,n,n2 2) )。由上一定理得。由上一定理得因为度数为偶数的各因为度数为偶数的各顶顶点次数之和为偶数。所以前一项点次数之和为偶数。所以前一项度数为偶数；若度数为偶数；若n n2 2为奇数，则第二项为奇数，两项之为奇数，则第二项为奇数，两项之和将为奇数，但这与上式矛盾。故和将为奇数，但
17、这与上式矛盾。故n n2 2必为偶数。必为偶数。问题：是否在一个部门的问题：是否在一个部门的25个人中间，由于意见不同，个人中间，由于意见不同，每个人恰好与每个人恰好与5个人意见一致？个人意见一致？23可图化、可简单图化可图化、可简单图化 设设G=为为一一个个n阶阶无无向向图图，Vv1,v2,vn，称称d(v1),d(v2)d(vn) 为为G的的度度数数列列。对对于于顶顶点点标标定定的无向图，它的度数列是唯一的。的无向图，它的度数列是唯一的。 反反之之，对对于于给给定定的的非非负负整整数数列列d=(d1,d2,dn),若若存存在在以以Vv1,v2,vn为为顶顶点点集集的的n阶阶无无向向图图G，
18、使得使得d(vi)=di，则称则称d是可图化的是可图化的。 特特别别的的，如如果果所所得得图图是是简简单单图图，则则称称d是是可可简简单单图图化的。化的。24可图化的判断定理可图化的判断定理定定理理14.3 14.3 设设非非负负整整数数列列d=(d=(d1,d2,dn), ), 则则d d是是可可图图化化的当且仅当的当且仅当 证明：证明：必要性显然必要性显然 充分性：构造性证明充分性：构造性证明定理定理14.4 14.4 设设G为任意为任意n阶无向简单图，阶无向简单图，则则(G) n-125可图化可图化q例：判断下列各非负整数列哪些是可图化的？例：判断下列各非负整数列哪些是可图化的？哪些是可
19、简单图化的？哪些是可简单图化的？(1)(5,5,4,4,2,1)(2)(5,4,3,2,2)(3)(3,3,3,1)(4)(d1,d2,dn), d1d2dn1, 且且 为偶数为偶数(5)(4,4,3,3,2,2)26同构的定义同构的定义定义定义14.5：设：设，和和，是两是两个图，若存在从到个图，若存在从到一双射函数：一双射函数：，使得，使得对任意的对任意的a,bV,a,b E当且仅当当且仅当g(a),g(b) ，并，并且且a,b和和g(a),g(b)有相同的重数，则称有相同的重数，则称和和同构同构。讨论定义：讨论定义：（1）和是同构的和是同构的,它们的顶点必须是一一对应的；它们的顶点必须是
20、一一对应的；（2）且且对对无无向向图图而而言言，还还要要保保持持顶顶点点之之间间的的邻邻接接关关系系和和边边的的重数；重数；（3）且且对对有有向向图图而而言言，不不但但要要保保持持顶顶点点之之间间的的邻邻接接关关系系，而而且还应保持且还应保持边的方向边的方向和边的重数。和边的重数。图图的的同同构构关关系系可可以以看看作作是是全全体体图图集集合合上上的的二二元元关关系系，并并且且此此关系是关系是等价关系等价关系。27例例4例：例： 存在一双射函数存在一双射函数:1,2,3,4a3,a4,a2,a1，其中：其中：顶点的一一对应顶点的一一对应： g(1)= a3; g(2)= a4; g(3)= a
21、2; 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）度数相同的顶点数相等。）度数相同的顶点数相等。但这但这不是充分条件不是充分条件。如下图。如下图30完全图完全图定义定义14.6：在个顶点的有向图：在个顶点的有向图G=中，如果每中，如果每
22、个顶点都邻接到其余的个顶点都邻接到其余的n-1个顶点，又邻接于其余个顶点，又邻接于其余的的n-1个顶点，则称个顶点，则称G为为有向完全图有向完全图；在个顶点；在个顶点的无向图的无向图G=中，每二个顶点之间均有一条中，每二个顶点之间均有一条边连接，则称边连接，则称G为为无向完全图无向完全图。31特殊图特殊图定定义义14.7：所所有有顶顶点点均均具具有有同同样样度度数数的的简简单单无无向向图图为为正则图正则图，各顶点的度数均为，各顶点的度数均为k k时称为时称为k k正则图正则图。32子图的定义子图的定义定义定义14.8:设设=,= 是二个图，是二个图， (a)若若 ， ，则称，则称是的是的子图子
23、图； (b)若若 ， ，并并且且，则则称称是的是的真子图真子图； (c)若若， ,则则称称是是的的生生成成子子图图（支撑子图支撑子图）。 (d)若若子子图图G 中中没没有有孤孤立立顶顶点点，G 由由E 唯唯一一确确定定，则则称称G 为为由边集由边集E 导出的子图导出的子图。 (e)若若在在子子图图G 中中，对对中中的的任任意意二二顶顶点点u,v，当当u,vE时时有有u,vE ，则则G 由由唯唯一一确确定定，此此时称时称G 为为由顶点集由顶点集导导出的子图出的子图。33例例 6例：图如下例：图如下 的真子图的真子图 生成子图：生成子图： E=,导出的子图由V=a,b,d,e导出的子图34例例 7
24、例例 画出画出4 4阶阶3 3边的所有非同构的无向简单图。边的所有非同构的无向简单图。解解：由由握握手手定定理理可可知知，该该无无向向简简单单图图各各顶顶点点度度数数之之和和为为6 6，最最大大度度小小于于或或等等于于3 3。于于是是所所求求无无向向简简单单图图的的度度数数列列应应满满足足的的条条件件是是，将将6 6分分成成4 4个个非非负负数数，每每个个整整数数均均大大于于等等于于0 0且且小小于于等等于于3 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将将每每种种度度数数列
25、列所所有有非非同同构构的的图图都都画画出出来来即即可可得得所所要要求求的全部非同构图。的全部非同构图。35补图补图定义定义14.9:设无向简单图设无向简单图G= 有有n个顶点，无向个顶点，无向简单图简单图H= 也有同样的顶点，而也有同样的顶点，而E是由是由n个顶点的完全图的边删去个顶点的完全图的边删去E所得，则图所得，则图H称为图称为图G的的补图补图。 自补图：自补图：H与与G同构同构36例例 8例例：试试画画出出5个个顶顶点点三三条条边边和和5个个顶顶点点七七条条边边的的简简单单无无向图。向图。解：解： 5个顶点三条边的图个顶点三条边的图5个顶点七条边的图（为个顶点七条边的图（为5顶点三条边
26、的补图）顶点三条边的补图）37图的操作图的操作关于图的四种操作：关于图的四种操作：（1）删去中的一条边）删去中的一条边e；（2）删删去去中中的的一一个个顶顶点点（即即是是删删去去顶顶点点和和与与有关联的所有边）。有关联的所有边）。（3）设设边边e=(u,v)E，用用Ge表表示示从从G中中删删除除e后后，将将e的的两两个个端端点点u,v用用一一个个新新的的顶顶点点w代代替替，使使w关关联联e以外以外u,v关联的所有边，称为关联的所有边，称为e的收缩的收缩。（4）设设u,vV，用用G(u,v)表表示示在在u,v之之间间加加一一条条边边(u,v)，称为，称为新加边新加边。38第十四章图的基本概念第十
27、四章图的基本概念 第二节：通路、回路、图的连通性第二节：通路、回路、图的连通性 3914.2 通路和回路通路和回路定义定义14.11: 在有向图中，从某一顶点出发经过某些点在有向图中，从某一顶点出发经过某些点边交替序列到达终点，此序列称为边交替序列到达终点，此序列称为通路通路。而经过的各条边之间没有相同的通路称为而经过的各条边之间没有相同的通路称为简单通路简单通路。如果通路中顶点各不相同且边也各不相同，则称为如果通路中顶点各不相同且边也各不相同，则称为初初级通路或路径级通路或路径。如果通路的起点和终点重合，称此通路为如果通路的起点和终点重合，称此通路为回路回路。没有。没有相同边的回路称为相同边
28、的回路称为简单回路简单回路，没有相同边也没有相，没有相同边也没有相同点（除起始点和终止点外）的回路称为同点（除起始点和终止点外）的回路称为圈圈。4014.2 通路和回路通路和回路讨论：讨论：（1）从从一一个个顶顶点点到到某某一一顶顶点点的的通通路路（若若有有的的话话）不不一定是唯一的；一定是唯一的；（2）通路的表示方法：通路的表示方法：(a)边点序列表示法：边点序列表示法： 设设，为为一一有有向向图图，viV，则则通通路路可可以以表示成：（表示成：（v1,e1,v2,e2,v3,vk-1,en,vk）(b)也可仅用边的序列表示也可仅用边的序列表示(c)顶点表示法顶点表示法(在简单图中在简单图中
29、)：（：（ 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有无限条通路，有无限条通路，中间有回路；中间有回路；（2）上例中的）上例中的P1 ，P2， P3， P5为简单通路。为简单通路。42通路的性质通路的性质定义定义:通路通路
30、P中边的条数称为通路中边的条数称为通路P的长度的长度（路长）。（路长）。长度为长度为0的通路定义为一个单独的顶点。的通路定义为一个单独的顶点。定理定理14.5:设图，是中的顶点数设图，是中的顶点数（即），如果从（即），如果从v1到到v2(v1v2)有一条通有一条通路，则从路，则从v1到到v2有一条长度不大于有一条长度不大于n-1的通路。的通路。 推论推论:设图，是中的顶点数（即设图，是中的顶点数（即），如果从），如果从v1到到v2(v1v2)有一条通路，有一条通路，则从则从v1到到v2有一条长度不大于有一条长度不大于n-1的初级通路（路的初级通路（路径）。径）。43通路和回路的性质通路和回路的
31、性质定理定理14.6：在阶图中，从：在阶图中，从vi到到vi如果存在一条回路如果存在一条回路的话，则从的话，则从vi到到vi一定存在一条长度小于或等于一定存在一条长度小于或等于的回路。的回路。推论：在阶图中，从推论：在阶图中，从vi到到vi如果存在一条简单回路如果存在一条简单回路的话，则从的话，则从vi到到vi一定存在一条长度小于或等于一定存在一条长度小于或等于的初级回路。的初级回路。44通路和回路通路和回路q例：例： 1. 无向完全图无向完全图Kn（n3）中有几种非同构的圈）中有几种非同构的圈？ 2. 无向完全图无向完全图K3的顶点依次标定为的顶点依次标定为a，b，c. 在定义意义下在定义意
32、义下K3中有多少中有多少 不同的长度为不同的长度为3的圈？的圈？ 4514.3 图的连通性图的连通性定定义义14.12：设设无无向向图图=，且且vi,vjV，若若从从vi到到vj存存在在一一条条通通路路的的话话，则则称称vi，vj是是连连通通的的。一一般认为般认为vi到自身是连通的。到自身是连通的。由由定定义义可可见见：连连通通的的概概念念与与vi到到vj之之间间的的通通路路多多少少、通路长度、是什么样的通路没有任何关系。通路长度、是什么样的通路没有任何关系。4614.3 图的连通性图的连通性连通性一定满足：连通性一定满足：（）（）自反性：自反性： vi到到vi一定是连通的。一定是连通的。（）
33、可可传传递递性性： 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距离距离定义定义14.14: 在无向图在无向图G=中，从顶点中，从顶点vi到到vj最短最短通路（短程线）的长度，叫做从通路（短程线）的长度，叫做从vi到到vj的的距离距离，记，记为为d(vi, vj)
35、 。若从。若从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= 。若存在。若存在 使得使得p(G-V) p(G)，且有任意的均有，且有任意的均有p(G-V) =p(G)，则称，则称V为为G的的点割集点割集。若是单个点，则称。若是单个点，则称割点割点。q定义定义14.16 设无向
36、图设无向图 G= 。若存在。若存在 使得使得p(G-E) p(G)，且有任意的均有，且有任意的均有p(G-E) =p(G)，则称，则称E为为G的的边割集边割集。若是单个边，则称。若是单个边，则称割边割边或者或者桥桥。q点连通度点连通度k-连通图连通图 注意：注意：若若G是是k-连通图，则在连通图，则在G中删除任何中删除任何k-1个顶点个顶点后，所得图一定还是连通的后，所得图一定还是连通的q边连通度边连通度 r边边-连通图连通图51点连通度、边连通度的关系点连通度、边连通度的关系q对于任何无向图对于任何无向图G，有，有52距离距离定定义义14.19：设设有有向向图图=，且且vi,vjV，若若从从
37、vi到到vj存存在在一一条条通通路路的的话话，则则称称vi可可达达vj。一一般般认认为为vi到到自自身身是是可可达达的的。若若vi可可达达vj并并且且vj可可达达vi，则则称称vi,vj相互可达相互可达。定义定义14.20: 在有向图在有向图G=中，从顶点中，从顶点vi到到vj最短最短通路（短程线）的长度，叫做从通路（短程线）的长度，叫做从vi到到vj的的距离距离，记，记为为d(vi, vj) 。若从。若从vi到到vj不存在通路，则不存在通路，则d(vi, vj) =。53连通性连通性定定义义14.22：在在有有向向图图中中，它它的的基基图图若若是是连连通通的的，则则称称此此有有向向图图为为弱
38、弱连连通通的的；若若图图中中任任何何顶顶点点偶偶对对中中至至少少有有一一点点到到另另一一顶顶点点是是可可达达的的，则则称称此此图图是是单单向向连连通通的的；如如果果任任两两顶顶点点均均是是互互相相可可达达的的，则则称称是是强强连连通通的。的。讨论定义：讨论定义：（1）强连通的一定是单向连通的和弱连通的；）强连通的一定是单向连通的和弱连通的；（2）单向连通的一定是弱连通的；）单向连通的一定是弱连通的；（3）弱弱连连通通的的既既可可能能不不是是单单向向连连通通的的，更更可可能能不不是是强连通的。强连通的。54连通性连通性 强连通的强连通的 单向连通的弱连通的单向连通的弱连通的55图的连通性图的连通
39、性定理定理14.8 设有向图设有向图D=，Vv1,v2,vn 。D是是强连通图强连通图当且仅当当且仅当D中存在经过每个顶点至少一中存在经过每个顶点至少一次的次的回路回路。证明：充分性显然证明：充分性显然必要性（构造性证明）必要性（构造性证明）定理定理14.9 设设D是是n阶有向图。阶有向图。D是是单向连通图单向连通图当且仅当当且仅当D中存在经过每个顶点至少一次的中存在经过每个顶点至少一次的通路通路。56二部图二部图定定义义14.23:14.23:如如果果无无向向图图的的顶顶点点集集V V分分成成两两个个子子集集X,Y,(X,Y,(即即满满足足XY=,XY=V),XY=,XY=V),使使得得G
40、G中中任任意意一一边边的的两两个个端端点点分分属属于于X X和和Y,Y,则则称称G G为为二二部部图图, ,X X和和Y Y称称为为互补顶点子集互补顶点子集, ,常记图为常记图为G=G=。 定定义义: :若若二二部部图图G=G=中中X X的的每每个个顶顶点点与与Y Y的的每每个个顶顶点点都都有有且且只只有有一一条条边边相相关关联联, ,称称G G为为完完全全二二部部图图, ,记记为为K Km,nm,n, ,其中其中|X|=|X|=m,|Ym,|Y|=n|=n。57例例4 abxyza x y z b 子集子集X=a,b,Y=x,y,z,这是一个二部图。这是一个二部图。这是完全二部图这是完全二部
41、图K2,3。58二部图二部图此两图均是此两图均是K3,3因而是同构的因而是同构的 定定理理14.10:无无向向图图G是是二二部部图图的的充充要要条条件件是是G的的所所有有回路的长度均为偶数。回路的长度均为偶数。59第十四章图的基本概念第十四章图的基本概念 第三节：图的矩阵表示和运算第三节：图的矩阵表示和运算 60图的矩阵表示图的矩阵表示矩矩阵阵是是研研究究图图的的有有关关性性质质的的最最有有效效的的工工具具之之一一，可可运运用用图图的的矩矩阵阵运运算算求求出出图图的的通通路路、回回路路和和其其它一些性质。它一些性质。前前面面讨讨论论图图的的图图解解表表示示法法的的优优点点是是直直观观，但但缺缺
42、点点是：是：（1）在在结结点点较较多多时时，用用图图表表示示十十分分繁繁杂杂，甚甚至至没没法表示；法表示；（2）计算机中难以贮存。）计算机中难以贮存。本本节节讨讨论论用用矩矩阵阵表表示示图图能能较较好好的的克克服服以以上上二二大大缺缺点。点。 61图的矩阵表示图的矩阵表示定定义义14.23 设设无无向向图图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的度数。的度数。
43、3）各顶点的度数之和等于边数的）各顶点的度数之和等于边数的2倍倍4）第）第j列与第列与第k列相同当且仅当边列相同当且仅当边ej和和ek是平行边。是平行边。5） 当且仅当当且仅当vi是孤立点是孤立点62图的矩阵表示图的矩阵表示定定义义14.24 设设有有向向图图D中中无无环环，V=v1,v2,vn，E=e1,e2,em，令令mij 1 vi为为ej的始点的始点 0 vi与与ej不关联不关联 1 vi为为ej的终点的终点则称则称(mij)nm为为G的的关联矩阵关联矩阵，记做，记做M(D)。1）M(D)中所有元素之和为中所有元素之和为0。2）M(D)中，中，-1的个数等于的个数等于+1的个数，都等于
44、边数的个数，都等于边数m。3）第）第i行中，行中，+1的个数等于的个数等于d+(vi)，-1的个数等于的个数等于d-(vi)。4）平行边所对应的列相同。）平行边所对应的列相同。63图的矩阵表示图的矩阵表示定定义义14.25：设设D，是是有有向向图图，其其中中V=v1,v2,vn，并并假假定定各各结结点点已已经经有有从从v1到到vn的的排排列列次次序序。定定义义一一个个nn的的矩矩阵阵A，并并把把其其中中各各元元素素aij表示成：表示成： aij = vi邻接到邻接到 vj 边的条数边的条数则称矩阵则称矩阵A为图为图G的的邻接矩阵邻接矩阵。例例：设设图图D，如如下下图图所所示示，其其中中 V=v
45、1,v2, v3,v4 64图的矩阵表示图的矩阵表示讨论定义：讨论定义：（1）若若图图D的的邻邻接接矩矩阵阵中中的的元元素素为为0和和1，又又称称为为布布尔矩阵。尔矩阵。（2）图图D的的邻邻接接矩矩阵阵中中的的元元素素的的次次序序是是无无关关紧紧要要的的，只只要要进进行行行行和和行行、列列和和列列的的交交换换，则则可可得得到到相相同同的矩阵。的矩阵。65图的矩阵表示图的矩阵表示（3）当当有有向向图图中中的的有有向向边边表表示示关关系系时时，邻邻接接矩矩阵阵就就是关系矩阵；是关系矩阵；若图是自反的，则主对角线的元素均为若图是自反的，则主对角线的元素均为1；若若图图是是对对称称的的，则则对对于于i
46、和和j有有aij=aji，主主对对角角线线的的元元素素不论。不论。66图的矩阵表示图的矩阵表示（4）零零图图的的邻邻接接矩矩阵阵称称为为零零矩矩阵阵，即即矩矩阵阵中中的的所所有有元素均为元素均为0；（5）在有向图的邻接矩阵中：）在有向图的邻接矩阵中：行中行中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
47、对角线元素之和为对角线元素之和为D中长度为中长度为1的回路的条数的回路的条数q考虑：考虑：A(D)的的n次幂表示什么？次幂表示什么？图的矩阵表示图的矩阵表示68图的矩阵表示图的矩阵表示*矩阵的计算（有向图中）：矩阵的计算（有向图中）： 设：设： 69令令其含义为：其含义为：若若ai1a1j1，则则表表示示有有i1j长度为长度为2的通路；的通路；A2表表示示i和和j之之间间具具有有长长度度为为2的不同通路的条数，的不同通路的条数，A3表示表示i和和j之间具有长度为之间具有长度为3的不同的不同通路通路的条数，的条数，A4表示表示i和和j之间具有长度为之间具有长度为4的不同的不同通路通路的条数。的条
48、数。70例例从从21有二条长度为有二条长度为2的通路；的通路；从从31有二条长度为有二条长度为3的通路的通路;从从21有二条长度为有二条长度为4的通路；的通路；71图的矩阵表示图的矩阵表示定定理理14.11：设设，|V|=，A为为G的的邻邻接接矩矩阵阵，则则Am的的元元素素表表示示（i ,j）之之间间具具有有长长度度为为m的的不不同同通通路路数数，（i ,j）表表示示矩矩阵阵Am中中的的一一个个记记入入值值。（长度为（长度为m的路径条数）的路径条数）推推论论：设设，|V|=，二二个个顶顶点点之之间间的的距距离离d(vi,vj)可可以以从从A1,A2, An中中去去求求得得，当当（i ,j）记记
49、入入值值不不为为零零且且矩矩阵阵的的幂幂次次最最小小时时，这这个个幂幂次次即即是是d(vi,vj) 。由推论由推论1可以求得一个图的距离矩阵。可以求得一个图的距离矩阵。72例例73图的矩阵表示图的矩阵表示推推论论：Bn = A1A2An表表示示i到到j之之间间的的长长度度小小于于等于等于n的所有通路数，的所有通路数， A1表示长度为表示长度为1的通路数。的通路数。 An表示长度为表示长度为n的通路数。的通路数。（注意：注意：Bn是是A1,A2, An中各对应位数字相加之和）中各对应位数字相加之和） 74图的矩阵表示图的矩阵表示定定义义14.27：设设D，是是有有向向图图，其其中中|V|=，假假
50、定定D中中各各结结点点是是有有序序的的，定定义义一一个个nn矩矩阵阵P，它的元素为：它的元素为：则则P称为图称为图D的的可达性矩阵可达性矩阵。75图的矩阵表示图的矩阵表示讨论定义：讨论定义：可达性矩阵中的元素为可达性矩阵中的元素为0和和1，它是布尔矩阵；它是布尔矩阵；可可达达性性矩矩阵阵只只能能表表示示vi到到vj有有无无通通路路，而而不不能能指指明明存在的所有通路，这和邻接矩阵是不相同的；存在的所有通路，这和邻接矩阵是不相同的；可可达达性性矩矩阵阵P并并没没有有表表达达出出每每一一个个元元素素自自身身可可达达的的概概念念，若若实实际际情情况况需需要要，可可规规定定：主主对对角角线线上上的的元
51、素均用元素均用1表示（表示（自己到自己是可达的）自己到自己是可达的）76图的矩阵表示图的矩阵表示下面介绍下面介绍可达性矩阵可达性矩阵的求法：的求法：其其方方法法是是：若若Bn-1中中（i ,j）是是非非“0”元元素素，则则对对应应的的Pi,j=1，否则，否则Pi,j =0。 例：例： 77图的矩阵表示图的矩阵表示由定义：若由定义：若 由B3可得：表示任何结点之间是可达的。表示任何结点之间是可达的。78图的运算图的运算定义定义14.29：设图：设图G1=和图和图G2=（）G1和和G2的的并并，定定义义为为图图G3= ，其其中中E3E1E2, V3为为E1E2中中边边关关联联的的顶顶点点集集，记记为为G3G1G2。（）G1和和G2的的交交运运算算定定义义为为图图G3= ，其其中中，E3E1E2, V3为为E1E2中中边边关关联联的的顶顶点点集集，记记为为G3G1 G2。（）G1和和G2的的差差运运算算定定义义为为图图G3= ，其其中中，E3E1E2, V3为为E3中中边边所所关关联联的的顶顶点点集集，记记为为G3G1G2。（）（）G1和和G2的的环和环和运算定义为运算定义为G3= ， G3=(G1G2)(G1G2)，记为，记为G1 G2 。79作业作业q5，6，11，14，17q21，23，25，33，40q44，46，47
