离散数学第六章

1、第六章第六章 图论图论(1/2)I.图的基本概念图的基本概念 一无向图与有向图一无向图与有向图 1.无向图的定义：一个无向图是一个有序的二元无向图的定义：一个无向图是一个有序的二元组组,记作记作G，其中，其中（1）非空集）非空集V 称为顶点集，其元素称为顶点称为顶点集，其元素称为顶点或结点或结点.（2）E称为边集，它是无序积称为边集，它是无序积V&V的多重子的多重子集，其元素称为无向边，简称边集，其元素称为无向边，简称边. 2.有向图的定义：一个有向图是一个有序的二元有向图的定义：一个有向图是一个有序的二元组组，记作，记作D，其中，其中 （1）V同无向图同无向图.（2）E为边集，它是笛

2、卡儿积为边集，它是笛卡儿积VV的多重子的多重子集，其元素称为有向边，简称边集，其元素称为有向边，简称边. 3. 例例: (1) 给定无向图给定无向图G=，其中，其中， V=v1,v2,v3,v4,v5E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5). (2) 给定有向图给定有向图D=，其中，其中， V=a,b,c,d，E=,. 画出画出G与与D的图形的图形.解：解： 4.一些概念和规定一些概念和规定(1) n阶图阶图:在图的定义中，用在图的定义中，用G表示无向图，表示无向图，D表示有向图，但有时用表示有向图，但有时用G泛指图泛指

3、图(无向的或无向的或有向的有向的)，可是，可是D只能表示有向图只能表示有向图.另外，为另外，为方便起见，有时用方便起见，有时用V(G)，E(G)分别表示分别表示G的的顶点集和边集，若顶点集和边集，若|V(G)|=n,则称则称G为为n阶图，阶图，对有向图可做类似规定对有向图可做类似规定.(2)有限图有限图 : 若若|V(G)|与与|E(G)|均为有限数，则均为有限数，则称称G为有限图为有限图. (3) n阶零图与平凡图阶零图与平凡图 :在图在图G中，若边集中，若边集E(G)为空集为空集 ,则称则称G为零图，此时，又若为零图，此时，又若G为为n阶阶图，则称图，则称G为为n阶零图，记作阶零图，记作N

4、n，特别地，特别地，称称N1为平凡图为平凡图. （4）空图：在图的定义中规定顶点集）空图：在图的定义中规定顶点集V为非为非空集，但在图的运算中可能产生顶点集为空空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定定点集为空集的图集的运算结果，为此规定定点集为空集的图为空图，并将空图记为为空图，并将空图记为（5）关联与关联次数、环、孤立点）关联与关联次数、环、孤立点 ：设设G=为无向图，为无向图，ek=(vi，vj)E，则，则称称vi，vj为为ek的端点，的端点，ek与与vi或或ek与与vj是彼此相关是彼此相关联的联的.若若vivj，则称，则称ek与与vi或或ek与与vj的关联次数为的关

5、联次数为1，若，若vi=vj，则称，则称ek与与vi的关联次数为的关联次数为2，并称，并称ek为环为环.任意的任意的vlV，若，若vlvi且且vlvj，则称，则称ek与与vl的关联次数为的关联次数为0. 设设D=为有向图，为有向图，ek=E，称，称vi，vj为为ek的端点，若的端点，若vi=vj，则称，则称ek为为D中的环中的环.无论无论在无向图中还是在有向图中，无边关联的顶在无向图中还是在有向图中，无边关联的顶点均称孤立点点均称孤立点. （6） 相邻与邻接相邻与邻接 ： 设无向图设无向图G=，vi，vjV，ek，elE.若若 etE，使得，使得et=（vi，vj），则称），则称vi与与vj是

6、相邻的是相邻的.若若ek与与el至少有一个公共端点，至少有一个公共端点，则称则称ek与与el是相邻的是相邻的. 设有向图设有向图D=，vi，vjV，ek，elE.若若 etE，使得，使得et=，则称，则称vi为为et的始点，的始点，vj为为et的终点，并称的终点，并称vi邻接到邻接到vj，vj邻接于邻接于vi.若若ek的终点为的终点为el的始点，则称的始点，则称ek与与el相邻相邻. 二简单图与多重图二简单图与多重图 1.定义：在无向图中，关联一对顶点的无向边如定义：在无向图中，关联一对顶点的无向边如果多于果多于1条，则称这些边为平行边，平行边的条，则称这些边为平行边，平行边的条数称为重数条数

7、称为重数.在有向图中，关联一对顶点的在有向图中，关联一对顶点的有向边如果多于有向边如果多于1条，并且这些边的始点和终条，并且这些边的始点和终点相同点相同(也就是它们的方向相同也就是它们的方向相同)，则称这些边，则称这些边为平行边为平行边.含平行边的图称为多重图，既不含含平行边的图称为多重图，既不含平行边也不含环的图称为简单图平行边也不含环的图称为简单图2.例：例：(1)中中e5与与e6是平是平行边，在行边，在(2)中，中，e2与与e3是平行边，是平行边，注意，注意，e6与与e7不不是平行边是平行边.(1)，(2)两个图都不是简两个图都不是简单图单图 三顶点的度数与握手定理三顶点的度数与握手定理

8、 1顶点的度数：顶点的度数： 设设G=为一无向图，为一无向图， vV，称，称v作为作为边的端点次数之和为边的端点次数之和为v的度数，简称为度，的度数，简称为度，记做记做 dG(v)，在不发生混淆时，简记为，在不发生混淆时，简记为d(v). 设设D=为有向图，为有向图， vV，称，称v作为边作为边的始点次数之和为的始点次数之和为v的出度，记做的出度，记做 (v),简记简记作作 (v).称称v作为边的终点次数之和为作为边的终点次数之和为v的入度，的入度，记做记做 (v)，简记作，简记作 (v)，称，称 (v)+ (v)为为v的度数，记做的度数，记做d(v). DddDdddd证：证： G中每条边中

