第七章 第一讲 无向图及有向图精选文档.ppt

《第七章 第一讲 无向图及有向图精选文档.ppt》由会员分享，可在线阅读，更多相关《第七章 第一讲 无向图及有向图精选文档.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章第七章 第一讲第一讲 无向无向图及有向图图及有向图本讲稿第一页，共三十四页本讲稿第二页，共三十四页第一讲第一讲 无向图及有向图无向图及有向图知识结构知识结构q图的定义图的定义q图的一些概念和规定图的一些概念和规定q简单图和多重图简单图和多重图q顶点的度数与握手定理顶点的度数与握手定理q图的同构图的同构q子图与补图子图与补图本讲稿第三页，共三十四页 引例引例1 1：哥尼斯堡七桥哥尼斯堡七桥问题问题问题问题（图论应用的开始）（图论应用的开始）（图论应用的开始）（图论应用的开始）qq问：能否从某地出发，通过每桥恰好一次，走遍了七桥问：能否从某地出发，通过每桥恰好一次，走遍了七桥问：能否从某地出

2、发，通过每桥恰好一次，走遍了七桥问：能否从某地出发，通过每桥恰好一次，走遍了七桥 后又返回到原处？后又返回到原处？后又返回到原处？后又返回到原处？qq瑞士数学家瑞士数学家瑞士数学家瑞士数学家欧拉欧拉欧拉欧拉在在在在1736173617361736年发表了一篇论文讨论这个问题，指出这个年发表了一篇论文讨论这个问题，指出这个年发表了一篇论文讨论这个问题，指出这个年发表了一篇论文讨论这个问题，指出这个问题无解。问题无解。问题无解。问题无解。普雷格尔河本讲稿第四页，共三十四页欧拉：传奇的一生欧拉：传奇的一生q年少时，听从父亲的安排，巴塞尔大学，学习神学和希伯来语，年少时，听从父亲的安排，巴塞尔大学，学

3、习神学和希伯来语，结果被约翰结果被约翰伯努利欣赏，伯努利欣赏，1717岁获得硕士学位之后，才开始专岁获得硕士学位之后，才开始专供数学。供数学。q为获得圣彼得堡科学院的医学部的职位空缺，的职位空缺，欧拉在巴塞尔便全力投入生理学的研究，并出席医学报告会。1727年，等他到等他到达俄罗斯时，叶卡捷琳娜一世女皇去世，他进入数学部。达俄罗斯时，叶卡捷琳娜一世女皇去世，他进入数学部。q1733年，欧拉回到瑞士，并结婚，一生共生育13个孩子，5个存活。q为了赢得巴黎奖金而投身于一个天文学问题，那是几个有影响的大数学家搞了几个月时间的，欧拉在三天之后把它解决了。可是过分的劳累使他得了一场病，病中右眼失明了。q

4、欧拉到底出了多少著作，直至1936年人们也没有确切的了解。但据估计，要出版已经搜集到的欧拉著作，将需用大4开本60至80卷。彼得堡学院为了整理他的著作整整花了47年。本讲稿第五页，共三十四页问题问题2(2(哈密顿环球旅行哈密顿环球旅行问题，问题，18571857年年):):十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020个城市，能个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？一次最后回到出发点？哈密顿圈（环球旅行游戏）哈密顿圈（环球旅行游戏）本讲稿第六页，共三十四页问题问题3(3(四色问题四色问

5、题):):对任何一张地图进行着色，两个共同边界的国家对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了染不同的颜色，则只需要四种颜色就够了.问题问题4(4(关键路径问题关键路径问题):):一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体育中心一座体育中心,小至组装一台机床小至组装一台机床,一架电视机一架电视机,都要包括许多工序都要包括许多工序.这些工序相互约束这些工序相互约束,只有在某些工序完成之后只有在某些工序完成之后,一个工一个工序才能开始序才能开始.即它们之间存在完成的先后次序关系即它们之间存在完成的先后次序关系,一一般认为这些关系是预知的般

6、认为这些关系是预知的,而且也能够预计完成每个而且也能够预计完成每个工序所需要的时间工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目时间才能够完成整个工程项目,影响工程进度的要影响工程进度的要害工序是哪几个？害工序是哪几个？本讲稿第七页，共三十四页二、图的概念二、图的概念二、图的概念二、图的概念 q设设A，B为任意的两个集合，为任意的两个集合，a,b|aAbB为为A与与B的的无序积无序积，记作，记作A&B。可将无序积中的无序对可将无序积中的无序对a,b记为记为(a,b)，并且允许并且允许ab。无论无论a,b是否相等，均有

