1、第14章 图的基本概念离离 散散 数数 学学中国地质大学本科生课程中国地质大学本科生课程本章内容本章内容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 子图与补图子图与补图无序积与多重集合无序积与多重集合
2、 q 设设A A，B B为任意的两个集合，称为任意的两个集合，称 a,b|aA Ab bBB为为A A与与B B的的无序积无序积，记作，记作A&BA&B。可将无序积中的无序对可将无序积中的无序对 a,b 记为记为(a,b)，并且允许并且允许ab。无论无论a,ba,b是否相等，均有是否相等，均有(a,b)(b,a)，因而因而A&BA&BB&AB&A。q 元素可以重复出现的集合称为元素可以重复出现的集合称为多重集合多重集合或者或者多重集多重集，某元，某元素重复出现的次数称为该元素的素重复出现的次数称为该元素的重复度重复度。例如例如 在多重集合在多重集合 a,a,b,b,b,c,d 中，中，a,b,
3、c,d的重复度分别为的重复度分别为2,3,1,12,3,1,1。定义定义14.114.1 一个一个无向图无向图是一个有序的二元组是一个有序的二元组,E,记作记作G G，其中其中（1 1）V V称为称为顶点集顶点集，其元素称为，其元素称为顶点顶点或或结点结点。（2 2）E E称为称为边集边集，它是，它是无序积无序积V&VV&V的多重子集，其元素称为的多重子集，其元素称为无向无向边边，简称，简称边边。定义定义14.214.2 一个一个有向图有向图是一个有序的二元组是一个有序的二元组 E，记作记作D D，其中其中（1 1）V V称为称为顶点集顶点集，其元素称为，其元素称为顶点顶点或或结点结点。（2
4、2）E E为为边集边集，它是，它是笛卡儿积笛卡儿积V VV V的多重子集，其元素称为的多重子集，其元素称为有向有向边边，简称，简称边边。无向图和有向图无向图和有向图说明说明q 可以用图形表示图，即用小圆圈（或实心点）表示顶可以用图形表示图，即用小圆圈（或实心点）表示顶点，用顶点之间的连线表示无向边，用有方向的连线点，用顶点之间的连线表示无向边，用有方向的连线表示有向边。表示有向边。例例14.114.1例例1414.1.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),(v
5、1 1,v,v2 2),(v),(v2 2,v,v3 3),(v),(v2 2,v,v3 3),(v),(v2 2,v,v5 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的图形。的图形。图的一些概念和规定图的一些概念和规定q G G表示无向图，但有时用表示无向图，但有时用G G泛指图泛指图(无向的或有向的无向的或有向的)。q D D只能表示有向图。只能表示有向图。q V(G)V(G)，E(G)E(G)分别表示分别表示G G的的顶点集顶点
6、集和和边集边集。q 若若|V(G)|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阶零图阶零图，记作，记作N Nn n，特别地，称特别地，称N N1 1为为平凡图平凡图。q 在图的定义中规定顶点集在图的定义中规定顶点集V V为非空集，但在图的运算中可能产为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定生顶点集为空集的运算结果，为
7、此规定顶点集为空集的图顶点集为空集的图为为空图空图，并将空图记为，并将空图记为。标定图与非标定图、基图标定图与非标定图、基图 q 将图的集合定义转化成图形表示之后，常用将图的集合定义转化成图形表示之后，常用e ek k表示表示无向边无向边(v vi i,v vj j)（或或有向边有向边 ），），并称并称顶点或边用字母标定顶点或边用字母标定的图的图为为标定图标定图，否则称为，否则称为非标定图非标定图。q 将有向图各将有向图各有向边均改成无向边后的无向图有向边均改成无向边后的无向图称为原来图称为原来图的的基图基图。q 易知标定图与非标定图是可以相互转化的，任何无向图易知标定图与非标定图是可以相互转
8、化的，任何无向图G G的各边均加上箭头就可以得到以的各边均加上箭头就可以得到以G G为基图的有向图。为基图的有向图。关联与关联次数、环、孤立点关联与关联次数、环、孤立点 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为为环环。任意的任意的vlV V，若若vlvi且且vlvj，则称则称ek与与vl的的关联次数为关联次数为0 0。
9、q 设设D D为有向图，为有向图，ek E E，称称vi,vj为为ek的的端点。端点。若若vivj，则称则称ek为为D D中的中的环环。q 无论在无向图中还是在有向图中，无边关联的顶点均称为无论在无向图中还是在有向图中，无边关联的顶点均称为孤孤立点立点。相邻与邻接相邻与邻接 q 设无向图设无向图G GVE，vi，vjV V，ek，elE E。若若 etE E，使得使得et(vi，vj)，则称则称vi与与vj是是相邻的相邻的。若若ek与与el至少有一个公共端点至少有一个公共端点，则称，则称ek与与el是是相邻的相邻的。q 设有向图设有向图D DVE，vi，vjV V，ek，elE E。若若 et
10、E E，使得使得et ，则称则称vi为为et的的始点始点，vj为为et的的终终点点，并称，并称vi邻接到邻接到vj，vj邻接于邻接于vi。若若ek的终点为的终点为el的始点，则称的始点，则称ek与与el相邻相邻。邻域邻域q 设无向图设无向图G ，vV，称称 u|uV(u,v)Euv 为为v的的邻域邻域，记做，记做NG(v)。称称NG G(v)v 为为v的的闭邻域闭邻域，记做，记做NG(v)(v)。称称 e|eEe与与v相关联相关联 为为v的的关联集关联集，记做，记做IG(v)。q 设有向图设有向图D ，vV，称称 u|uV V E Euv 为为v的的后继元集后继元集，记做，记做+D(v)v)。
11、称称 u|uV V E Euv 为为v的的先驱元集先驱元集，记做，记做-D(v)v)。称称+D D(v)-D D(v)为为v的的邻域邻域，记做，记做ND(v)。称称ND(v)v 为为v的的闭邻域闭邻域，记做，记做ND(v)。举例举例N NG G(v1 1)+D(d)v2 2，v5 5 NG(v1)v1 1，v2 2，v5 5 I IG G(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 简单图与多重图简单图与多重图 定义定义14.314.3 在无向图中，关联一对顶点的无向边如果在无向图中，关联一对顶点的无向边如果多于多于1
12、 1条条，则称这些边为则称这些边为平行边平行边，平行边的条数称为，平行边的条数称为重数重数。在有向图中，关联一对顶点的有向边如果在有向图中，关联一对顶点的有向边如果多于多于1 1条条，并且这些，并且这些边的边的始点和终点相同始点和终点相同(也就是它们的方向相同也就是它们的方向相同)，则称这些边，则称这些边为为平行边平行边。含平行边的图称为含平行边的图称为多重图多重图。既不含平行边也不含环的图既不含平行边也不含环的图称为称为简单图简单图。例如：例如：在图在图14.114.1中，中，(a)a)中中e e5 5与与e e6 6是平行边，是平行边，(b)b)中中e e2 2与与e e3 3是平行边，但
13、是平行边，但e e6 6与与e e7 7不是平行边。不是平行边。(a)a)和和(b)b)两个图都不是简单图。两个图都不是简单图。顶点的度数顶点的度数定义定义14.414.4 设设G G为一无向图，为一无向图，vV V，称称v作为边的端点作为边的端点次数之和为次数之和为v的度数的度数，简称为，简称为度度，记做，记做 dG(v)。在不发生混淆时，简记为在不发生混淆时，简记为d(v)。设设D DVE为有向图，为有向图，vV V，称称v作为边的始点次数之和为作为边的始点次数之和为v的出度的出度，记做，记做dD-(v)，简记作简记作d-(v)。称称v作为边的终点次数之和为作为边的终点次数之和为v的入度的
14、入度，记做，记做d+D(v)，简记作简记作d+(v)。称称d-(v)+)+d+(v)为为v v的的度数度数，记做，记做d(v)。图的度数的相关概念图的度数的相关概念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)最小
15、出度最小出度-(D)(D)minmind-(v)|)|vV(D)V(D)q 称度数为称度数为1 1的顶点为的顶点为悬挂顶点悬挂顶点，与它关联的边称为，与它关联的边称为悬挂边悬挂边。度为偶数度为偶数(奇数奇数)的顶点称为的顶点称为偶度偶度(奇度奇度)顶点顶点。图的度数举例图的度数举例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)，d(a)4+14+15 5。5 5，3 3，-4(4(在在a点达到点达到)-0(0
16、(在在b点达到点达到)+3(3(在在b点达到点达到)+1(1(在在a和和c点达到点达到)握手定理握手定理定理定理14.114.1 设设G G为任意无向图，为任意无向图，V V v1 1,v2 2,vn，|E|E|m，则则n n12)(iimvd说明说明任何无向图中，各顶点度数之和等于边数的两倍。任何无向图中，各顶点度数之和等于边数的两倍。证明证明G G中每条边中每条边(包括环包括环)均有两个端点，均有两个端点，所以在计算所以在计算G G中各顶点度数之和时，中各顶点度数之和时，每条边均提供每条边均提供2 2度，当然，度，当然，m条边，共提供条边，共提供2 2m度。度。定理定理14.2 14.2
17、设设D D为任意有向图，为任意有向图，V V v1 1,v2 2,vn，|E|E|m，则则 n nn nn n111)()(,2)(iiiiiimvdvdmvd且握手定理的推论握手定理的推论推论推论任何图任何图(无向的或有向的无向的或有向的)中，奇度顶点的个数是偶数。中，奇度顶点的个数是偶数。证明证明设设G GVE为任意一图，令为任意一图，令V V1 1 v|vV Vd(v)为奇数为奇数 V V2 2 v|vV Vd(v)为偶数为偶数 则则V V1 1V V2 2V V，V V1 1V V2 2 ，由握手定理可知由握手定理可知 Vvvdm)(221)()(VvVvvdvd由于由于2 2m和和2
18、)(Vvvd，所以，所以1)(Vvvd为偶数为偶数，但因但因V V1 1中顶点度数为奇数，中顶点度数为奇数，所以所以|V V1 1|必为偶数。必为偶数。问题研究问题研究问题：问题：在一个部门的在一个部门的2525个人中间，由于意见不同，是否可能每个个人中间，由于意见不同，是否可能每个人恰好与其他人恰好与其他5 5个人意见一致？个人意见一致？解答：解答：不可能不可能。考虑一个图，其中顶点代表人，如果两个人意见。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。度数为奇数的
19、图，这是不可能的。说明：说明：(1)(1)很多离散问题可以用图模型求解。很多离散问题可以用图模型求解。(2)(2)为了建立一个图模型，需要决定顶点和边分别代表什么。为了建立一个图模型，需要决定顶点和边分别代表什么。(3)(3)在一个图模型中，边经常代表两个顶点之间的关系。在一个图模型中，边经常代表两个顶点之间的关系。度数列度数列设设G G为一个为一个n阶无向图，阶无向图，V V v1 1,v2 2,vn，称称d(v1 1)，d(v2 2)，d(vn n)为为G G的的度数列度数列。对于顶点标定的无向图，它的度数列是唯一的。对于顶点标定的无向图，它的度数列是唯一的。反之，对于给定的非负整数列反之
20、，对于给定的非负整数列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 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的的
21、出度列出度列和和入度列入度列。度数列举例度数列举例按顶点的标定顺序，度数列为按顶点的标定顺序，度数列为4,4,2,1,34,4,2,1,3。按字母顺序，度数列，出度列，入按字母顺序，度数列，出度列，入度列分别为度列分别为5,3,3,35,3,3,34,0,2,14,0,2,11,3,1,21,3,1,2可图化的充要条件可图化的充要条件定理定理14.314.3 设非负整数列设非负整数列d(d1 1，d2 2，dn)，则则d d是可图化的当是可图化的当且仅当且仅当 n n1)2(mod0iid证明证明必要性。必要性。由握手定理显然得证。由握手定理显然得证。充分性。充分性。由已知条件可知，由已知条件
22、可知，d中有偶数个奇数度点。中有偶数个奇数度点。奇数度点两两之间连一边，剩余度用环来实现。奇数度点两两之间连一边，剩余度用环来实现。5331定理定理14.314.3的证明的证明由握手定理可知必然性显然。由握手定理可知必然性显然。下面证明充分性。下面证明充分性。由已知条件可知，由已知条件可知，d d中有中有2 2k(0kn/2)k(0kn/2)个奇数，个奇数，不妨设它们为不妨设它们为d d1 1，d d2 2，d dk k，d dk+1k+1，d dk+2k+2，d d2k2k。可用多种方法做出可用多种方法做出n n阶无向图阶无向图G G，V Vvv1 1,v v2 2,v vn n。比如边集如
23、下产生：在顶点比如边集如下产生：在顶点v vr r与与v vr+kr+k之间连边，之间连边，r r1,2,1,2,k k。若若d di i为偶数，令为偶数，令d d i id di i，若若d di i为奇数，令为奇数，令d d i id di i-1-1，得得d d(d(d 1 1，d d 2 2，d d n n)，则则d d i i均为偶数。均为偶数。再在再在v vi i处做出处做出d d i i/2/2条环条环,i i1,n1,n，将所得各边集合在一起组成将所得各边集合在一起组成E E，则则G G的度数列为的度数列为d d。其实，其实，d di i为偶数时，为偶数时，d(vd(vi i)
24、2d2d i i/2/22d2di i/2/2d di i，当当d di i为奇数时，为奇数时，d(vd(vi i)1+2d1+2d i i/2/21+d1+d i i1+d1+di i-1-1d di i，这就证明了这就证明了d d是可图化的。是可图化的。可图化举例可图化举例由定理由定理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)等是可图化的。等是可图化的。定理定理14.414.4定理定理14.414.4
25、设设G G为任意为任意n阶无向简单图，则阶无向简单图，则(G)G)n-1-1。证明证明因为因为G G既无既无平行边平行边也无也无环环，所以所以G G中任何顶点中任何顶点v至多与其余的至多与其余的n-1-1个顶点均相邻，个顶点均相邻，于是于是d(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)可图
26、化，不可简单图化。可图化，不可简单图化。若它可简单图化，若它可简单图化，设所得图为设所得图为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)可图化，不可简单图化。可图化，不可简单图化。假设该序列可以简单图化，假设该序列可以简单图化，设设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，由
27、于由于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 3不可能都是不可能都是3 3度顶点，这是矛盾的，度顶点，这是矛盾的，因而因而(3)(3)中序列也不可简单图化。中序列也不可简单图化。(4)(4)(d d1 1,d,d2 2,d dn n)，d d1 1dd2 2 ddn n1 1 且且 为偶数。为偶数。n n1iid可图化，不可简单图化。可图化，不可简单图化。例例14.214.2(5)(4,4,3,3,2,2)(5)(4,4,3,3,2,2)可简单图化。下图中两个可简单图化
28、。下图中两个6 6阶无向简单图都以阶无向简单图都以(5)(5)中序列为中序列为度数列。度数列。图的同构图的同构定义定义14.514.5 设设G G1 1V，G G2 2V 为两个无向图，为两个无向图，若存在若存在双射函数双射函数f f：V V1 1V V2 2，对于对于vi,vjV V1 1，(vi,vj)E E1 1当且仅当当且仅当(f(f(vi),f(),f(vj)E E2 2，并且并且(vi,vj)与与(f(f(vi),f(),f(vj)的重数相同，的重数相同，则称则称G G1 1与与G G2 2是同构的是同构的，记做，记做G G1 1G G2 2。说明说明(1)(1)类似地，可以定义两
29、个有向图的同构。类似地，可以定义两个有向图的同构。(2)(2)图的同构关系看成全体图集合上的二元关系。图的同构关系看成全体图集合上的二元关系。(3)(3)图的同构关系是等价关系。图的同构关系是等价关系。(4)(4)在图同构的意义下，图的数学定义与图形表示在图同构的意义下，图的数学定义与图形表示 是一一对应的。是一一对应的。图的同构举例图的同构举例彼得森彼得森(Petersen)图图完全图完全图定义定义14.614.6 设设G G为为n阶无向阶无向简单图简单图，若，若G G中中每个顶点均与其余的每个顶点均与其余的n-1-1个顶点相邻个顶点相邻，则称，则称G G为为n阶无向完全图阶无向完全图，简称
30、，简称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 Kn，则称则称D D是是n阶竞赛图阶竞赛图。完全图举例完全图举例n阶无向完全图的边数为：阶无向完全图的边数为：n(n-1)/2-1)/2n阶有向完全图的边数为：阶有向完全图的边数为：n(n-1)-1)n阶竞赛图的边
31、数为：阶竞赛图的边数为：n(n-1)/2-1)/2K5 53 3阶有向完全图阶有向完全图4 4阶竞赛图阶竞赛图正则图正则图定义定义14.714.7 设设G G为为n阶无向简单图，若阶无向简单图，若vV(G)V(G)，均有均有d(v)k，则称则称G G为为k-正则图正则图。举例举例n阶零图是阶零图是0-0-正则图正则图n阶无向完全图阶无向完全图是是(n-1)-1)-正则图正则图彼得森图是彼得森图是3-3-正则图正则图说明说明n阶阶k-正则图中，边数正则图中，边数mkn/2/2。当当k为奇数时，为奇数时，n必为偶数。必为偶数。子图子图定义定义14.814.8 设设G ，G 为两个图为两个图(同为无
32、向图或同为无向图或同为有向图同为有向图)，若，若V V且且E E，则称则称G G 是是G G的的子图子图，G为为G 的的母图母图，记作，记作G G。若若V V或或E E，则称则称G 为为G的的真子图真子图。若若V V，则称则称G 为为G的的生成子图生成子图。设设G 为一图，为一图，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中边关联的顶点为顶中边关联的顶点
33、为顶点集点集V1 1的图的图为为G的的E1 1导出的子图导出的子图，记作，记作G E1 1。导出子图举例导出子图举例在上图中，设在上图中，设G G为为(1)(1)中图所表示，中图所表示，取取V V1 1aa,b,cb,c，则则V V1 1的导出子图的导出子图GVGV1 1 为为(2)(2)中图所示。中图所示。取取E E1 1ee1 1,e e3 3，则则E E1 1的导出子图的导出子图GEGE1 1 为为(3)(3)中图所示。中图所示。例例14.314.3(1)(1)画出画出4 4阶阶3 3条边的所有非同构的无向条边的所有非同构的无向简单图简单图。由由握手定理握手定理可知，所画的无向简单图各顶
34、点度数之和为可知，所画的无向简单图各顶点度数之和为2 23 36 6，最大度小于或等于，最大度小于或等于3 3。于是所求无向简单图的度数列应满足。于是所求无向简单图的度数列应满足的条件是，将的条件是，将6 6分成分成4 4个非负整数，每个整数均大于或等于个非负整数，每个整数均大于或等于0 0且且小于或等于小于或等于3 3，并且，并且奇数的个数为偶数奇数的个数为偶数。将这样的整数列排出。将这样的整数列排出来只有下面三种情况：来只有下面三种情况：(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 将每种度数列所有非同构的将每种度
35、数列所有非同构的图都画出来即得所要求的全图都画出来即得所要求的全部非同构的图。部非同构的图。对于给定的正整数对于给定的正整数n和和m(mn(n-1)/2)-1)/2)，构造出所有非同构的构造出所有非同构的n阶阶m条边的所有条边的所有非同构的无向非同构的无向(有向有向)简单图，这是目前还简单图，这是目前还没有解决的难题。没有解决的难题。例例14.314.3(2)(2)画出画出3 3阶阶2 2条边的所有非同构的有向简单图。条边的所有非同构的有向简单图。由握手定理可知，所画有向简单图各顶点度数之和为由握手定理可知，所画有向简单图各顶点度数之和为4 4，最，最大出度和最大入度均小于或等于大出度和最大入
36、度均小于或等于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.914.9 设设G 为为n阶无向简单图，阶无向简单图，以以V为顶点集为顶点集，以所，以所有有使使G成为完全图成为完全图Kn的添加边组成的集合的添加边组成的集合为边集的图，称为为边集的图，称为G的的补图
37、补图，记作，记作G。若图若图GG，则称为则称为G是是自补图自补图。(1)(1)为自补图为自补图(2)(2)和和(3)(3)互为补图互为补图定义定义14.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 中所有顶
38、点，称为中所有顶点，称为删除删除V 。(3)(3)设边设边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)，称为称为加新边加新边。说明说明在收缩边和加新边过程中可能产生在收缩边和加新边过程中可能产生环环和和平行边平行边。举例
39、举例GGe5G e1,e4 Gv5G v4,v5 G e514.2 14.2 通路与回路通路与回路定义定义14.1114.11 设设G为无向标定图，为无向标定图，G中顶点与边的交替序列中顶点与边的交替序列vi0ej1vi1ej2vi2ejivil称为称为vi0到到vil的的通路通路，其中，其中，vir-1,vir为为ejr的的端点端点，r 1 1，2 2，l，vi0，vil分别称为分别称为的的始点始点与与终点终点，中边的中边的条数称为它的条数称为它的长度长度。若若vi0vil，则称通路为，则称通路为回路回路。若若的的所有边各异所有边各异，则称，则称为为简单通路简单通路，又若又若vi0vil，则
40、称，则称为为简单回路简单回路。若若的所有的所有顶点顶点(除除vi0 0与与vij可能相同外可能相同外)各异各异，所有，所有边也各异边也各异，则，则称称为为初级通路初级通路或或路径路径，又若又若vi0 0vil，则称，则称为为初级回路初级回路或或圈圈。将长度为奇数的圈称为将长度为奇数的圈称为奇圈奇圈，长度为偶数的圈称为，长度为偶数的圈称为偶圈偶圈。关于通路与回路的说明关于通路与回路的说明q 在初级通路与初级回路的定义中，仍将初级回路看成初级在初级通路与初级回路的定义中，仍将初级回路看成初级通路通路(路径路径)的特殊情况，只是在应用中初级通路的特殊情况，只是在应用中初级通路(路径路径)都都是始点与
41、终点不相同的，是始点与终点不相同的，长为长为1 1的圈只能由环生成的圈只能由环生成，长为长为2 2的圈只能由平行边生成的圈只能由平行边生成，因而在，因而在简单无向图中，圈的长度简单无向图中，圈的长度至少为至少为3 3。q 若若中有中有边重复边重复出现，则称出现，则称为为复杂通路复杂通路，又若又若vi0 0v vil，则称则称为为复杂回路复杂回路。q 在有向图中在有向图中，通路、回路及分类的定义与无向图中非常相，通路、回路及分类的定义与无向图中非常相似，只是似，只是要注意有向边方向的一致性要注意有向边方向的一致性。q 在以上的定义中，将回路定义成通路的特殊情况，即在以上的定义中，将回路定义成通路
42、的特殊情况，即回路回路也是通路也是通路，又，又初级通路初级通路(回路回路)是简单通路是简单通路(回路回路)，但反之，但反之不真。不真。通路和回路的简单表示法通路和回路的简单表示法(1)(1)只用边的序列表示通路只用边的序列表示通路(回路回路)。定义。定义14.1114.11中的中的可以表示可以表示成成ej1 1,ej2 2,ejl。(2)(2)在简单图中也可以只用顶点序列表示通路在简单图中也可以只用顶点序列表示通路(回路回路)。定义中。定义中的的也可以表示成也可以表示成vi0 0,vi2 2,vil。(3)(3)为了写出非标定图中的通路为了写出非标定图中的通路(回路回路)，可以先将非标定图标，
43、可以先将非标定图标成标定图，再写出通路与回路。成标定图，再写出通路与回路。(4)(4)在非简单标定图中，当只用顶点序列表示不出某些通路在非简单标定图中，当只用顶点序列表示不出某些通路(回回路路)时，可在顶点序列中加入一些边时，可在顶点序列中加入一些边(这些边是平行边或环这些边是平行边或环)，可称这种表示法为，可称这种表示法为混合表示法混合表示法。定理定理14.514.5定理定理14.514.5 在在n阶图阶图G中，若从顶点中，若从顶点vi到到vj（vivj）存在通路，则从存在通路，则从vi到到vj存在长度小于或等于存在长度小于或等于n-1-1的通路。的通路。证明证明设设v0 0e1 1v1 1
44、e2 2elvl(v0 0vi,vlvj)为为G中一条长度为中一条长度为l的通路，的通路，若若ln-1-1，则则满足要求，满足要求，否则必有否则必有l+1+1n，即即上的顶点数大于上的顶点数大于G中的顶点数，中的顶点数，于是必存在于是必存在k,s,0,0k sl，使得使得 vsvk,即在即在上存在上存在vs到自身的回路到自身的回路Csk,在在上删除上删除C Csk上的一切边及除上的一切边及除vs外的一切顶点，外的一切顶点，得得 v0 0e1 1v1 1e2 2vkes+1+1 elvl,仍为仍为vi到到vj的通路，的通路，且长度至少比且长度至少比减少减少1 1。若若 还不满足要求，则重复上述过
45、程，由于还不满足要求，则重复上述过程，由于G是有限图，经过有是有限图，经过有限步后，必得到限步后，必得到vi到到vj长度小于或等于长度小于或等于n-1-1的通路。的通路。定理定理14.614.6推论推论 在在n阶图阶图G中，若从顶点中，若从顶点vi到到vj（vivj）存在通路，则存在通路，则vi到到vj一定存在长度小于或等于一定存在长度小于或等于n-1-1的初级通路（路径）。的初级通路（路径）。定理定理14.614.6 在一个在一个n阶图阶图G中，若存在中，若存在vi 到自身的回路，则一定到自身的回路，则一定存在存在vi 到自身长度小于或等于到自身长度小于或等于n的回路。的回路。推论推论 在一
46、个在一个n阶图阶图G中，若存在中，若存在vi 到自身的简单回路，则一定到自身的简单回路，则一定存在存在vi 到自身长度小于或等于到自身长度小于或等于n的初级回路。的初级回路。例例14.414.4例例14.414.4 无向完全图无向完全图Kn(n3)3)中有几种非同构的圈？中有几种非同构的圈？解答解答长度相同的圈都是同构的，长度相同的圈都是同构的，因而只有长度不同的圈才是非同构的，因而只有长度不同的圈才是非同构的，易知易知Kn(n3)3)中含长度为中含长度为3 3，4 4，n的圈，的圈，所以所以Kn(n3)3)中有中有n-2-2种非同构的圈。种非同构的圈。例例14.514.5例例14.514.5
47、 无向完全图无向完全图K3 3的顶点依次标定为的顶点依次标定为a,b,c。在定义意义下在定义意义下K3 3中有多少个不同的圈？中有多少个不同的圈？解答解答在同构意义下，在同构意义下，K3 3中只有一个长度为中只有一个长度为3 3的圈。的圈。但在定义意义下，不同起点但在定义意义下，不同起点(终点终点)的圈是不同的，的圈是不同的，顶点间排列顺序不同的圈也看成是不同的，顶点间排列顺序不同的圈也看成是不同的，因而因而K3 3中有中有6 6个不同的长为个不同的长为3 3的圈：的圈：abca，acba，bacb，bcab，cabc，cbac如果只考虑起点如果只考虑起点(终点终点)的差异，的差异，而不考虑顺
48、时针逆时针的差异，应有而不考虑顺时针逆时针的差异，应有3 3种不同的圈，种不同的圈，当然它们都是同构的，画出图来只有一个。当然它们都是同构的，画出图来只有一个。14.3 14.3 图的连通性图的连通性q 无向图的连通性无向图的连通性q 无向图中顶点之间的短程线及距离无向图中顶点之间的短程线及距离q 无向图的连通程度：点割集、割点、边割集、割边、连通度无向图的连通程度：点割集、割点、边割集、割边、连通度q 有向图的连通性及判别方法有向图的连通性及判别方法q 扩大路径法与极大路径扩大路径法与极大路径q 二部图及其判别方法二部图及其判别方法 无向图的连通性无向图的连通性定义定义14.1214.12
49、设无向图设无向图G ，u,vV，若若u,v之间存在通之间存在通路，则称路，则称u,v是是连通的连通的，记作，记作uv。vV，规定规定vv。无向图中顶点之间的连通关系无向图中顶点之间的连通关系 （u,v）|u,vV V且且u与与v之间有通路之间有通路 是自反的、对称的、传递的，因而是自反的、对称的、传递的，因而是是V V上的等价关系上的等价关系。连通图与连通分支连通图与连通分支 若无向图若无向图G是平凡图或是平凡图或G中任何两个顶点都是连通的，则称中任何两个顶点都是连通的，则称G为为连通图连通图，否则称，否则称G是是非连通图非连通图或或分离图分离图。说明：说明：完全图完全图Kn(n1)1)都是连
50、通图都是连通图零图零图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(Nn)n。无向图中顶点之间的短程线及距离无向图中