9、每条边(包括环包括环)均有两个端点，所均有两个端点，所以在计算以在计算G中各顶点度数之和时，每条边均中各顶点度数之和时，每条边均提供提供2度，当然，度，当然，m条边，共提供条边，共提供2m度度. 2握手定理握手定理 定理定理1 (握手定理握手定理) 设设G=为任意无向为任意无向图，图，V=v1,v2,vn，|E|=m，则，则 =2m 1niid v 定理定理2(握手定理握手定理) 设设D=为任意有向图，为任意有向图，V=v1,v2,vn，|E|=m，则，则 =2m，且且 = =m. 1niid v 1niidv 1niidv握手定理的推论：握手定理的推论： 任何图任何图(无向的或有向的无向的或

10、有向的)中，中，奇度顶点的个数是偶数奇度顶点的个数是偶数. 证：证： 设设G=为任意一图，令为任意一图，令 V1=v|vVd(v)为奇数为奇数 V2=v|vVd(v)为偶数为偶数 则则V1V2=V，V1V2= ，由握手定理可知，由握手定理可知 2m= = + 由于由于2m， 均为偶数，所以均为偶数，所以 为为偶数，但因偶数，但因V1中顶点的度数为奇数，所以中顶点的度数为奇数，所以|V1|必为偶数必为偶数. v Vd v 2v Vd v 1v Vd v 2v Vd v 1v Vd v3.顶点度数有关的概念顶点度数有关的概念（1）无向图）无向图G中的最大度和最小度中的最大度和最小度: 在无向图在无

11、向图G中，令中，令 (G)=maxd(v)|vV(G) (G)=mind(v)|vV(G)称称(G)，(G)分别为分别为G的最大度的最大度 和最小度和最小度. 在不引起混淆的情况下，将在不引起混淆的情况下，将(G)，(G)分分别简记为别简记为和和. (2) 有向图有向图D中的最大度、最大出度、最大入中的最大度、最大出度、最大入度与最小度、最小出度、最小入度度与最小度、最小出度、最小入度: 在有向图在有向图D中，类似无向图，可以定义最大中，类似无向图，可以定义最大度度(D)，最小度，最小度(D)，另外，令，另外，令 + (D)=maxd- -(v)|vV(D) + (D)=min d+ (v)|

12、vV(D) - - (D)=maxd- -(v)|vV(D) - - (D)=mind- -(v)|vV(D)分别称为分别称为D的最大出度，最小出度，的最大出度，最小出度， 最大最大入度，最小入度入度，最小入度. 以上记号可分别简记为以上记号可分别简记为 ，+ ， + ， - - ， - -.(3) 悬挂顶点与悬挂边悬挂顶点与悬挂边;奇度顶点与偶度顶点奇度顶点与偶度顶点: 称度数称度数为为1的顶点为悬挂顶点，与它关联的边称为悬挂边的顶点为悬挂顶点，与它关联的边称为悬挂边.度为偶数度为偶数(奇数奇数)的顶点称为偶度的顶点称为偶度(奇度奇度)顶点顶点.(4)例：例：#15. 幻灯片幻灯片 15 (

13、1)的的d(v1)=4(注意注意, 环提环提供供2度度), = 4, = 1,v4是悬挂顶点，是悬挂顶点，e7是悬挂是悬挂边边.(2)的的d+ +(a)=4d- -(a)=1(环环e1提供出度提供出度1, 提供入提供入度度1), d(a)=4+1=5.=5，=3, + +=4 (在在a点达到点达到), + +=0(在在b点达到点达到), - -=3(在在b点达到点达到)，- -=1(在在a和和c点达到点达到). （5）度数列：）度数列： 设设G=为一个为一个n阶无向图阶无向图,V=v1,v2,vn,称称d(v1),d(v2),d(vn)为为G的度数列，对于顶点的度数列，对于顶点标定的无向图，它

14、的度数列是唯一的标定的无向图，它的度数列是唯一的. 设设D=为一个为一个n阶有向图，阶有向图，V=v1,v2,vn，称，称d(v1),d(v2),d(vn)为为D的度的度数列，另外称数列，另外称d+ (v1), d+ (v2), d+ (vn)与与d- - (v1), d- -(v2), d- -(vn)分别为分别为D的出度列和入度列的出度列和入度列.如：如：#14. 幻灯片幻灯片 14 (1)中，按顶点的标定顺序，中，按顶点的标定顺序，度数列为度数列为4,4,2,1,3.在在(2)中，中，按字母顺序，度数列，出按字母顺序，度数列，出度列，入度列分别为度列，入度列分别为5,3,3,3；4,0,

15、2,1；1,3,1,2. （6）可图化的与可简单图化的非负整数列：）可图化的与可简单图化的非负整数列：1）对于给定的非负整数列）对于给定的非负整数列d=(d1,d2, ,dn),若存若存在以在以V=v1,v2,vn为顶点集的为顶点集的n阶无向图阶无向图G,使使得得d(vi)=di,则称则称d是可图化的是可图化的.特别地特别地,若所得图若所得图是简单图是简单图,则称则称d是可简单图化的是可简单图化的. 2）判别定理）判别定理: 设非负整数列设非负整数列d=(d1,d2,dn)，则则d是可图化的当且仅当是可图化的当且仅当 0(mod 2).3）例）例: (3，3，2，1),(3，2，2，1，1)等