7、是否相等，均有(a,b)(b,a)，故故A&BB&A。q元素可以重复出现的集合称为元素可以重复出现的集合称为多重集合多重集合或者或者多重集多重集。例如例如 多重集合多重集合a,a,b,b,b,c,d,(a,a),(b,b),(b,b).本讲稿第八页，共三十四页定义定义1 一个一个无向图（无向图（undirected graphundirected graph）是一个有序的二元组是一个有序的二元组是一个有序的二元组是一个有序的二元组,记作记作G，其中其中其中其中（1 1）V 称为称为称为称为顶点集顶点集顶点集顶点集，其元素称为，其元素称为，其元素称为，其元素称为顶点顶点或或结点（结点（verti

8、cesvertices,nodesnodes）。（2 2）E称为称为边集边集边集边集，它是，它是无序积无序积无序积无序积V&V V的多重子集，其元素称为的多重子集，其元素称为无向边无向边无向边无向边，简称，简称边（边（边（边（edges）。例例例例1 1(1)(1)给定无向图给定无向图给定无向图给定无向图G，其中其中其中其中 Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5).本讲稿第九页，共三十四页例例1 （2 2）E,定义定义2 一个一个有向图有向图（directed graph）是一个有序的二

9、）是一个有序的二元组元组，记作记作D，其中其中（1）V称为顶点集，其元素称为称为顶点集，其元素称为顶点顶点或或结点结点。（2）E为边集，它是笛卡儿积为边集，它是笛卡儿积VV的多重子集，其元素的多重子集，其元素称为称为有向边有向边，简称，简称边边。本讲稿第十页，共三十四页图的一些概念和规定图的一些概念和规定图的一些概念和规定图的一些概念和规定qqG G表示无向图，但有时用表示无向图，但有时用表示无向图，但有时用表示无向图，但有时用G G泛指图泛指图(无向的或有向的无向的或有向的)。qD D只能表示有向图。只能表示有向图。只能表示有向图。只能表示有向图。qqV V(G)，E(G G)分别表示分别表

10、示分别表示分别表示G G的的的的顶点集顶点集和和和和边集边集。qq若若若若|V(G)|)|n，则称则称则称则称G为为为为n阶图阶图阶图阶图。q若若|V(G G)|)|与与与与|E E(G)|)|均为有限数，则称均为有限数，则称G为为为为有限图有限图有限图有限图。qq若边集若边集若边集若边集E(G)，则称则称则称则称G为为零图零图，此时，又若，此时，又若G为为为为n n阶图，阶图，阶图，阶图，则称则称则称则称G G为为为为n阶零图阶零图阶零图阶零图，记作，记作Nn n，特别地，称特别地，称N N1为为平凡图平凡图(trivial trivial graphgraph)。本讲稿第十一页，共三十四页

11、关联与关联次数、环、孤立点关联与关联次数、环、孤立点 q设设G G 为无向图，为无向图，e ek(v vi i,vj)E，称称称称vi,v vj为为ek的端点的端点的端点的端点，ek k与与v vi或或或或ek k与与与与v vj是彼此相是彼此相是彼此相是彼此相关联关联关联关联的。的。若若vi ivj，则称则称则称则称e ek k与与与与v vi i或或或或e ek k与与与与v vj j的的关联次数为关联次数为1。若若v vi ivj j，则称则称则称则称e ek k与与v vi i的的关联次数为关联次数为2，并称，并称ek为为环环。任意的任意的任意的任意的vlV，若若若若vl lvi且且v

12、l vj，则称则称ek与与与与v vl l的的关联次数为关联次数为关联次数为关联次数为0 0。q设设D D 为有向图，为有向图，ekE E，称称称称vi,v vj j为为ek k的的端点。端点。端点。端点。若若v vivj j，则称则称则称则称e ek k为为D中的中的中的中的环环环环。q无论在无向图中还是在有向图中，无边关联的顶点均称无论在无向图中还是在有向图中，无边关联的顶点均称为为孤立点孤立点(isolated vertices)。本讲稿第十二页，共三十四页相邻与邻接相邻与邻接 q设无向图设无向图G G ，v vi i，vj jV V，e ek，el lE E。若若若若 etE，使得使得

