《图的基本概念#学习材料》由会员分享，可在线阅读，更多相关《图的基本概念#学习材料（81页珍藏版）》请在金锄头文库上搜索。
1、第第1414章章 图的基本概念图的基本概念离离 散散 数数 学学中国地质大学本科生课程中国地质大学本科生课程本章内容本章内容本章内容本章内容14.1 14.1 图图14.2 14.2 通路与回路通路与回路14.3 14.3 图的连通性图的连通性14.4 14.4 图的矩阵表示图的矩阵表示14.5 14.5 图的运算图的运算基本要求基本要求作业作业2课件精选14.1 14.1 14.1 14.1 图的基本概念图的基本概念图的基本概念图的基本概念q图的定义图的定义q图的一些概念和规定图的一些概念和规定q简单图和多重图简单图和多重图q顶点的度数与握手定理顶点的度数与握手定理q图的同构图的同构q完全图
2、与正则图完全图与正则图q子图与补图子图与补图3课件精选无序积与多重集合无序积与多重集合无序积与多重集合无序积与多重集合 q元元素素可可以以重重复复出出现现的的集集合合称称为为多多重重集集合合或或者者多多重重集集，某某元元素重复出现的次数称为该元素的素重复出现的次数称为该元素的重复度重复度。例如例如 在多重集合在多重集合 a, ,a, ,b, ,b, ,b, ,c, ,d 中，中， a, ,b, ,c, ,d的重复度分别为的重复度分别为2,3,1,12,3,1,1。 4课件精选定义定义14.114.1 一个一个无向图无向图是一个有序的二元组是一个有序的二元组 ,E,记作记作G G，其中其中（1
3、1）VV称为称为顶点集顶点集，其元素称为，其元素称为顶点顶点或或结点结点。（2 2）E E称为称为边集边集，它是，它是无序积无序积V&VV&V的多重子集，其元素称为的多重子集，其元素称为无向无向边边，简称，简称边边。定义定义14.214.2 一个一个有向图有向图是一个有序的二元组是一个有序的二元组 E，记作记作D D，其中其中（1 1）VV称为称为顶点集顶点集，其元素称为，其元素称为顶点顶点或或结点结点。（2 2）E E为为边集边集，它是，它是笛卡儿积笛卡儿积VVVV的多重子集，其元素称为的多重子集，其元素称为有向有向边边，简称，简称边边。无向图和有向图无向图和有向图无向图和有向图无向图和有向
4、图说明说明q可以用图形表示图，即用小圆圈（或实心点）表示顶可以用图形表示图，即用小圆圈（或实心点）表示顶点，用顶点之间的连线表示无向边，用有方向的连线点，用顶点之间的连线表示无向边，用有方向的连线表示有向边。表示有向边。 5课件精选例例例例14.114.114.114.1例例14.114.1 (1) (1) 给定无向图给定无向图G G，其中其中 V Vvv1 1,v,v2 2,v,v3 3,v,v4 4,v,v5 5 ，E=(vE=(v1 1,v,v1 1),(v),(v1 1,v,v2 2),(v),(v2 2,v,v3 3),(v),(v2 2,v,v3 3),(v),(v2 2,v,v5
5、 5),(v),(v1 1,v,v5 5),(v),(v4 4,v,v5 5). ). (2) (2) 给定有向图给定有向图D=D=，其中其中 V Va,b,c,da,b,c,d，E E,。 画出画出G G与与D D的图形。的图形。6课件精选图的一些概念和规定图的一些概念和规定图的一些概念和规定图的一些概念和规定qG G表示无向图，但有时用表示无向图，但有时用G G泛指图泛指图( (无向的或有向的无向的或有向的) )。qD D只能表示有向图。只能表示有向图。qV(G)V(G)，E(G)E(G)分别表示分别表示G G的的顶点集顶点集和和边集边集。q若若| |V(G)|V(G)|n n，则称则称G
6、 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阶零图阶零图，记作，记作N Nn n，特别地，称特别地，称N N1 1为为平凡图平凡图。 q在图的定义中规定顶点集在图的定义中规定顶点集V V为非空集，但在图的运算中可能产为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定生顶点集为空集的运算结果，为此规定顶点集为空集的图顶点集为空集的图为为空空图图，并将空
7、图记为，并将空图记为。 7课件精选标定图与非标定图、基图标定图与非标定图、基图标定图与非标定图、基图标定图与非标定图、基图 q将图的集合定义转化成图形表示之后，常用将图的集合定义转化成图形表示之后，常用e ek k表示表示无向边无向边( (v vi i,v,vj j) )（或或有向边有向边 ），），并称并称顶点或边用字母标定顶点或边用字母标定的图的图为为标定图标定图，否则称为，否则称为非标定图非标定图。q将有向图各将有向图各有向边均改成无向边后的无向图有向边均改成无向边后的无向图称为原来图的称为原来图的基图基图。q易知标定图与非标定图是可以相互转化的，任何无向图易知标定图与非标定图是可以相互转
8、化的，任何无向图G G的各边均加上箭头就可以得到以的各边均加上箭头就可以得到以G G为基图的有向图。为基图的有向图。 8课件精选关联与关联次数、环、孤立点关联与关联次数、环、孤立点关联与关联次数、环、孤立点关联与关联次数、环、孤立点 q设设G G为无向图，为无向图，ek( (vi, ,vj)E)E，称称vi, ,vj为为ek的端点的端点，ek与与vi或或ek与与vj是彼此相是彼此相关联关联的。的。若若vivj，则称则称ek与与vi或或ek与与vj的的关联次数为关联次数为1 1。若若vivj，则称则称ek与与vi的的关联次数为关联次数为2 2，并称，并称ek为为环环。 若端点若端点vl不与边不与
9、边ek关联，则称关联，则称ek与与vl的的关联次数为关联次数为0 0。 q设设D D为有向图，为有向图，ek EE，称称vi, ,vj为为ek的的端点。端点。若若vivj，则称则称ek为为D D中的中的环环。q无论在无向图中还是在有向图中，无边关联的顶点均称为无论在无向图中还是在有向图中，无边关联的顶点均称为孤立孤立点点。 9课件精选相邻与邻接相邻与邻接相邻与邻接相邻与邻接 q设无向图设无向图G GVE，vi，vjVV，ek，elEE。若若 etEE，使得使得et( (vi，vj) )，则称则称vi与与vj是是相邻的相邻的。若若ek与与el至少有一个公共端点至少有一个公共端点，则称，则称ek与
10、与el是是相邻的相邻的。 q设有向图设有向图D DVE，vi，vjVV，ek，elEE。若若 etEE，使得使得et ，则称则称vi为为et的的始点始点，vj为为et的的终终点点，并称，并称vi邻接到邻接到vj ， vj邻接于邻接于vi。若若ek的终点为的终点为el的始点，则称的始点，则称ek与与el相邻相邻。10课件精选邻域邻域邻域邻域q设无向图设无向图G ， vV，称称 u| |uV(u, ,v)Euv 为为v的的邻域邻域，记做，记做NG( (v) )。称称NG G( (v)v 为为v的的闭邻域闭邻域，记做，记做NG(v)(v)。称称 e| |eEe与与v相关联相关联 为为v的的关联集关联
11、集，记做，记做IG( (v) )。q设有向图设有向图D ， vV，称称 u| |uVV EEuv 为为v的的后继元集后继元集，记做，记做+ +D( (v)v)。称称 u| |uVV EEuv 为为v的的先驱元集先驱元集，记做，记做- -D( (v)v)。称称+ +D D( (v)- -D D( (v) )为为v的的邻域邻域，记做，记做ND( (v) )。称称ND( (v)v 为为v的的闭邻域闭邻域，记做，记做ND( (v) )。11课件精选举例举例举例举例N NG G( (v1 1) ) + +D( (d ) ) v2 2，v5 5 NG(v1) v1 1，v2 2，v5 5 I IG G(
12、(v1 1) ) e1 1，e2 2，e3 3 c - -D(D(d ) ) a，c N ND D( (d ) ) a，c N ND D( (d ) ) a，c，d 12课件精选简单图与多重图简单图与多重图简单图与多重图简单图与多重图 定义定义14.314.3 在无向图中，关联一对顶点的无向边如果在无向图中，关联一对顶点的无向边如果多于多于1 1条条，则称这些边为则称这些边为平行边平行边，平行边的条数称为，平行边的条数称为重数重数。在有向图中，关联一对顶点的有向边如果在有向图中，关联一对顶点的有向边如果多于多于1 1条条，并且这些，并且这些边的边的始点和终点相同始点和终点相同( (也就是它们的
13、方向相同也就是它们的方向相同) )，则称这些边，则称这些边为为平行边平行边。含平行边的图称为含平行边的图称为多重图多重图。既不含平行边也不含环的图既不含平行边也不含环的图称为称为简单图简单图。例如：例如：在图在图14.114.1中，中，( (a)a)中中e e5 5与与e e6 6是平行边，是平行边，( (b)b)中中e e2 2与与e e3 3是平行边，但是平行边，但e e6 6与与e e7 7不是平行边。不是平行边。( (a)a)和和( (b)b)两个图都不是简单图。两个图都不是简单图。13课件精选顶点的度数顶点的度数顶点的度数顶点的度数定义定义14.414.4 设设G G为一无向图，为一
14、无向图， vVV，称称v作为边的端点作为边的端点次数之和为次数之和为v的度数的度数，简称为，简称为度度，记做，记做 dG( (v) )。在不发生混淆时，简记为在不发生混淆时，简记为d( (v) )。设设D DVE为有向图，为有向图， vVV，称称v作为边的始点次数之和为作为边的始点次数之和为v的出度的出度，记做，记做d+ +D( (v) )，简记作简记作d+ +( (v) )。称称v作为边的终点次数之和为作为边的终点次数之和为v的入度的入度，记做，记做d -D( (v) )，简记作简记作d- -( (v) )。称称d+ +( (v)+)+d- -( (v) )为为v v的的度数度数，记做，记做
15、d( (v) )。14课件精选图的度数的相关概念图的度数的相关概念图的度数的相关概念图的度数的相关概念q在无向图在无向图G G中，中，最大度最大度(G)G)maxmaxd( (v)|)|vV(G)V(G)最小度最小度(G)(G)mind(mind(v)|)|vV(G) V(G) q在有向图在有向图D D中，中，最大出度最大出度+ +( (D)D)maxmaxd+ +( (v)|)|vV(D)V(D)最小出度最小出度+ +(D)(D)minmind+ +( (v)|)|vV(D)V(D)最大入度最大入度- -(D)(D)maxmaxd- -( (v)|)|vV(D)V(D)最小入度最小入度- -
16、(D)(D)minmind- -( (v)|)|vV(D)V(D)q称度数为称度数为1 1的顶点为的顶点为悬挂顶点悬挂顶点，与它关联的边称为，与它关联的边称为悬挂边悬挂边。度为偶数度为偶数( (奇数奇数) )的顶点称为的顶点称为偶度偶度( (奇度奇度) )顶点顶点。 15课件精选图的度数举例图的度数举例图的度数举例图的度数举例d( (v1 1) )4(4(注意，环提供注意，环提供2 2度度) )，4 4，1 1，v4 4是悬挂顶点，是悬挂顶点，e7 7是悬挂边。是悬挂边。d+ +( (a) )4 4，d- -( (a) )1 1( (环环e1 1提供出度提供出度1 1，提供入度，提供入度1)1
17、)，d( (a) )4+14+15 5。5 5，3 3，+ +4 (4 (在在a点达到点达到) )+ +0(0(在在b点达到点达到) )- -3(3(在在b点达到点达到) )- -1(1(在在a和和c点达到点达到) ) 16课件精选握手定理握手定理握手定理握手定理定理定理14.114.1 设设G G为任意无向图，为任意无向图，V V v1 1, ,v2 2, , ,vn ，|E|E|m，则则说明说明任何无向图中，各顶点度数之和等于边数的两倍。任何无向图中，各顶点度数之和等于边数的两倍。证明证明G G中每条边中每条边( (包括环包括环) )均有两个端点，均有两个端点，所以在计算所以在计算G G中
18、各顶点度数之和时，中各顶点度数之和时，每条边均提供每条边均提供2 2度，当然，度，当然，m条边，共提供条边，共提供2 2m度。度。 定理定理14.2 14.2 设设D D为任意有向图，为任意有向图，V V v1 1, ,v2 2, , ,vn ，|E|E|m，则则 17课件精选握手定理的推论握手定理的推论握手定理的推论握手定理的推论推论推论任何图任何图( (无向的或有向的无向的或有向的) )中，奇度顶点的个数是偶数。中，奇度顶点的个数是偶数。 证明证明设设G GVE为任意一图，令为任意一图，令V V1 1 v| |vVVd( (v) )为奇数为奇数 V V2 2 v| |vVVd( (v) )
19、为偶数为偶数 则则V V1 1VV2 2V V，V V1 1VV2 2 ，由握手定理可知由握手定理可知 由于由于2 2m和和，所以，所以为偶数为偶数，但因但因V V1 1中顶点度数为奇数，中顶点度数为奇数， 所以所以| |V V1 1| |必为偶数。必为偶数。18课件精选问题研究问题研究问题研究问题研究问题：问题：在一个部门的在一个部门的2525个人中间，由于意见不同，是否可能每个个人中间，由于意见不同，是否可能每个人恰好与其他人恰好与其他5 5个人意见一致？个人意见一致？解答：解答：不可能不可能。考虑一个图，其中顶点代表人，如果两个人意见。考虑一个图，其中顶点代表人，如果两个人意见相同，可用
20、边连接，所以每个顶点都是奇数度。存在奇数个度相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。数为奇数的图，这是不可能的。说明：说明：(1)(1)很多离散问题可以用图模型求解。很多离散问题可以用图模型求解。(2)(2)为了建立一个图模型，需要决定顶点和边分别代表什么。为了建立一个图模型，需要决定顶点和边分别代表什么。(3)(3)在一个图模型中，边经常代表两个顶点之间的关系。在一个图模型中，边经常代表两个顶点之间的关系。19课件精选度数列度数列度数列度数列设设G G为一个为一个n阶无向图，阶无向图，V V v1 1, ,v2 2, , ,vn ，称称d( (v1
21、1) )，d( (v2 2) )，d( (vn n) )为为G G的的度数列度数列。对于顶点标定的无向图，它的度数列是唯一的。对于顶点标定的无向图，它的度数列是唯一的。反之，对于给定的非负整数列反之，对于给定的非负整数列d d1 1, ,d2 2, , ,dn ，若存在若存在V V v1 1, ,v2 2, , ,vn 为顶点集的为顶点集的n阶无向图阶无向图G G，使得使得d( (vi) )di，则称则称d是是可图化的可图化的。特别地，若所得图是简单图，则称特别地，若所得图是简单图，则称d是是可简单图化的可简单图化的。类似地，设类似地，设D D为一个为一个n n阶有向图，阶有向图，V V v1
22、 1, ,v2 2, , ,vn ，称称d( (v1 1) )，d( (v2 2) )，d( (vn) )为为D D的的度数列度数列，另外称，另外称d+ +( (v1 1) )，d+ +( (v2 2) )，d+ +( (vn) )与与d- -( (v1 1) )，d- -( (v2 2) )，d- -( (vn) )分别为分别为D D的的出度列出度列和和入度列入度列。20课件精选度数列举例度数列举例度数列举例度数列举例按顶点的标定顺序，度数列为按顶点的标定顺序，度数列为4,4,2,1,34,4,2,1,3。按字母顺序，度数列，出度列，入按字母顺序，度数列，出度列，入度列分别为度列分别为5,3
23、,3,35,3,3,34,0,2,14,0,2,11,3,1,21,3,1,221课件精选可图化的充要条件可图化的充要条件可图化的充要条件可图化的充要条件定理定理14.314.3 设非负整数列设非负整数列d( (d1 1，d2 2，dn) )，则则d d是可图化的当是可图化的当且仅当且仅当 证明证明必要性。必要性。由握手定理显然得证。由握手定理显然得证。充分性。充分性。由已知条件可知，由已知条件可知，d中有偶数个奇数度点。中有偶数个奇数度点。奇数度点两两之间连一边，剩余度用环来实现。奇数度点两两之间连一边，剩余度用环来实现。533122课件精选可图化举例可图化举例可图化举例可图化举例由定理由定
24、理14.314.3立即可知，立即可知，(3,3,2,1)(3,3,2,1)，(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)等是可图化的。等是可图化的。 24课件精选定理定理定理定理14.414.414.414.4定理定理14.414.4 设设G G为任意为任意n阶无向简单图，则阶无向简单图，则(G)G)n-1-1。 证明证明因为因为G G既无平行边也无环，既无平行边也无环，所以所以G G中任何顶点中任何顶点v至多与其余的至多与其余的n-1-1个顶点均相邻，个顶点均相邻，于是于是d(
25、(v)n-1-1，由于由于v v的任意性，所以的任意性，所以(G)G)n-1-1。例例14.214.2 判断下列各非负整数列哪些是可图化的？哪些是可简判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？单图化的？(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矛盾。矛盾。 25课件精选
26、例例例例14.214.214.214.2(3) (3,3,3,1)(3) (3,3,3,1)可图化，不可简单图化。假设该序列可以简单图化，可图化，不可简单图化。假设该序列可以简单图化，设设G GVE以该序列为度数列。以该序列为度数列。不妨设不妨设V Vvv1 1,v,v2 2,v,v3 3,v,v4 4 且且 d(vd(v1 1) )d(vd(v2 2) )d(vd(v3 3) )3,d(v3,d(v4 4) )1 1，由于由于d(vd(v4 4) )1 1，因而因而v v4 4只能与只能与v v1 1，v v2 2，v v3 3之一相邻，之一相邻，于是于是v v1 1，v v2 2，v v3
27、 3不可能都是不可能都是3 3度顶点，这是矛盾的，度顶点，这是矛盾的，因而因而(3)(3)中序列也不可简单图化。中序列也不可简单图化。 (4) (4) (d d1 1,d,d2 2, ,d dn n) )，d d1 1dd2 2 ddn n1 1 且且 为偶数。为偶数。 可图化，不可简单图化。可图化，不可简单图化。26课件精选例例例例14.214.214.214.2(5) (4,4,3,3,2,2) (5) (4,4,3,3,2,2) 可简单图化。下图中两个可简单图化。下图中两个6 6阶无向简单图都以阶无向简单图都以(5)(5)中序列为度中序列为度数列。数列。27课件精选完全图完全图完全图完全
28、图定义定义14.614.6 设设G G为为n阶无向简单图，若阶无向简单图，若G G中中每个顶点均与其余的每个顶点均与其余的n-1-1个顶点相邻个顶点相邻，则称，则称G G为为n阶无向完全图阶无向完全图，简称，简称n阶完全图阶完全图，记做，记做K Kn( (n1)1)。 设设D D为为n阶有向简单图，若阶有向简单图，若D D中每个顶点都邻接到其余的中每个顶点都邻接到其余的n-1-1个顶个顶点，又邻接于其余的点，又邻接于其余的n-1-1个顶点，则称个顶点，则称D D是是n阶有向完全图阶有向完全图。设设D D为为n阶有向简单图，若阶有向简单图，若D D的基图为的基图为n阶无向完全图阶无向完全图K K
29、n，则称则称D D是是n阶竞赛图阶竞赛图。30课件精选完全图举例完全图举例完全图举例完全图举例n阶无向完全图的边数为：阶无向完全图的边数为： n( (n-1)/2-1)/2n阶有向完全图的边数为：阶有向完全图的边数为： n( (n-1)-1)n阶竞赛图的边数为：阶竞赛图的边数为：n( (n-1)/2-1)/2K5 53 3阶有向完全图阶有向完全图4 4阶竞赛图阶竞赛图31课件精选正则图正则图正则图正则图定义定义14.714.7 设设G G为为n阶无向简单图，若阶无向简单图，若vV(G)V(G)，均有均有d( (v) )k，则称则称G G为为k- -正则图正则图。 举例举例n阶零图是阶零图是0-
30、0-正则图正则图n阶无向完全图是阶无向完全图是( (n-1)-1)-正则图正则图彼得森图是彼得森图是3-3-正则图正则图说明说明n阶阶k- -正则图中，边数正则图中，边数mkn/2/2。当当k为奇数时，为奇数时，n必为偶数。必为偶数。32课件精选子图子图子图子图定义定义14.814.8 设设G ，G 为两个图为两个图( (同为无向图或同为无向图或同为有向图同为有向图) )，若，若V V且且E E，则称则称G G 是是G G的的子图子图，G为为G 的的母图母图，记作，记作G G。若若V V或或E E，则称则称G 为为G的的真子图真子图。若若V V，则称则称G 为为G的的生成子图生成子图。 设设G
31、 为一图，为一图，V1 1 V且且V1 1，称以称以V1 1为顶点集，以为顶点集，以G中中两个端点都在两个端点都在V1 1中的边中的边组成边集组成边集E1 1的图为的图为G的的V1 1导出的子导出的子图图，记作，记作G V1 1 。设设E1 1 E且且E1 1，称以称以E1 1为边集，以为边集，以E1 1中边关联的顶点为顶中边关联的顶点为顶点集点集V1 1的图的图为为G的的E1 1导出的子图导出的子图，记作，记作G E1 1 。33课件精选导出子图举例导出子图举例导出子图举例导出子图举例在上图中，设在上图中，设G G为为(1)(1)中图所表示，中图所表示，取取V V1 1a,b,ca,b,c，
32、则则V V1 1的导出子图的导出子图GVGV1 1 为为(2)(2)中图所示。中图所示。取取E E1 1ee1 1,e,e3 3 ，则则E E1 1的导出子图的导出子图GEGE1 1 为为(3)(3)中图所示。中图所示。34课件精选定义定义定义定义14.914.914.914.9定义定义14.914.9 设设G 为为n阶无向简单图，阶无向简单图，以以V为顶点集为顶点集，以所，以所有有使使G成为完全图成为完全图Kn的添加边组成的集合的添加边组成的集合为边集的图，称为为边集的图，称为G的的补图补图，记作，记作G。若图若图GG，则称为则称为G是是自补图自补图。(1)(1)为自补图为自补图(2)(2)
33、和和(3)(3)互为补图互为补图37课件精选定义定义定义定义14.1014.1014.1014.10定义定义14.1014.10 设设G 为无向图。为无向图。(1)(1)设设eE，用用G- -e表示从表示从G G中去掉边中去掉边e，称为称为删除删除e。设设E E，用用G- -E 表示从表示从G中删除中删除E 中所有的边，称为中所有的边，称为删除删除E 。(2)(2)设设vV，用用G- -v表示从表示从G中去掉中去掉v及所关联的一切边，称为及所关联的一切边，称为删除顶删除顶点点v。设设V V，用用G- -V 表示从表示从G中删除中删除V 中所有顶点，称为中所有顶点，称为删除删除V 。(3)(3)
34、设边设边e( (u, ,v)E，用用G e表示从表示从G中删除中删除e后，将后，将e的两个端点的两个端点u, ,v用一个新的顶点用一个新的顶点w( (或用或用u或或v充当充当w) )代替，使代替，使w关联除关联除e外外u, ,v关联关联的所有边，称为的所有边，称为边边e的收缩的收缩。(4)(4)设设u, ,vV( (u, ,v可能相邻，也可能不相邻可能相邻，也可能不相邻) )，用用G(u, ,v) )( (或或G+(+(u, ,v) ) )表示在表示在u, ,v之间加一条边之间加一条边( (u, ,v) )，称为称为加新边加新边。说明说明在收缩边和加新边过程中可能产生环和平行边。在收缩边和加新
35、边过程中可能产生环和平行边。38课件精选14.2 14.2 14.2 14.2 通路与回路通路与回路通路与回路通路与回路定定义义14.1114.11 设设G为为无无向向标标定定图图，G中中顶顶点点与与边边的的交交替替序序列列vi0ej1vi1ej2vi2ejivil称称为为vi0到到vil的的通通路路，其其中中，vir-1, ,vir为为ejr的的端端点点，r 1 1，2 2，l，vi0，vil分分别别称称为为的的始始点点与与终终点点，中中边边的的条条数称为它的数称为它的长度长度。若若vi0vil，则称通路为，则称通路为回路回路。若若的的所有边各异所有边各异，则称，则称为为简单通路简单通路，又
36、若又若vi0vil，则称，则称为为简单回路简单回路。若若的的所所有有顶顶点点( (除除vi0 0与与vij可可能能相相同同外外) )各各异异，所所有有边边也也各各异异，则则称称为为初级通路初级通路或或路径路径，又若又若vi0 0vil，则称，则称为为初级回路初级回路或或圈圈。将长度为奇数的圈称为将长度为奇数的圈称为奇圈奇圈，长度为偶数的圈称为，长度为偶数的圈称为偶圈偶圈。 40课件精选关于通路与回路的说明关于通路与回路的说明关于通路与回路的说明关于通路与回路的说明q在初级通路与初级回路的定义中，仍将初级回路看成初级通在初级通路与初级回路的定义中，仍将初级回路看成初级通路路( (路径路径) )的
37、特殊情况，只是在应用中初级通路的特殊情况，只是在应用中初级通路( (路径路径) )都是始都是始点与终点不相同的，点与终点不相同的，长为长为1 1的圈只能由环生成的圈只能由环生成，长为长为2 2的圈只的圈只能由平行边生成能由平行边生成，因而在，因而在简单无向图中，圈的长度至少为简单无向图中，圈的长度至少为3 3。q若若中有中有边重复边重复出现，则称出现，则称为为复杂通路复杂通路，又若又若vi0 0v vil，则称则称为为复杂回路复杂回路。 q在有向图中在有向图中，通路、回路及分类的定义与无向图中非常相似，通路、回路及分类的定义与无向图中非常相似，只是只是要注意有向边方向的一致性要注意有向边方向的
38、一致性。 q在以上的定义中，将回路定义成通路的特殊情况，即在以上的定义中，将回路定义成通路的特殊情况，即回路也回路也是通路是通路，又，又初级通路初级通路( (回路回路) )是简单通路是简单通路( (回路回路) )，但反之不真。，但反之不真。41课件精选通路和回路的简单表示法通路和回路的简单表示法通路和回路的简单表示法通路和回路的简单表示法(1)(1)只用边的序列表示通路只用边的序列表示通路( (回路回路) )。定义。定义14.1114.11中的中的可以表示可以表示成成ej1 1 , ,ej2 2 , , , ,ejl。(2)(2)在简单图中也可以只用顶点序列表示通路在简单图中也可以只用顶点序列
39、表示通路( (回路回路) )。定义中。定义中的的也可以表示成也可以表示成vi0 0 , ,vi2 2 , , , ,vil。(3)(3)为了写出非标定图中的通路为了写出非标定图中的通路( (回路回路) )，可以先将非标定图标，可以先将非标定图标成标定图，再写出通路与回路。成标定图，再写出通路与回路。(4)(4)在非简单标定图中，当只用顶点序列表示不出某些通路在非简单标定图中，当只用顶点序列表示不出某些通路( (回回路路) )时，可在顶点序列中加入一些边时，可在顶点序列中加入一些边( (这些边是平行边或环这些边是平行边或环) )，可称这种表示法为，可称这种表示法为混合表示法混合表示法。 42课件
40、精选14.3 14.3 14.3 14.3 图的连通性图的连通性图的连通性图的连通性q无向图的连通性无向图的连通性q无向图中顶点之间的短程线及距离无向图中顶点之间的短程线及距离q无向图的连通程度：点割集、割点、边割集、割边、连通度无向图的连通程度：点割集、割点、边割集、割边、连通度q有向图的连通性及判别方法有向图的连通性及判别方法q扩大路径法与极大路径扩大路径法与极大路径q二部图及其判别方法二部图及其判别方法 47课件精选无向图的连通性无向图的连通性无向图的连通性无向图的连通性定定义义14.1214.12 设设无无向向图图G ，u, ,vV，若若u, ,v之之间间存存在在通通路路，则称则称u,
41、 ,v是是连通的连通的，记作，记作uv。 vV，规定规定vv。 无向图中顶点之间的连通关系无向图中顶点之间的连通关系 （u, ,v）| | u, ,vVV且且u与与v之间有通路之间有通路 是自反的、对称的、传递的，因而是自反的、对称的、传递的，因而是是V V上的等价关系上的等价关系。48课件精选连通图与连通分支连通图与连通分支连通图与连通分支连通图与连通分支 若无向图若无向图G是平凡图或是平凡图或G中任何两个顶点都是连通的，则称中任何两个顶点都是连通的，则称G为为连通图连通图，否则称，否则称G是是非连通图非连通图或或分离图分离图。说明：说明：完全图完全图Kn( (n1)1)都是连通图都是连通图
42、零图零图Nn( (n2)2)都是分离图。都是分离图。 定义定义14.114.13 3 设无向图设无向图G ，V关于顶点之间的连通关系关于顶点之间的连通关系的的商集商集V/ / V1 1, ,V2 2, , ,Vk ，Vi为等价类，称导出子图为等价类，称导出子图G Vi ( (i1,2,1,2, ,k) )为为G的的连通分支连通分支，连通分支数连通分支数k常记为常记为p( (G) )。 说明说明若若G为连通图，则为连通图，则p( (G) )1 1。若若G为非连通图，则为非连通图，则p( (G)2)2。在所有的在所有的n阶无向图中，阶无向图中，n阶零图是连通分支最多的，阶零图是连通分支最多的，p(
43、 (Nn) )n。 49课件精选无向图中顶点之间的短程线及距离无向图中顶点之间的短程线及距离无向图中顶点之间的短程线及距离无向图中顶点之间的短程线及距离 定义定义14.114.14 4 设设u, ,v为无向图为无向图G G中任意两个顶点，若中任意两个顶点，若uv，称称u, ,v之间之间长度最短的通路长度最短的通路为为u, ,v之间的之间的短程线短程线，短程线的长度称为，短程线的长度称为u, ,v之间之间的的距离距离，记作，记作d( (u, ,v) )。当当u, ,v不连通时，规定不连通时，规定d( (u, ,v) )。 距离有以下性质：距离有以下性质：(1)(1)d( (u, ,v)0)0，u
44、v时，等号成立。时，等号成立。(2)(2)具有对称性，具有对称性，d( (u, ,v) )d( (v, ,u) )。(3)(3)满足三角不等式：满足三角不等式： u, ,v, ,wV( (G) )，则则d( (u, ,v)+)+d( (v, ,w)d( (u, ,w) )说明：说明：在完全图在完全图Kn( (n2)2)中，任何两个顶点之间的距离都是中，任何两个顶点之间的距离都是1 1。在在n阶零图阶零图Nn( (n2)2)中，任何两个顶点之间的距离都为中，任何两个顶点之间的距离都为。50课件精选如何定义连通度如何定义连通度如何定义连通度如何定义连通度q问题问题：如何定量地比较无向图的连通性的强
45、与弱？：如何定量地比较无向图的连通性的强与弱？q点连通度点连通度：为了破坏连通性，至少需要删除多少个顶点？：为了破坏连通性，至少需要删除多少个顶点？q边连通度边连通度：为了破坏连通性，至少需要删除多少条边？：为了破坏连通性，至少需要删除多少条边？q“破坏连通性破坏连通性”是指是指“变得更加不连通变得更加不连通” 。51课件精选无向图的点无向图的点无向图的点无向图的点割割割割集集集集定义定义14.114.15 5 设无向图设无向图G ，若存在若存在V V，且且V ，使得使得p( (G- -V )p( (G) )，而对于任意的而对于任意的V V ，均有均有p( (G- -V ) )p( (G) )
46、，则称则称V 是是G的的点割集点割集。若若V 是单元集，即是单元集，即V v ，则称则称v为为割点割点。 v2 2, ,v4 4,v3 3,v5 5 都是点割集都是点割集v3 3, ,v5 5都是割点都是割点v1 1与与v6 6不在任何割集中。不在任何割集中。 52课件精选无向图的边割集无向图的边割集无向图的边割集无向图的边割集定义定义14.114.16 6设无向图设无向图G ，若存在若存在E E，且且E ，使使得得p( (G- -E )p( (G) )，而对于任意的而对于任意的E E ，均有均有p( (G- -E ) )p( (G) )，则称则称E 是是G的的边割集边割集，或简称为，或简称为
47、割集割集。若若E 是单元集，即是单元集，即E ee，则称则称e为为割边割边或或桥桥。 e6 6,e,e5 5,e2 2, ,e3 3,e1 1, ,e2 2,e3 3, ,e4 4,e1 1, ,e4 4,e1 1, ,e3 3,e2 2, ,e4 4 都是割集，都是割集，e6 6, ,e5 5是桥。是桥。 53课件精选点连通度点连通度点连通度点连通度定义定义14.114.17 7设设G为无向连通图且为非完全图，则称为无向连通图且为非完全图，则称 K( (G) )minmin| |V | | |V 为为G的点割集的点割集 为为G的的点连通度点连通度，简称，简称连通度连通度。说明说明 连通度是为
48、了产生一个不连通图需要删去的点的最少数目。连通度是为了产生一个不连通图需要删去的点的最少数目。规定完全图规定完全图Kn( (n1)1)的点连通度为的点连通度为n-1-1，规定规定非连通图的点连通度为非连通图的点连通度为0 0，若若K( (G)k，则称则称G G是是k- -连通图连通图，k为非负整数。为非负整数。说明说明K( (G) )有时简记为有时简记为K。上例中图的点连通度为上例中图的点连通度为1 1，此图为，此图为1-1-连通图。连通图。K5 5的点连通度的点连通度K4 4，所以所以K5 5是是1-1-连通图，连通图，2-2-连通图，连通图，3-3-连通图，连通图，4-4-连通图。连通图。
49、若若G是是k- -连通图（连通图（k11）则在则在G中删除任何中删除任何k-1-1个顶点后，所得图个顶点后，所得图一定还是连通的。一定还是连通的。 54课件精选边连通度边连通度边连通度边连通度定义定义14.114.18 8 设设G是无向连通图，称是无向连通图，称 (G ) )minmin| |E | | | E 是是G G的边割集的边割集 为为G的的边连通度边连通度。规定非连通图的边连通度为规定非连通图的边连通度为0 0。若若(G)r，则称则称G是是r 边边- -连通图连通图。 说明说明 (G) )也可以简记为也可以简记为。若若G是是 r 边边- -连通图，则在连通图，则在G G中任意删除中任
50、意删除r-1-1条边后，所得图依然是条边后，所得图依然是连通的。连通的。完全图完全图Kn的边连通度为的边连通度为n-1-1，因而因而Kn是是r边边- -连通图，连通图，00rn-1-1。图图14.814.8中图的边连通度中图的边连通度1 1，它只能是它只能是1 1边边- -连通图。连通图。55课件精选例例例例14.614.614.614.6求所示各图的点连通度，边连通度，并指出它们各是几连通图及求所示各图的点连通度，边连通度，并指出它们各是几连通图及几边连通图。最后将它们按点连通程度及边连通程度排序。几边连通图。最后将它们按点连通程度及边连通程度排序。K4 4K3 3K2 2K1 1K=1 =
51、21 =2K2 2K0 0K0 056课件精选例例例例14.614.614.614.6的解答的解答的解答的解答设第设第i个图的点连通度为个图的点连通度为Ki，边连通度为边连通度为i，I I1,2,1,2,8,8。容易看出，容易看出，K1 11 14 4，K2 22 23 3，K3 33 32 2，K4 44 41 1， K5 5=1 =1 5 5=2=2，K6 66 62 2，K7 77 70 0，K8 88 80 0。(1)(1)是是k- -连通图，连通图，k边边- -连通图，连通图，k1,2,3,41,2,3,4。(2)(2)是是k- -连通图，连通图，k边边- -连通图，连通图，k1,2
52、,31,2,3。(3)(3)是是k- -连通图，连通图，k边边- -连通图，连通图，k1,21,2。(4)(4)是是1-1-连通图，连通图，1 1边边- -连通图。连通图。(5)(5)是是1-1-连通图，连通图，k边边- -连通图，连通图，k1,21,2。(6)(6)是是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)(
53、8)。边连通程度为边连通程度为(1)(2)(3)(1)(2)(3)(5)(5)(6)(4)(7)(6)(4)(7)(8)(8)。57课件精选定理定理定理定理14.714.714.714.7定理定理14.714.7 对于任何无向图对于任何无向图G，有有 K( (G)()(G)()(G) )例例14.714.7 ( (1)1)给出一些无向简单图，使得给出一些无向简单图，使得 K。 (2) (2)给出一些无向简单图，使得给出一些无向简单图，使得 K。解答解答 (1) (1) n阶无向完全图阶无向完全图Kn和和n阶零图阶零图Nn都满足要求。都满足要求。(2)(2)在两个在两个Kn( (n4)4)之间放
54、置一个顶点之间放置一个顶点v，使使v与两个与两个Kn中的每一个中的每一个的任意两个不同的顶点相邻，所得简单图满足要求。的任意两个不同的顶点相邻，所得简单图满足要求。因为这样的图中有一个割点，所以点连通度为因为这样的图中有一个割点，所以点连通度为1 1，又因为无桥，而有两条边组成的边割集，所以边连通度为又因为无桥，而有两条边组成的边割集，所以边连通度为2 2，当当n4 4时，时，3 3，当当n55时，时，4 4。58课件精选有向图的连通性有向图的连通性有向图的连通性有向图的连通性定定义义14.14.1919 设设D 为为一一个个有有向向图图。vi, ,vjV，若若从从vi到到vj存存在通路，则称
55、在通路，则称vi可达可达vj，记作记作vivj，规定规定vi总是可达自身的，即总是可达自身的，即vivi。若若vivj且且vjvi，则称则称vi与与vj是是相互可达相互可达的，记作的，记作vi vj。规定规定vivi。 说明说明 与与都是都是V V上的二元关系，并且不难看出上的二元关系，并且不难看出是是V上的等上的等价关系。价关系。 定义定义14.214.20 0 设设D 为有向图，为有向图，vi, ,vjVV，若若vivj，称称vi到到vj长度最短的通路长度最短的通路为为vi到到vj的的短程线短程线，短程线的长度为短程线的长度为vi到到vj的距离，记作的距离，记作d 。说明说明 与无向图中顶
56、点与无向图中顶点vi与与vj之间的距离之间的距离d( (vi, ,vj) )相比，相比，d 除除无对称性外，具有无对称性外，具有d( (vi, ,vj) )所具有的一切性质。所具有的一切性质。 59课件精选连通图连通图连通图连通图定义定义14.214.21 1 设设D 为一个有向图。若为一个有向图。若D的基图是连通图，则称的基图是连通图，则称D是是弱连通图弱连通图，简称为，简称为连通图连通图。若若vi, ,vjV，vivj与与vjvi至少成立其一，则称至少成立其一，则称D是是单向连通图单向连通图。若均有若均有vi vj，则称则称D是是强连通图强连通图。说明说明 强连通图一定是单向连通图，强连通
57、图一定是单向连通图，单向连通图一定是弱连通图。单向连通图一定是弱连通图。 强连通图强连通图单向连通图单向连通图弱连通图弱连通图60课件精选二部图二部图二部图二部图定定义义14.214.22 2 设设G 为为一一个个无无向向图图，若若能能将将V分分成成V1 1和和V2 2( (V1 1V2 2V, ,V1 1V2 2) )，使使得得G中中的的每每条条边边的的两两个个端端点点都都是是一一个个属属于于V1 1，另另一一个个属属于于V2 2，则则称称G为为二二部部图图（或或称称二二分分图图，偶图偶图等），称等），称V1 1和和V2 2为为互补顶点子集互补顶点子集。常将二部图常将二部图G记为记为 。若若
58、G是是简简单单二二部部图图，V1 1中中每每个个顶顶点点均均与与V2 2中中所所有有顶顶点点相相邻邻，则称则称G为为完全二部图完全二部图，记为，记为Kr, ,s，其中其中r| |V1 1| |，s| |V2 2| |。 说明说明n阶零图为二部图。阶零图为二部图。 66课件精选二部图举例二部图举例二部图举例二部图举例K6的子图的子图K6的子图的子图K3,3K2,3K3,3K2,367课件精选14.4 14.4 14.4 14.4 图的矩阵表示图的矩阵表示图的矩阵表示图的矩阵表示定义定义14.214.23 3 设无向图设无向图G ，V v1 1, ,v2 2, , ,vn ，E e1 1, ,e2
59、 2, , ,em ，令令mij为顶点为顶点vi与边与边ej的关联次数，则称的关联次数，则称( (mij) )nm为为G的的关联矩阵关联矩阵，记作，记作M( (G) )。70课件精选有向图的关联矩阵有向图的关联矩阵有向图的关联矩阵有向图的关联矩阵定义定义14.214.24 4 设有向图设有向图D 中无环，中无环，V v1 1, ,v2 2, , ,vn ，E e1 1, ,e2 2, , ,em ，令令 则称则称( (mij) )nm为为D的的关联矩阵关联矩阵，记作，记作M( (D) )。71课件精选有向图的邻接矩阵有向图的邻接矩阵有向图的邻接矩阵有向图的邻接矩阵定义定义14.214.25 5
60、 设有向图设有向图D ，V v1 1, ,v2 2, , ,vn ，E e1 1, ,e2 2, ,，em ，令令aij(1)(1)为顶点为顶点vi邻接到顶点邻接到顶点vj边的条数，称边的条数，称( (aij(1)(1) )nn为为D D的的邻接矩阵邻接矩阵，记作，记作A( (D) )，或简记为或简记为A。72课件精选有向图的可达矩阵有向图的可达矩阵有向图的可达矩阵有向图的可达矩阵定义定义14.214.26 6 设设D 为有向图。为有向图。V v1 1, ,v2 2, , ,vn ，令令 pij1 1 vi 可达可达 vj0 0 否则否则称称( (pij) )nn为为D的的可达矩阵可达矩阵，记
61、作，记作P( (D) )，简记为简记为P。 76课件精选基本要求基本要求基本要求基本要求q理解与图的定义有关的诸多概念，以及它们之间的相互关系。理解与图的定义有关的诸多概念，以及它们之间的相互关系。q深刻理解握手定理及其推论的内容，并能熟练地应用它们。深刻理解握手定理及其推论的内容，并能熟练地应用它们。q深刻理解图同构、简单图、完全图、正则图、子图、补图、二深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图等概念及其它们的性质和相互关系，并能熟练地应用这些部图等概念及其它们的性质和相互关系，并能熟练地应用这些性质和关系。性质和关系。q深刻理解通路与回路的定义、相互关系及其分类，掌握通路与深刻理解通路与回路的定义、相互关系及其分类，掌握通路与回路的各种不同的表示方法。回路的各种不同的表示方法。q理解无向图的点连通度、边连通度等概念及其之间的关系，并理解无向图的点连通度、边连通度等概念及其之间的关系，并能熟练地求出给定的较为简单的图的点连通度与边连通度。能熟练地求出给定的较为简单的图的点连通度与边连通度。q理解有向图连通性的概念及其分类，掌握判断有向连通图类型理解有向图连通性的概念及其分类，掌握判断有向连通图类型的方法。的方法。80课件精选作业作业作业作业习题十四习题十四3(b)3(b)、8 8、212181课件精选