16、是不等是不可图化的可图化的,而而(3，3，2，2),(3，2，2，2，1)等等是可图化的是可图化的. 1niid4）简单图定理：）简单图定理： 设设G为任意为任意n阶无向简单图，阶无向简单图，则则(G)n- -1. 证：证： 因为因为G既无既无平行边平行边也无也无环环，所以，所以G中任中任何顶点何顶点v至多与其余的至多与其余的n- -1个顶点均相邻，于个顶点均相邻，于是是d(v)n- -1，由于，由于v的任意性，所以的任意性，所以(G)n- -1. 5）判断下列各非负整数列哪些是）判断下列各非负整数列哪些是可图化的可图化的？哪？哪些是些是可简单图化的可简单图化的？1) (5,5,4,4,2,1

17、)；2) (5,4,3,2,2)；3) (3,3,3,1)；4) (d1,d2,dn)，d1d2dn1 且且 为偶数为偶数5) (4,4,3,3,2,2).1niid解解 ：易知，除：易知，除(1)中序列不可图化外，其余各序列都可中序列不可图化外，其余各序列都可图化图化.但除了但除了(5)中序列外，其余的都是不可简单图化的中序列外，其余的都是不可简单图化的. (2)中序列有中序列有5个数，若它可简单图化，设所得图为个数，若它可简单图化，设所得图为G，则则(G)=max5,4,3,2,2=5，这与简单图定理矛盾，这与简单图定理矛盾.所以所以(2)中序列不可简单图化中序列不可简单图化.类似可证类似

18、可证(4)中序列不可简单图化中序列不可简单图化.假设假设(3)中序列可以简单图化，设中序列可以简单图化，设G=以以(3)中序列中序列为度数列为度数列.不妨设不妨设V=v1，v2，v3，v4 且且 d(v1)=d(v2)=d(v3)=3,d(v4)=1，由于，由于d(v4)1，因而，因而v4只能只能与与v1，v2，v3之一相邻，于是之一相邻，于是v1，v2，v3不可能都是不可能都是3度度顶点，这是矛盾的，因而顶点，这是矛盾的，因而(3)中序列也不可简单图化中序列也不可简单图化. (5)中序列是可简单图化的，下图中两个中序列是可简单图化的，下图中两个6阶无向简单图阶无向简单图都以都以(5)中序列为