13、使得使得e et t(vi，v vj j)，则称则称则称则称vi i与与与与vj是是是是相邻的相邻的。若若若若e ek与与与与e el l至少有一个公共端点，则称至少有一个公共端点，则称ek与与与与el l是是是是相邻的相邻的。设有向图设有向图D，v vi i，v vj jV V，e ek，elE E。若若若若 e et tE，使得使得使得使得et，则称则称vi i为为e et的的始点始点，v vj j为为为为e et的的的的终点终点终点终点，并称，并称，并称，并称v vi i邻接到邻接到邻接到邻接到vj，vj j邻接于邻接于v vi i。若若ek k的终点为的终点为e el的始点，则称的始点

14、，则称的始点，则称的始点，则称ek与与e el l相邻相邻相邻相邻(adjacent)。vi iv vjekel lvivjeke el本讲稿第十三页，共三十四页简单图与多重图简单图与多重图 定义定义3 在无向图中，关联一对顶点的无向边如果多于在无向图中，关联一对顶点的无向边如果多于1条，则条，则称这些边为称这些边为平行边平行边，平行边的条数称为，平行边的条数称为重数重数。在有向图中，关联一对顶点的有向边如果多于在有向图中，关联一对顶点的有向边如果多于在有向图中，关联一对顶点的有向边如果多于在有向图中，关联一对顶点的有向边如果多于1 1条，并且这些边条，并且这些边条，并且这些边条，并且这些边的

15、始点和终点相同的始点和终点相同的始点和终点相同的始点和终点相同(也就是它们的方向相同也就是它们的方向相同也就是它们的方向相同也就是它们的方向相同)，则称这些边为，则称这些边为，则称这些边为，则称这些边为平平行边行边(parallel edgesparallel edges)。含平行边的图称为。含平行边的图称为多重图多重图多重图多重图(multigraph)。既不含平行边也不含环的图称为既不含平行边也不含环的图称为既不含平行边也不含环的图称为既不含平行边也不含环的图称为简单图简单图简单图简单图(simple graph)。例如：在图例如：在图例如：在图例如：在图 中中中中e e5与与与与e6 6

16、是平行边，是平行边，是平行边，是平行边，不是简单图。不是简单图。不是简单图。不是简单图。本讲稿第十四页，共三十四页顶点的度数顶点的度数(degree)定义定义4 设设G为一无向图，为一无向图，vV，称称v作为边的端作为边的端点次数之和为点次数之和为v的度数的度数，简称为，简称为度度，记做，记做 dG(v)。在不在不发生混淆时，简记为发生混淆时，简记为d(v)。设设D为有向图，为有向图，vV，称称v作为边的始点次数之和为作为边的始点次数之和为v的出度的出度(out-degree)，记，记做做d+D(v)，简记作简记作d+(v)。称称v作为边的终点次数之和为作为边的终点次数之和为v的入度的入度(i

17、n-degree)，记，记做做 d-D(v)，简记作简记作d-(v)。称称d+(v)+d-(v)为为v的的度数度数，记做，记做d(v)。本讲稿第十五页，共三十四页设设设设G G为一个为一个为一个为一个n阶无向图，阶无向图，阶无向图，阶无向图，Vv v1,v v2,v vn，称称d(v1)，d(v2 2)，d d(vn)为为为为G G的的度数列度数列。对于顶点标定的无向图，它的度数列是唯一的。对于顶点标定的无向图，它的度数列是唯一的。对于顶点标定的无向图，它的度数列是唯一的。对于顶点标定的无向图，它的度数列是唯一的。类似地，设类似地，设D 为一个为一个n阶有向图，阶有向图，Vv v1,v2,vn

18、 n，称称d(v1)，d(v2 2)，d(v vn n)为为D D的的的的度数列度数列，另外称，另外称，另外称，另外称d d+(v v1)，d+(v2)，d+(vn)与与d d-(v1 1)，d d-(v2 2)，d d-(vn)分别为分别为D的的的的出度出度出度出度列列列列和和入度列入度列入度列入度列。度数列为度数列为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本讲稿第十六页，共三十四页图的度数的相关概念图的度数的相关概念q在无向图在无向图G中，中，最大度最大