19、度数列中序列为度数列. 四图的同构四图的同构 1.两图同构的定义两图同构的定义 ： 设设G1=，G2=为两个无向图为两个无向图(两个有向图两个有向图)，若存，若存在在双射函数双射函数f：V1V2，对于，对于 vi，vj V1，(vi，vj)E1(E1)当且仅当当且仅当(f(vi)，f(vj)E2(E2)，并且，并且(vi，vj)()与与(f(vi)，f(vj)()的重数相同，则称的重数相同，则称G1与与G2是同构的，记做是同构的，记做G1 G2 .2.例例:(1)为彼得松为彼得松(Petersen)图，图，(2)，(3)均与均与(1)同构同构.(4)，(5)，(6)各图彼此间都不同构各图彼此间

20、都不同构. 五完全图与正则图五完全图与正则图 1 完全图完全图 设设G为为n阶无向阶无向简单图简单图，若，若G中每个中每个顶点均与其余的顶点均与其余的n- -1个顶点相邻，个顶点相邻， 则称则称G为为n阶阶无向完全图，简称无向完全图，简称n阶完全图，记做阶完全图，记做Kn(n1). 设设D为为n阶有向简单图，若阶有向简单图，若D中每个顶点都中每个顶点都邻接到其余的邻接到其余的n- -1个顶点，又邻接于其余的个顶点，又邻接于其余的n- -1个顶点，个顶点， 则称则称D是是n阶有向完全图阶有向完全图. 设设D为为n阶有向简单图，若阶有向简单图，若D的基图为的基图为n阶无阶无向完全图向完全图Kn ，

21、则称，则称D是是n阶竞赛图阶竞赛图. 2.例：例：(1)为为K5，(2)为为3阶有向完全图，阶有向完全图，(3)为为4阶阶竞赛图竞赛图.易知，易知，n阶无向完全图，阶无向完全图，n阶有向完全阶有向完全图，图，n阶竞赛图的边数分别为阶竞赛图的边数分别为 n(n- -1)/2，n(n1)，n(n-1)/2. 3正则图正则图 ： 设设G为为n阶无向简单图，若阶无向简单图，若 vV(G)，均有，均有d(v)=k，则称，则称G为为k-正则图正则图. 4.注：注：n阶零图是阶零图是0-正则图，正则图，n阶无向完全图阶无向完全图是是(n-1)正则图，彼得松图是正则图，彼得松图是3-正则图正则图. 由由握手定

22、理握手定理可知，可知，n阶阶k-正则图中，边数正则图中，边数m=kn/2，因而当，因而当k为奇数时，为奇数时，n必为偶数必为偶数. 六子图与补图六子图与补图 1子图子图 :设设G=, G=为两个为两个图图(同为无向图或同为有向图同为无向图或同为有向图), 若若V V且且E E,则称则称G是是G的的子图子图, G为为G的的母图母图，记作，记作G G. 又若又若V V或或E E, 则称则称G为为G的真子图的真子图.若若V=V, 则称则称G为为G的的生成子图生成子图. 设设G=为一图为一图, V1 V且且V1 , 称以称以V1为顶点集为顶点集, 以以G中两个端点都在中两个端点都在V1中的边组成边中的

23、边组成边集集E1的图为的图为G的的V1导出的子图导出的子图, 记作记作GV1. 又设又设E1 E且且E1 , 称以称以E1为边集为边集, 以以E1中边关联的顶点中边关联的顶点为顶点集为顶点集V1的图为的图为G的的E1导出的子图导出的子图, 记作记作GE1. 2.例：设例：设G为为(1)中图所表示，取中图所表示，取V1=a,b,c，则，则V1的导出子图的导出子图GV1为为(2)中图所示中图所示.取取E1=e1,e3，则，则E1的导出子图的导出子图GE1为为(3)中图所示中图所示. 2补图与自补图补图与自补图 设设G=为为n阶无向简单图，以阶无向简单图，以V为顶点为顶点集，以所有使集，以所有使G成

24、为成为完全图完全图Kn的添加边组成的的添加边组成的集合为边集的图，称为集合为边集的图，称为G的的补图补图，记做，记做 . 若图若图 , 则称则称G是是自补图自补图. GGGII.通路与回路通路与回路一通路与回路的定义一通路与回路的定义 定义定义: 设设G为无向标定图，为无向标定图，G中顶点与边的中顶点与边的交替序列交替序列=v0e1v1e2elvl 称为称为v0 到到vl 的通路，的通路，其中其中vr-1 ，vr 为为er 的端点，的端点，r=1，2，l，v0 ，vl 分别称为分别称为的始点与终点，的始点与终点，中边的中边的条数称为它的长度条数称为它的长度.若若v0=vl ，则称通路为回，则称

25、通路为回路路. 若若的所有边各异，则称的所有边各异，则称为简单通路，为简单通路，又若又若v0=vl ，则称，则称为简单回路为简单回路.若若的所有顶的所有顶点点(除除 v0与与vl 可能相同外可能相同外)各异，所有边也各各异，所有边也各异，则称异，则称为初级通路或路径，此时又若为初级通路或路径，此时又若 v0=vl，则称，则称为初级回路或圈为初级回路或圈.将长度为奇数将长度为奇数的圈称为奇圈，长度为偶数的圈称为偶圈的圈称为奇圈，长度为偶数的圈称为偶圈. 注意，在初级通路与初级回路的定义中，注意，在初级通路与初级回路的定义中，仍将初级回路看成初级通路仍将初级回路看成初级通路(路径路径)的特殊情的特

26、殊情况，只是在应用中初级通路况，只是在应用中初级通路(路径路径)都是始点都是始点与终点不相同的，长为与终点不相同的，长为1的圈只能由环生成，的圈只能由环生成，长为长为2的圈只能由平行边生成，因而在简单的圈只能由平行边生成，因而在简单无向图中，圈的长度至少为无向图中，圈的长度至少为3. 另外，若另外，若中有边重复出现，则称中有边重复出现，则称为复为复杂通路，又若杂通路，又若 v0=vl，则称，则称为复杂回路为复杂回路.二二. n阶图中通路与回路的性质阶图中通路与回路的性质 定理定理1. 在在n阶图阶图G中中, 若从顶点若从顶点vi到到vj（vivj）存）存在通路在通路, 则从则从vi到到vj存在

27、长度小于或等于存在长度小于或等于 （n- -1）的通路）的通路. 证：设证：设=v0e1v1e2elvl（v0=vi,vl=vj）为）为G中一条长度为中一条长度为l的通路的通路, 若若ln- -1, 则则满足要求，满足要求，否则必有否则必有l+1n, 即即上的顶点数大于上的顶点数大于G中的顶中的顶点数点数, 于是必存在于是必存在k,s,0ksl,使得使得vs=vk,即在即在上存在上存在vs到自身的回路到自身的回路Csk,在在上删除上删除Csk上的上的一切边及除一切边及除vs外的一切顶点外的一切顶点, 得得= v0e1v1e2vkes+1 elvl, 仍为仍为vi到到vj的通路的通路, 且且长度

28、至少比长度至少比减少减少1.若若还不满足要求还不满足要求, 则重复则重复上述过程上述过程, 由于由于G是有限图是有限图, 经过有限步后经过有限步后, 必必得到得到vi到到vj长度小于或等于长度小于或等于n- -1的通路的通路. 推论推论 在在n阶图阶图G中，若从顶点中，若从顶点vi到到vj（vivj）存在）存在通路，则通路，则vi到到vj一定存在长度小于或等于一定存在长度小于或等于n- -1的初的初级通路（路径）级通路（路径）. 定理定理2.在一个在一个n阶图阶图G中，若存在中，若存在vi到自身的回路，到自身的回路，则一定存在则一定存在vi到自身长度小于或等于到自身长度小于或等于n的回路的回路

29、. 推论推论. 在一个在一个n阶图阶图G中，若存在中，若存在vi到自身的简单到自身的简单回路，则一定存在回路，则一定存在vi到自身长度小于或等于到自身长度小于或等于n的的初级回路初级回路. III. 图的连通性图的连通性 一、无向图的连通性一、无向图的连通性 1.定义定义: 1）设无向图）设无向图G=, 任意任意u,vV，若，若u,v之之间存在通路，则称间存在通路，则称u,v是连通的，记作是连通的，记作uv. vV，规定，规定vv.2）若无向图）若无向图G是平凡图或是平凡图或G中任何两个顶点中任何两个顶点都是连通的，则称都是连通的，则称G为连通图，否则称为连通图，否则称G是是非连通图或分离图非

30、连通图或分离图. 2.无向图中顶点之间的连通关系无向图中顶点之间的连通关系 =（u,v）|u,vV且且u与与v之间有通路之间有通路是自反的，对称的，传递的，因而是自反的，对称的，传递的，因而是是V上的上的等价关系等价关系.3.连通分支的定义：设无向图连通分支的定义：设无向图G=，V关于关于顶点之间的连通关系顶点之间的连通关系的的商集商集V/=V1,V2,Vk，Vi为为等价类等价类，称，称导出子图导出子图GVi(i=1,2,k)为为G的连通分支，连通分支数的连通分支，连通分支数k常记为常记为p(G).4.例：若例：若G为连通图，则为连通图，则p(G)=1，若，若G为非连通为非连通图，则图，则p(

31、G)2，在所有的，在所有的n阶无向图中，阶无向图中，n阶零阶零图是连通分支最多的，图是连通分支最多的，p(Nn)= n二、无向图中顶点之间的短程线及距离二、无向图中顶点之间的短程线及距离1.定义：设定义：设u,v为无向图为无向图G中任意两个顶点，若中任意两个顶点，若 u v，称，称u,v之间长度最短的通路为之间长度最短的通路为u,v之间之间 的短程线，短程线的长度称为的短程线，短程线的长度称为u,v之间的距离之间的距离 记作记作d(u,v).当当u,v不连通时，规定不连通时，规定d(u,v)=. 2. 性质性质: (1) d(u,v)0，u=v时，等号成立时，等号成立. (2)具有对称性，具有

32、对称性，d(u,v)=d(v,u). (3)满足三角不等式：满足三角不等式： u,v,wV(G)，则，则 d(u,v)+d(v,w)d(u,w) 三三.有向图的连通性有向图的连通性1.定义：设定义：设D=为一个有向图，任意为一个有向图，任意vi,vjV，若从，若从vi到到vj存在通路，则称存在通路，则称vi可达可达vj，记作，记作vivj，规定，规定vi总是可达自身的，即总是可达自身的，即vivi.若若vivj且且vjvi，则称，则称vi与与vj是相互可是相互可达的，记作达的，记作vi vj.规定规定vi vi. 2.距离：设距离：设D=为有向图，为有向图， vi,vjV，若，若vivj，称，

33、称vi到到vj长度最短的通路为长度最短的通路为vi到到vj的短的短程线，短程线的长度为程线，短程线的长度为vi到到vj的距离，记作的距离，记作d. 3.分类：设分类：设D=为一个有向图为一个有向图.若若D的的基图基图是连通图，则称是连通图，则称D是弱连通图，简称为连通图是弱连通图，简称为连通图.若任意若任意 vi,vjV ，vivj与与vjvi至少成立其一，至少成立其一，则称则称D是单向连通图是单向连通图.若均有若均有vi vj，则，则称称D是强连通图是强连通图.4.例：例： （1）为强连通图，（2）为单连通图，（3）是弱连通图.由定义可知，强连通图一定是单向连通图，单向连通图一定是弱连通图.

34、 IV.图的矩阵表示图的矩阵表示一一.无向图与有向图的关联矩阵无向图与有向图的关联矩阵 1.无向图的关联矩阵无向图的关联矩阵: 设无向图设无向图G=，V=v1,v2,vn，E=e1,e2,em，令，令mij为顶为顶点点vi与边与边ej的关联次数，则称的关联次数，则称(mij)nm为为G的的关联矩阵，记作关联矩阵，记作M(G). 2.例：例：M(G)= 3.M（G）的性质：）的性质：1） mij=2(j=1,2,m)即即M(G)每列元素之和均为每列元素之和均为2，这正说明每条边关联两个顶点（环所关联的，这正说明每条边关联两个顶点（环所关联的两个端点重合）两个端点重合）.2） mij =d(vi)

35、，即，即M(G)第第i行元素之和为行元素之和为vi的度的度数，数，i=1,2,n. 3） d(vi)= mij= mij= 2=2m,这个结果正这个结果正是是握手定理握手定理的内容，即各顶点的度数之和等于的内容，即各顶点的度数之和等于边数的边数的2倍倍. 4）第）第j列与第列与第k行相同，当且仅当边行相同，当且仅当边ej与与ek是是平行平行边边. 5） mij=0当且仅当当且仅当vi是是孤立点孤立点. 1mj 1ni 1ni 1ni 1mj 1mj 1ni 1mj 1mj 4.有向图的关联矩阵有向图的关联矩阵:设有向图设有向图D=中无环，中无环，V=v1,v2,vn，E=e1,e2,em,令令

36、 mij= 则称则称(mij)nm为为D的关联矩阵，记作的关联矩阵，记作M(D). 5.例：例：M(D)= 6.M(D)的性质：的性质： (1) mij=0，j=1,2,m，从而，从而 mij =0，这说明这说明M(D)中所有元素之和为中所有元素之和为0. (2)M(D)中，负中，负1的个数等于正的个数等于正1的个数，都的个数，都等于边数等于边数m，这正是有向图握手定理的内容，这正是有向图握手定理的内容. (3)第第i行中，正行中，正1的个数等于的个数等于d+(vi)，负，负1的个的个数等于数等于d- -(vi). (4) 平行边所对应的列相同平行边所对应的列相同. 1ni1mj1ni二二.有

37、向图的邻接矩阵有向图的邻接矩阵1.设有向图设有向图D=，V=v1,v2,vn，E=e1,e2,，em，令，令aij为顶点为顶点vi邻接到顶点邻接到顶点vj边的条数，称边的条数，称(aij)nn为为D的邻接矩阵，记的邻接矩阵，记作作A(D)，或简记为，或简记为A. 2.例：例： A 3.性质：性质：（1）设）设A为有向图为有向图D的邻接矩阵，的邻接矩阵， V=v1,v2,vn为为D的顶点集的顶点集,则则A的的l次幂次幂Al（l1）中元素）中元素aij(l)为为D中中vi到到vj长度为长度为l的通路的通路 数数,其中其中aii(l) 为为vi到自身长度为到自身长度为l的回路数的回路数,而而aij(

38、l) 为为D中长度为中长度为l的通路总数的通路总数,其中其中 aii(l) 为为D中中长度为长度为l的回路总数的回路总数. （2）设）设Bl=A+A2+Al（l1）,则则Bl中元素中元素 bij(l)为为D中长度小于或等于中长度小于或等于l的通路数的通路数, 其中其中 bii(l)为为D中长度小于或等于中长度小于或等于l的回路数的回路数.1nj 1ni1ni 1ni1nj 1 2 0 00 0 1 0( )1 0 0 10 0 1 0A G2341解：解：2341200120012200010001010011001100112100010001010013222564212102221222

39、1443212102221AAA4. 例：例： 求图求图G）的邻接矩阵）的邻接矩阵. 所以，由所以，由v1到到v3长度为长度为1、2、3、4的通路分别有的通路分别有0、2、2、4条，条，G中中共有长度为共有长度为4的通路的通路44条，其中回条，其中回路路11条，长度小于等于条，长度小于等于4的通路共的通路共有有88条，其中回路条，其中回路22条条.三三.有向图的可达矩阵有向图的可达矩阵1.定义：定义： 设设G=V,E是一有向图，是一有向图， V=v1，v2，vn，令，令10ijpvi可达可达vj 否则否则 称（称（p ij ） nn 为为G的可达矩阵，记作的可达矩阵，记作 P （G）.2 例例

40、.记下图可达矩阵为记下图可达矩阵为 P （G），则），则 1 1 1 11 1 1 1( )1 1 1 11 1 1 1P G2341一些特殊图一些特殊图一一.二部图二部图1.定义定义: 设设G=为一个无向图，若能将为一个无向图，若能将V分成分成V1和和V2（V1V2=V,V1V2= ），使得），使得G中的每条边的两个端点都是一个属于中的每条边的两个端点都是一个属于V1，另一个属于另一个属于V2，则称，则称G为二部图（或称二分为二部图（或称二分图，偶图等），称图，偶图等），称V1和和V2为互补顶点子集，为互补顶点子集，常将二部图常将二部图G记为记为.又若又若G是简单是简单二部图，二部图，V1中

41、每个顶点均与中每个顶点均与V2中所有顶点相中所有顶点相邻，则称邻，则称G为完全二部图，记为为完全二部图，记为Kr,s，其中，其中r=|V1|,s=|V2|. 2.例例:在左图所示各图在左图所示各图都是二部图，其中，都是二部图，其中，(1)，(2)，(3)为为K6的的子图，子图，(3)为完全二为完全二部图部图K3,3，常将，常将K3,3画成与其同构的画成与其同构的(5)的形式，的形式，K3,3是经常是经常遇到的图遇到的图.(4)是是K5的的子图，它是完全二子图，它是完全二部图部图K2,3，K2,3常画常画成成(6)的形式的形式. 3.定理定理: 一个无向图一个无向图G=V , E是二部图当且是二

42、部图当且仅当仅当G中无奇数长度的回路中无奇数长度的回路. 二二.欧拉图欧拉图1.定义定义: 通过图（无向图或有向图）中所有边通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路一次行遍所有顶点的回路称为欧拉回路.具具有欧拉回路的图称为欧拉图，具有欧拉通有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图路而无欧拉回路的图称为半欧拉图.2.例例: e1e2e3e4e5为（为（1）中的欧拉回路，所以（）中的欧拉回路，所以（1）图

43、为欧拉图图为欧拉图.e1e2e3e4e5为（为（2）中的一条欧拉通路，）中的一条欧拉通路，但图中不存在欧拉回路，所以（但图中不存在欧拉回路，所以（2）为半欧拉图）为半欧拉图.（3）中既没有欧拉回路，也没有欧拉通路）中既没有欧拉回路，也没有欧拉通路,所以所以（3）不是欧拉图，也不是半欧拉图）不是欧拉图，也不是半欧拉图.e1e2e3e4为为（4）图中的欧拉回路，所以（）图中的欧拉回路，所以（4）图为欧拉图）图为欧拉图.（5），（），（6）图中都既没有欧拉回路，也没有欧）图中都既没有欧拉回路，也没有欧拉通路（为什么？）拉通路（为什么？） 3.判别定理判别定理 :无向图无向图G是欧拉图当且仅当是欧拉图

44、当且仅当G是连通图，且是连通图，且G中没有奇度顶点中没有奇度顶点.无向图无向图G是半欧拉图当且仅当是半欧拉图当且仅当G是连通的，是连通的，且且G中恰有两个奇度顶点中恰有两个奇度顶点. 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D是强连通的且是强连通的且每个顶点的入度都等于出度每个顶点的入度都等于出度. 1) 有向图有向图D是半欧拉图当且仅当是半欧拉图当且仅当D是是单向连通单向连通的，且的，且D中恰有两个奇度顶点，其中一个的中恰有两个奇度顶点，其中一个的入度比出度大入度比出度大1，另一个的出度比入度大，另一个的出度比入度大1，而其余顶点的入度都等于出度而其余顶点的入度都等于出度. 三三.哈密

45、顿图哈密顿图 1.定义定义: 经过图（有向图或无向图）中所有顶经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路点一次且仅一次的通路称为哈密顿通路.经经过图中所有顶点一次且仅一次的回路称为过图中所有顶点一次且仅一次的回路称为哈密顿回路哈密顿回路.具有哈密顿回路的图称为哈密具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图路的图称为半哈密顿图.平凡图平凡图是哈密顿图是哈密顿图. 2.例例: 三个无向图都有哈密顿回路，所以都是哈三个无向图都有哈密顿回路，所以都是哈密顿图密顿图.有向图中，（有向图中，（4）具有哈密顿

46、回路，因）具有哈密顿回路，因而它是哈密顿图而它是哈密顿图.（5）只有哈密顿通路，但无）只有哈密顿通路，但无哈密顿回路，因而它是半哈密顿图，而（哈密顿回路，因而它是半哈密顿图，而（6）中既无哈密顿回路，也没有哈密顿通路，因而中既无哈密顿回路，也没有哈密顿通路，因而不是哈密顿图，也不是半哈密顿图不是哈密顿图，也不是半哈密顿图. 4.例例1:三个图都是三个图都是二部图二部图.它们中的那些是哈它们中的那些是哈密顿图？哪些是半哈密顿图？为什么？密顿图？哪些是半哈密顿图？为什么？ 3.哈密顿图与半哈密顿图的一些必要与充分哈密顿图与半哈密顿图的一些必要与充分条件条件 定理定理1. 设无向图设无向图G=是哈密

47、顿图，对是哈密顿图，对于任意非空于任意非空V1包含于包含于V,均有均有 p(G-V1)|V1| 其中，其中，p(G- -V1)为为G- -V1的的连通分支数连通分支数. 定理定理2.设无向图设无向图G=是半哈密顿图，是半哈密顿图，对于任意非空对于任意非空V1包含于包含于V,均有均有 p(G- -V1)|V1|+1 解：解： 在（在（1）中）中,易知互补顶点子集易知互补顶点子集V1=a,f,V2=b,c,d,e.设此二部图为设此二部图为G1，则，则G1=. p(G1- -V1)=4|V1|=2，G1不是哈密不是哈密顿图，也不是半哈密顿图顿图，也不是半哈密顿图. 设（设（2）中图为）中图为G2，则

48、，则G2=，其中其中V1=a,g,h,i,c，V2=b,e,f,j,k,d，易知，易知，p(G2-V1)=|V2|=6|V1|=5，G2不是哈密顿图，但不是哈密顿图，但G2是半哈密顿图，其实，是半哈密顿图，其实，baegjckhfid为为G2中一中一条哈密顿通路条哈密顿通路. 设（设（3）中图为）中图为G3. G3=，其中，其中V1=a,c,g,h,e，V2=b,d,i,j,f，G3中存在哈密顿中存在哈密顿回路，如回路，如abcdgihjefa，所以，所以G3是哈密顿图是哈密顿图. 例例2:三个图中哪些三个图中哪些是哈密顿图？哪些是哈密顿图？哪些是半哈密顿图？是半哈密顿图？ 在（在（1）中，存

49、在哈密顿回路，所以（）中，存在哈密顿回路，所以（1）为哈密顿图为哈密顿图. 在（在（2）中，取）中，取V1=a,b,c,d,e，从，从图中删除图中删除V1得得7个连通分支，个连通分支，(2)不是哈不是哈密顿图，也不是半哈密顿图密顿图，也不是半哈密顿图. 在（在（3）中，取）中，取V1=b,e,h，从图中，从图中删除删除V1得得4个连通分支，它不是哈密顿个连通分支，它不是哈密顿图图.但（但（3）中存在哈密顿通路，所以）中存在哈密顿通路，所以（3）是半哈密顿图）是半哈密顿图. 四四.平面图平面图 1.定义定义:如果图如果图G能以能以这样的方式画在曲面这样的方式画在曲面S上，即除顶点处外上，即除顶点

50、处外无边相交，则称无边相交，则称G可可嵌入曲面嵌入曲面S.若若G可嵌可嵌入平面，则称入平面，则称G是可是可平面图或平面图平面图或平面图.画出画出的无边相交的图称为的无边相交的图称为G的平面嵌入的平面嵌入.无平面无平面嵌入的图称为非平面嵌入的图称为非平面图图. 2.例例:3.平面图的面与次数平面图的面与次数 1).定义定义: 设设G是平面图是平面图(且已是平面嵌入且已是平面嵌入)，由，由G的边将的边将G所在的平面划分成若干个区域，所在的平面划分成若干个区域，每个区域都称为每个区域都称为G的一个面的一个面.其中面积无限其中面积无限的面称为无限面或外部面，面积有限的面的面称为无限面或外部面，面积有限

51、的面称为有限面或内部面称为有限面或内部面.包围每个面的所有边包围每个面的所有边组成的回路组称为该面的边界，边界的长组成的回路组称为该面的边界，边界的长度称为该面的次数度称为该面的次数. 常记外部面为常记外部面为R0，内部面为，内部面为R1，R2，Rk，面，面R的次数记为的次数记为deg(R). 2).例例:图是某图的平面嵌图是某图的平面嵌入，它有入，它有5个面个面.R1的边界的边界为圈为圈abdc，deg(R1)4.R2的边界也是圈，此圈的边界也是圈，此圈为为efg，deg(R2)3，R3的边界为环的边界为环h,deg(R3)=1R4的边界为圈的边界为圈kjl，deg(R4)3.外部面外部面R

52、0的的边界由一个简单回路边界由一个简单回路abefgdc和一个复杂回路和一个复杂回路kjihil组成，组成，deg(R0)13. 3)定理定理: 平面图平面图G中所有面的次数之和等于边中所有面的次数之和等于边数数m的两倍，即的两倍，即 deg(Ri)=2m,其中其中r为为G的的面数面数. 树树 TreeI.无向树及其性质无向树及其性质 一、无向树的定义一、无向树的定义 连通无回路的无向图称为无向树，或简称树，连通无回路的无向图称为无向树，或简称树，常用常用T表示树表示树.平凡图称为平凡树平凡图称为平凡树.若无向图若无向图G至至少有两个连通分支，每个连通都是树，则称少有两个连通分支，每个连通都是