19、度最大度最大度(G G)maxd d(v v)|)|vV(G G)最小度最小度最小度最小度(G)mind d(v)|v vV(G G)q在有向图在有向图D D中，中，最大出度最大出度+(D D)maxd d+(v v)|v vV(D D)最小出度最小出度+(D D)mind+(v)|vV(D D)最大入度最大入度-(D)maxd-(v)|)|vV V(D)最小入度最小入度最小入度最小入度-(D)mind d-(v v)|)|v vV V(D D)q称度数为称度数为称度数为称度数为1 1的顶点为的顶点为的顶点为的顶点为悬挂顶点悬挂顶点悬挂顶点悬挂顶点，与它关联的边称为，与它关联的边称为，与它关联

20、的边称为，与它关联的边称为悬挂边悬挂边悬挂边悬挂边。度为偶数度为偶数(奇数奇数)的顶点称为的顶点称为偶度偶度(奇度奇度)顶点顶点。本讲稿第十七页，共三十四页图的度数举例图的度数举例d d(v v1 1 1 1)4(4(4(4(注意，环提供注意，环提供注意，环提供注意，环提供2 2 2 2度度度度)，4 4 4 4，1 1 1 1，v v4 4 4 4是悬挂顶点，是悬挂顶点，是悬挂顶点，是悬挂顶点，e e7 7 7 7是悬挂边。是悬挂边。是悬挂边。是悬挂边。d+(a)4 4，d-(a)1 1+4 4 +0 0-3 3 -1 1度数列：度数列：度数列：度数列：4、4、2 2、1、3出：出：4、0、

21、2、1 入：入：1、3、1、2边：边：边：边：7 7度数列：度数列：5、3、3、3 边数：边数：7本讲稿第十八页，共三十四页握手定理握手定理(The Handshaking Theorem)定理定理1 设设设设G G 为任意无向图，为任意无向图，为任意无向图，为任意无向图，V v v1,v v2 2,v vn，|E|mm，则则则则说明说明 任何无向图中，各顶点度数之和等于边数的两倍。任何无向图中，各顶点度数之和等于边数的两倍。证明证明G中每条边中每条边中每条边中每条边(包括环包括环包括环包括环)均有两个端点，所以在计算均有两个端点，所以在计算均有两个端点，所以在计算均有两个端点，所以在计算GG

22、中各顶点中各顶点度数之和时，度数之和时，每条边均提供每条边均提供2度，当然，度，当然，m条边，共提条边，共提供供2m度。度。度。度。定理定理2 2 设设D 为任意有向图，为任意有向图，V Vv v1 1,v v2 2,v vn，|E E|mm，则则 本讲稿第十九页，共三十四页推论推论推论推论 任何图任何图(无向或有向无向或有向)中，奇度顶点的个数是偶数。中，奇度顶点的个数是偶数。证明证明设设设设G G 为任意一图，令为任意一图，令V V1v|v vVd d(v)为奇数为奇数V2 v|vVd d(v v)为偶数为偶数则则V1V2V V，V1V V2 2 ，由握手定理可知由握手定理可知 由于由于由

23、于由于2 2 2 2mm和和，所以，所以为偶数为偶数，但因但因但因但因V1中顶点度数为奇数，中顶点度数为奇数，中顶点度数为奇数，中顶点度数为奇数，所以所以所以所以|V1 1|必为偶数。必为偶数。必为偶数。必为偶数。本讲稿第二十页，共三十四页例：例：(3,3,2,1)(3,3,2,1)，(3,2,2,1,1)(3,3,2,2)(3,2,2,1,1)(3,3,2,2)(3,2,2,1,1)(3,3,2,2)(3,2,2,1,1)(3,3,2,2)、(3,2,2,2,1)(3,2,2,2,1)(3,2,2,2,1)(3,2,2,2,1)是否是否可图化？可图化？解：解：(3,3,2,1)(3,3,2,

24、1)，(3,2,2,1,1)(3,2,2,1,1)(3,2,2,1,1)(3,2,2,1,1)不可以图化不可以图化 (3,3,2,2)(3,3,2,2)(3,3,2,2)(3,3,2,2)可以图化可以图化可以图化可以图化 (3,2,2,2,1)(3,2,2,2,1)(3,2,2,2,1)(3,2,2,2,1)可以图化可以图化 若非负整数列可以对应为图的度数列，则称之若非负整数列可以对应为图的度数列，则称之为可图化。为可图化。本讲稿第二十一页，共三十四页定理定理4 设设设设G G为任意为任意为任意为任意n阶无向简单图，则阶无向简单图，则阶无向简单图，则阶无向简单图，则(G)n n-1。证明证明因

25、为因为因为因为G既无平行边也无环，既无平行边也无环，所以所以G G中任何顶点中任何顶点v v至多与其余的至多与其余的至多与其余的至多与其余的n-1个顶点均相邻，个顶点均相邻，于是于是d(v)n n-1-1，由于由于v v的任意性，所以的任意性，所以(G)n-1。例例2 判断下列各非负整数列哪些可图化的？哪些可简单图化的判断下列各非负整数列哪些可图化的？哪些可简单图化的？(1)(5,5,4,4,2,1)不可图化。不可图化。(2)(5,4,3,2,2)可图化，不可简单图化。若它可简单图化，可图化，不可简单图化。若它可简单图化，设所得图为设所得图为设所得图为设所得图为G G，则则(G)max5,4,

26、3,2,2max5,4,3,2,25 5，这与定理矛盾这与定理矛盾 本讲稿第二十二页，共三十四页(3)(3,3,3,1)(3)(3,3,3,1)(3)(3,3,3,1)(3)(3,3,3,1)可图化，不可简单图化。可图化，不可简单图化。假设可以简单图化，设假设可以简单图化，设G 以该序列为度数列以该序列为度数列设设设设Vv v1 1,v2,v3 3,v4且且 d(v v1 1)d d(v v2 2)d(v v3 3)3,d(v v4 4)1 1，由于由于d d(v v4 4)1，因而因而v4只能与只能与v1 1，v v2，v3 3之一相邻，去掉之一相邻，去掉之一相邻，去掉之一相邻，去掉v v4

27、后，与后，与v4 4关联的边也去掉，于是剩余的关联的边也去掉，于是剩余的v1，v2 2，v3 3组成的组成的图的度数应该是图的度数应该是图的度数应该是图的度数应该是2、3 3、3 3，此时因为最大度为，此时因为最大度为，此时因为最大度为，此时因为最大度为3，不满足，不满足，不满足，不满足 n-1=2的要求，因此这三个点构成的图必定有平行边或的要求，因此这三个点构成的图必定有平行边或者环，不是简单图，此时若加入者环，不是简单图，此时若加入者环，不是简单图，此时若加入者环，不是简单图，此时若加入v v4及与及与v v4 4关联的边构成的关联的边构成的图必定也不是简单图。图必定也不是简单图。即有即有

28、(3)中序列也不可简单图化。中序列也不可简单图化。本讲稿第二十三页，共三十四页(5)(4,4,3,3,2,2)(5)(4,4,3,3,2,2)可简单图化。下图中两个可简单图化。下图中两个6阶无向简单图都以阶无向简单图都以阶无向简单图都以阶无向简单图都以(5)(5)中序列为中序列为中序列为中序列为度数列。度数列。度数列。度数列。本讲稿第二十四页，共三十四页定义定义定义定义5 5 设设G1 ，G G2 为两个无向图，为两个无向图，若存在双射函数若存在双射函数f：V V1V2 2，对于对于v vi i,vjV1 1，(v vi,v vj)E1当且当且当且当且仅当仅当仅当仅当(f f(vi),),f(

29、v vj j)E2 2，并且并且(v vi i,vj)与与与与(f(v vi i),),f(vj)的重数相同，的重数相同，则称则称G G1与与G G2 2是同构的是同构的是同构的是同构的(isomorphicisomorphic)，记做，记做G1 G G2 2。说明说明(1)(1)点数、边数和度数列对影响等。点数、边数和度数列对影响等。点数、边数和度数列对影响等。点数、边数和度数列对影响等。(2)在图同构的意义下，图的数学定义与图形表示是在图同构的意义下，图的数学定义与图形表示是一一对应的。一一对应的。方法一：边方法一：边 伸缩伸缩方法二：点方法二：点 挪动挪动ab bcd da abcd本讲

30、稿第二十五页，共三十四页 a abed dc ceadcbe1e e1e2e2 2本讲稿第二十六页，共三十四页完全图完全图(complete graph)定义定义6 设设G为为n阶无向阶无向简单图简单图，若，若G中每个顶点均与中每个顶点均与其其余余的的n-1个顶点相邻，则称个顶点相邻，则称G为为n阶无向完全图阶无向完全图，简，简称称n阶完全图阶完全图，记做，记做Kn(n1)。设设D为为n阶有向简单图，若阶有向简单图，若D中任意两个不同的顶中任意两个不同的顶点之间都存在两条方向相反的边，则称点之间都存在两条方向相反的边，则称D是是n阶有阶有向完全图向完全图。n阶无向完全图的边数为：阶无向完全图的

31、边数为：n(n-1)/2-1)/2n阶有向完全图的边数为：阶有向完全图的边数为：n(n-1)-1)本讲稿第二十七页，共三十四页完全图举例完全图举例K5 53 3阶有向完全图阶有向完全图4 4阶竞赛图阶竞赛图本讲稿第二十八页，共三十四页子图子图(subgraph)定义定义8 设设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，

32、称以称以V1为顶点集，为顶点集，以以G中两个端点都在中两个端点都在V1中的边组成边集中的边组成边集E1的图为的图为G的的V1导出的子图（导出的子图（induced subgraph），记作记作GV1。设设E1 E且且E1，称以称以E1为边集，以为边集，以E1中边关联的顶中边关联的顶点为顶点集点为顶点集V1的图为的图为G的的E1导出的子图（导出的子图（induced subgraph），记作，记作GE1。点全选！点全选！点全选！点全选！点不一定全选！点不一定全选！本讲稿第二十九页，共三十四页例：画出例：画出例：画出例：画出K4 4的所有非同构的生成子图。的所有非同构的生成子图。解解 :K K4

33、4的所有非同构的生成子图如图所示的所有非同构的生成子图如图所示的所有非同构的生成子图如图所示的所有非同构的生成子图如图所示 本讲稿第三十页，共三十四页导出子图举例导出子图举例在上图中，设在上图中，设G G为为为为(1)(1)中图所表示，中图所表示，中图所表示，中图所表示，取取V1a,b,c，则则则则V V1 1的导出子图的导出子图G G V1为为为为(2)(2)中图所示。中图所示。中图所示。中图所示。取取取取E E1 1 e e1 1,e3 3，则则则则E E1 1的导出子图的导出子图G E1 为为(3)中图所示。中图所示。本讲稿第三十一页，共三十四页例例3 画出画出4阶阶3条边的所有非同构的

34、无向简单图。条边的所有非同构的无向简单图。由握手定理可知，所画的无向简单图各顶点度数之和为由握手定理可知，所画的无向简单图各顶点度数之和为由握手定理可知，所画的无向简单图各顶点度数之和为由握手定理可知，所画的无向简单图各顶点度数之和为232323236 6 6 6，最大度小于或等于，最大度小于或等于，最大度小于或等于，最大度小于或等于3 3 3 3。于是所求无向简单图的度。于是所求无向简单图的度。于是所求无向简单图的度。于是所求无向简单图的度数列应满足的条件是，将数列应满足的条件是，将数列应满足的条件是，将数列应满足的条件是，将6 6 6 6分成分成分成分成4 4 4 4个非负整数，每个整数均

35、个非负整数，每个整数均个非负整数，每个整数均个非负整数，每个整数均大于或等于大于或等于大于或等于大于或等于0 0 0 0且小于或等于且小于或等于且小于或等于且小于或等于3 3 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 将每种度数列所有非同构的将每种度数列所有非同构的图都画出来即得所要求的全图都画出

36、来即得所要求的全部非同构的图。部非同构的图。本讲稿第三十二页，共三十四页定义定义9 9 设设G 为为n阶无向简单图，以阶无向简单图，以V为顶点集，以所有使为顶点集，以所有使G成为完全图成为完全图Kn的添加边组成的集合为的添加边组成的集合为边集的图，称为边集的图，称为G的的补图补图(complementary graphcomplementary graph)，记作，记作G。若图若图GG，则称为则称为G是是自补图自补图。(1)(1)为自补图为自补图(2)(2)(2)(2)和和和和(3)(3)(3)(3)互为补图互为补图互为补图互为补图，显然，显然(2)(2)和和(3)(3)不同构不同构，不自补，不自补，不自补，不自补本讲稿第三十三页，共三十四页课后作业题：课后作业题：173173页页 7.17.17.157.15其中选作的是：其中选作的是：7.9 7.9、7.127.12、7.147.14、7.157.15其余的必做！其余的必做！本讲稿第三十四页，共三十四页