53、树，则称G为森林为森林. 在无向图中，在无向图中，悬挂顶点悬挂顶点称为树叶，度数大于或称为树叶，度数大于或等于等于2的顶点称为分支点的顶点称为分支点.二、无向树的性质二、无向树的性质 定理定理 设设G=是是n阶阶m条边的无向图，则下条边的无向图，则下面各命题是等价的：面各命题是等价的： （1）G是树是树. （2）G中任意两个顶点之间存在唯一的路径中任意两个顶点之间存在唯一的路径.（3）G中无回路且中无回路且m=n-1.（4）G是连通的且是连通的且m=n-1.（5）G是连通的且是连通的且G中任何边均为中任何边均为桥桥.（6）G中没有回路，但在任何两个不同的顶中没有回路，但在任何两个不同的顶点之间

54、加一条新边，在所得图中得到唯一的点之间加一条新边，在所得图中得到唯一的一个含新边的圈一个含新边的圈.定理定理 设设T是是n阶非平凡的无向树，则阶非平凡的无向树，则T中至少有中至少有两片树叶两片树叶. TII. 生成树生成树 一、生成树的定义及存在定理一、生成树的定义及存在定理 1.定义定义: 设设T是无向图是无向图G的子图并且为树，则的子图并且为树，则称称T为为G的树的树.若若T是是G的树且为生成子图，则的树且为生成子图，则称称T是是G的生成树的生成树.设设T是是G的生成树的生成树.eE(G)，若，若eE(T)，则称，则称e为为T的树枝，否的树枝，否则称则称e为为T的弦的弦.并称并称导出子图导

55、出子图GE(G)-E(T)为为T的余树，记作的余树，记作 . 2.例例:3.定理定理: 无向图无向图G具有生成树，当且仅当具有生成树，当且仅当G是是 连通图连通图.推论推论1：设：设G为为n阶阶m条边的无向连通图，则条边的无向连通图，则 mn-1. 推论推论2 ：设：设G是是n阶阶m条边的无向连通图，条边的无向连通图，T为为G的生成树，则的生成树，则T的余树中的余树中 含有含有m-n+1条边条边（即（即T有有m-n+1条弦）条弦）. TIII.基本回路及基本回路系统基本回路及基本回路系统1.定义定义: 设设T是是n阶阶m条边的无向连通图条边的无向连通图G的一的一棵生成树，设棵生成树，设e1,e

56、2,em-n+ +1为为T的弦，设的弦，设Cr为为T添加添加er产生的产生的G中只含弦中只含弦er，其余边，其余边均为树枝的圈，称均为树枝的圈，称Cr为为G的对应的对应T的弦的弦er的的基本回路或基本圈，基本回路或基本圈，r=1,2,m-n+1.并称并称C1,C2,Cm-n+1为为G对应对应T的基本回路系统的基本回路系统 .2.例例:下图对应生成树的下图对应生成树的弦分别为弦分别为e6,e7,e8,e10,e11.设它们对应的基本回路设它们对应的基本回路分别为分别为C1,C2,C3,C4,C5，从对应的弦开始，按顺从对应的弦开始，按顺时针（也可都按逆时针）时针（也可都按逆时针）的顺序写出它们，

57、分别的顺序写出它们，分别为为 C1= e6e4e5 C2= e7e2e1 C3= e8e9e2e1 C4= e10e3e5e2 C5= e11e3e5e2e9 基本回路系统为基本回路系统为C1,C2,C3,C4,C5. IV.基本割集及基本割集系统基本割集及基本割集系统 1.定义定义: 设设T是是n阶连通图阶连通图G的一棵生成树，的一棵生成树，e1，e2，en-1为为T的树枝，的树枝，Si是是G的只含树枝的只含树枝ei的割集，则称的割集，则称Si为为G的对应生成树的对应生成树T由树枝由树枝ei生成的基本割集，生成的基本割集，i=1，2，n- -1.并称并称S1，S2，Sn-1为为G对应对应T的

58、基本割集系统的基本割集系统. 2.例例:e1, e2, e3, e4, e5, e9为为T的的树枝，设它们对应的基本割树枝，设它们对应的基本割集分别为集分别为S1, S2, S3, S4, S5, S6.以以树枝为集合中的第一个元素树枝为集合中的第一个元素的方式写出它们（当然集合的方式写出它们（当然集合中的元素是不讲顺序的，这中的元素是不讲顺序的，这里为了区分树枝和弦）里为了区分树枝和弦）. S1=e1,e7,e8 S2=e2,e7,e8,e10,e11S3=e3,e10,e11 S4=e4,e6S5=e5,e6,e10,e11 S6=e9,e8,e11基本割集系统为基本割集系统为S1,S2,

59、S3,S4,S5,S6. V.最小生成树最小生成树 1.定义定义: 设无向连通带权图设无向连通带权图G=，T是是G的一棵生成树的一棵生成树.T的各边权之和称为的各边权之和称为T的权，记的权，记作作W(T).G的所有生成树中权最小的生成树称的所有生成树中权最小的生成树称为为G的最小生成树的最小生成树.2.求法求法:求最小生成树已经有许多种算法，这里求最小生成树已经有许多种算法，这里介绍避圈法（介绍避圈法（Kruskal算法）算法）. (1)设设n阶无向连通带权图阶无向连通带权图G=有有m条边条边.不妨设不妨设G中没有环（否则，可以将所有的环中没有环（否则，可以将所有的环先删去），将先删去），将m条边按权从小到大顺序排列，条边按权从小到大顺序排列，设为设为e1,e2,em. 2.求法求法:求最小生成树已经有许多种算法，这里求最小生成树已经有许多种算法，这里介绍避圈法（介绍避圈法（Kruskal算法）算法）. (1)设设n阶无向连通带权图阶无向连通带权图G=有有m条边条边.不妨设不妨设G中没有环（否则，可以将所有的环中没有环（否则，可以将所有的环先删去），将先删去），将m条边按权从小到大顺序排列，条边按权从小到大顺