《第七章 第一讲 无向图及有向图优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第七章 第一讲 无向图及有向图优秀PPT.ppt（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第七章第七章 第一讲第一讲 无无向图及有向图向图及有向图现在学习的是第1页，共34页现在学习的是第2页，共34页第一讲第一讲 无向图及有向图无向图及有向图知识结构知识结构q图的定义图的定义q图的一些概念和规定图的一些概念和规定q简单图和多重图简单图和多重图q顶点的度数与握手定理顶点的度数与握手定理q图的同构图的同构q子图与补图子图与补图现在学习的是第3页，共34页 引例引例1 1：哥尼斯堡七桥哥尼斯堡七桥问题问题问题问题（图论应用的开始）（图论应用的开始）（图论应用的开始）（图论应用的开始）qq问：能否从某地出发，通过每桥恰好一次，走遍了七桥问：能否从某地出发，通过每桥恰好一次，走遍了七桥问：
2、能否从某地出发，通过每桥恰好一次，走遍了七桥问：能否从某地出发，通过每桥恰好一次，走遍了七桥 后又返回到原处？后又返回到原处？后又返回到原处？后又返回到原处？qq瑞士数学家瑞士数学家瑞士数学家瑞士数学家欧拉欧拉欧拉欧拉在在在在1736173617361736年发表了一篇论文讨论这个问题，指出这年发表了一篇论文讨论这个问题，指出这年发表了一篇论文讨论这个问题，指出这年发表了一篇论文讨论这个问题，指出这个问题无解。个问题无解。个问题无解。个问题无解。普雷格尔河现在学习的是第4页，共34页欧拉：传奇的一生欧拉：传奇的一生q年少时，听从父亲的安排，巴塞尔大学，学习神学和希伯来语，年少时，听从父亲的安排
3、，巴塞尔大学，学习神学和希伯来语，结果被约翰结果被约翰伯努利欣赏，伯努利欣赏，1717岁获得硕士学位之后，才开始专岁获得硕士学位之后，才开始专供数学。供数学。q为获得圣彼得堡科学院的医学部的职位空缺，的职位空缺，欧拉在巴塞尔便全力投入生理学的研究，并出席医学报告会。1727年，等他到等他到达俄罗斯时，叶卡捷琳娜一世女皇去世，他进入数学部。达俄罗斯时，叶卡捷琳娜一世女皇去世，他进入数学部。q1733年，欧拉回到瑞士，并结婚，一生共生育13个孩子，5个存活。q为了赢得巴黎奖金而投身于一个天文学问题，那是几个有影响的大数学家搞了几个月时间的，欧拉在三天之后把它解决了。可是过分的劳累使他得了一场病，病
4、中右眼失明了。q欧拉到底出了多少著作，直至1936年人们也没有确切的了解。但据估计，要出版已经搜集到的欧拉著作，将需用大4开本60至80卷。彼得堡学院为了整理他的著作整整花了47年。现在学习的是第5页，共34页问题问题2(2(哈密顿环球旅行哈密顿环球旅行问题，问题，18571857年年):):十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020个城市，能否个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？一次最后回到出发点？哈密顿圈（环球旅行游戏）哈密顿圈（环球旅行游戏）现在学习的是第6页，共34页问题问
5、题3(3(四色问题四色问题):):对任何一张地图进行着色，两个共同边界的国对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了家染不同的颜色，则只需要四种颜色就够了.问题问题4(4(关键路径问题关键路径问题):):一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体育中心一座体育中心,小至组装一台机床小至组装一台机床,一架电视机一架电视机,都要包括许多工序都要包括许多工序.这些工序相互约束这些工序相互约束,只有在某些工序完成之后只有在某些工序完成之后,一一个工序才能开始个工序才能开始.即它们之间存在完成的先后次序即它们之间存在完成的先后次序关系关系,一般
6、认为这些关系是预知的一般认为这些关系是预知的,而且也能够预计而且也能够预计完成每个工序所需要的时间完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目间才能够完成整个工程项目,影响工程进度的要害工影响工程进度的要害工序是哪几个？序是哪几个？现在学习的是第7页，共34页二、图的概念二、图的概念二、图的概念二、图的概念 q设设A，B为任意的两个集合，为任意的两个集合，a,b|aAbB为为A与与B的的无序积无序积，记作，记作A&B。可将无序积中的无序对可将无序积中的无序对a,b记为记为(a,b)，并且允许并且允许ab。
7、无论无论a,b是否相等，均有是否相等，均有(a,b)(b,a)，故故A&BB&A。q元素可以重复出现的集合称为元素可以重复出现的集合称为多重集合多重集合或者或者多重集多重集。例如例如 多重集合多重集合a,a,b,b,b,c,d,(a,a),(b,b),(b,b).现在学习的是第8页，共34页定义定义定义定义1 1 一个一个无向图（无向图（无向图（无向图（undirected graphundirected graph）是一个有序的二元组是一个有序的二元组,记作记作记作记作G，其中其中（1 1）V V称为称为顶点集顶点集，其元素称为，其元素称为顶点顶点顶点顶点或或或或结点（结点（结点（结点（ve
8、rtices,nodes）。（2 2）E E称为称为边集边集，它是，它是无序积无序积V V&V的多重子集，其元素称的多重子集，其元素称为为无向边无向边，简称，简称边（边（edges）。例例例例1 1(1)(1)给定无向图给定无向图给定无向图给定无向图G，其中其中其中其中 V Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5).现在学习的是第9页，共34页例例1（2）E,定义定义2 一个一个有向图有向图（directed graph）是一个有序的二）是一个有序的二元组元组，记作记作D，其中其中（1）V
9、称为顶点集，其元素称为称为顶点集，其元素称为顶点顶点或或结点结点。（2）E为边集，它是笛卡儿积为边集，它是笛卡儿积VV的多重子集，其元素的多重子集，其元素称为称为有向边有向边，简称，简称边边。现在学习的是第10页，共34页图的一些概念和规定图的一些概念和规定图的一些概念和规定图的一些概念和规定qqG G表示无向图，但有时用表示无向图，但有时用G G泛指图泛指图泛指图泛指图(无向的或有向的无向的或有向的无向的或有向的无向的或有向的)。qqD D只能表示有向图。只能表示有向图。只能表示有向图。只能表示有向图。qqV V(G G)，E E(G)分别表示分别表示G G的的顶点集顶点集和和边集边集边集边
10、集。qq若若若若|V V(G)|n n，则称则称则称则称G为为为为n阶图阶图。qq若若若若|V(G G)|与与|E E(G G)|均为有限数，则称均为有限数，则称均为有限数，则称均为有限数，则称G为为为为有限图有限图。q若边集若边集E(G)，则称则称则称则称G为为零图零图零图零图，此时，又若，此时，又若G G为为n n阶图，阶图，则称则称G G为为为为n n阶零图阶零图阶零图阶零图，记作，记作，记作，记作N Nn n，特别地，称特别地，称特别地，称特别地，称N N1为为为为平凡图平凡图(trivial graph)。现在学习的是第11页，共34页关联与关联次数、环、孤立点关联与关联次数、环、孤
11、立点 qq设设设设G 为无向图，为无向图，为无向图，为无向图，e ek(vi i,vj)E，称称vi i,vj j为为e ek k的端点的端点，e ek k与与与与vi或或或或ek k与与v vj j是彼此相是彼此相关联关联的。的。的。的。若若v vi v vj，则称则称则称则称e ek k与与与与vi或或ek与与vj的的的的关联次数为关联次数为关联次数为关联次数为1 1。若若viv vj，则称则称ek与与与与v vi i的的的的关联次数为关联次数为关联次数为关联次数为2 2，并称，并称ek为为为为环环。任意的任意的任意的任意的v vl lV V，若若v vl l vi i且且vl lvj，则
12、称则称则称则称ek与与v vl l的的的的关联次数为关联次数为关联次数为关联次数为0 0。qq设设设设D D 为有向图，为有向图，e ek k E，称称称称vi i,v vj为为为为e ek的的的的端点。端点。端点。端点。若若若若vi iv vj j，则称则称则称则称e ek为为D中的中的中的中的环环。qq无论在无向图中还是在有向图中，无边关联的顶点均称为无论在无向图中还是在有向图中，无边关联的顶点均称为无论在无向图中还是在有向图中，无边关联的顶点均称为无论在无向图中还是在有向图中，无边关联的顶点均称为孤孤立点立点(isolated verticesisolated vertices)。现在学
13、习的是第12页，共34页相邻与邻接相邻与邻接 q设无向图设无向图G ，v vi，vjV，e ek k，el lE。若若若若 e et tE，使得使得使得使得e et t(vi i，v vj j)，则称则称v vi i与与v vj j是是是是相邻的相邻的。若若ek与与与与el l至少有一个公共端点，则称至少有一个公共端点，则称e ek与与与与el l是是相邻的相邻的。设有向图设有向图D D，v vi，v vjV，ek k，e elE E。若若若若 e et tE，使得使得使得使得e et ，则称则称则称则称v vi为为et的的始点始点始点始点，vj j为为为为et t的的终点终点终点终点，并称，
14、并称v vi i邻接到邻接到v vj j，v vj邻接于邻接于vi。若若ek k的终点为的终点为的终点为的终点为el l的始点，则称的始点，则称e ek与与e el l相邻相邻(adjacent)。v vivj je ek ke elv vi ivjekel现在学习的是第13页，共34页简单图与多重图简单图与多重图 定义定义3 在无向图中，关联一对顶点的无向边如果多于在无向图中，关联一对顶点的无向边如果多于在无向图中，关联一对顶点的无向边如果多于在无向图中，关联一对顶点的无向边如果多于1 1条，则称这条，则称这条，则称这条，则称这些边为些边为些边为些边为平行边平行边，平行边的条数称为，平行边的
15、条数称为，平行边的条数称为，平行边的条数称为重数重数重数重数。在有向图中，关联一对顶点的有向边如果多于在有向图中，关联一对顶点的有向边如果多于1条，并且条，并且这些边的始点和终点相同这些边的始点和终点相同(也就是它们的方向相同也就是它们的方向相同)，则，则称这些边为称这些边为平行边平行边平行边平行边(parallel edges)。含平行边的图称为。含平行边的图称为。含平行边的图称为。含平行边的图称为多重图多重图多重图多重图(multigraph)。既不含平行边也不含环的图称为既不含平行边也不含环的图称为简单图简单图简单图简单图(simple graph)。例如：在图例如：在图例如：在图例如：
16、在图中中中中e e5 5与与与与e6是平行边，是平行边，不是简单图。不是简单图。现在学习的是第14页，共34页顶点的度数顶点的度数(degree)定义定义4 设设G为一无向图，为一无向图，vV，称称v作为边的作为边的端点次数之和为端点次数之和为v的度数的度数，简称为，简称为度度，记做，记做 dG(v)。在不发生混淆时，简记为在不发生混淆时，简记为d(v)。设设D为有向图，为有向图，vV，称称v作为边的始点次数之和为作为边的始点次数之和为v的出度的出度(out-degree)，记做记做d+D(v)，简记作简记作d+(v)。称称v作为边的终点次数之和为作为边的终点次数之和为v的入度的入度(in-d
17、egree)，记做，记做 d-D(v)，简记作简记作d-(v)。称称d+(v)+d-(v)为为v的的度数度数，记做，记做d(v)。现在学习的是第15页，共34页设设G G 为一个为一个为一个为一个n n阶无向图，阶无向图，V V v v1,v2,v vn n，称称称称d d(v1)，d d(v2)，d d(v vn)为为G的的的的度数列度数列。对于顶点标定的无向图，它的度数列是唯一的。对于顶点标定的无向图，它的度数列是唯一的。类似地，设类似地，设D D 为一个为一个为一个为一个n阶有向图，阶有向图，阶有向图，阶有向图，V V v v1,v v2 2,v vn n，称称称称d(v v1 1)，d
18、(v v2)，d d(vn n)为为为为D的的的的度数列度数列度数列度数列，另外称，另外称d+(v1 1)，d d+(v2)，d+(v vn)与与与与d-(v v1 1)，d-(v v2)，d-(vn n)分别为分别为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现在学习的是第16页，共34页图的度数的相关概念图的度数的相关概念qq在无向图在无向图在无向图在无向图G G中，中，中，
19、中，最大度最大度最大度最大度(G G)maxd d(v v)|)|vV(G)最小度最小度(G G)mind d(v v)|)|v vV V(G G)q在有向图在有向图D D中，中，最大出度最大出度+(D)maxmaxd+(v v)|v vV(D)最小出度最小出度+(D)minmind d+(v)|)|vV V(D)最大入度最大入度最大入度最大入度-(D)maxd-(v)|)|v vV V(D)最小入度最小入度最小入度最小入度-(D)minmind d-(v v)|)|vV V(D)q称度数为称度数为1的顶点为的顶点为悬挂顶点悬挂顶点悬挂顶点悬挂顶点，与它关联的边称为，与它关联的边称为悬挂边悬挂
20、边悬挂边悬挂边。度为偶数度为偶数(奇数奇数)的顶点称为的顶点称为偶度偶度偶度偶度(奇度奇度奇度奇度)顶点顶点顶点顶点。现在学习的是第17页，共34页图的度数举例图的度数举例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、4 4、2、1 1、3 3出：出：4、
21、0、2、1 入：入：1、3、1、2边：边：边：边：7度数列：度数列：5、3、3、3 边数：边数：7现在学习的是第18页，共34页握手定理握手定理(The Handshaking Theorem)定理定理1 设设G G为任意无向图，为任意无向图，V Vv v1 1,v v2,v vn n，|E E|mm，则则则则说明说明说明说明任何无向图中，各顶点度数之和等于边数的两倍。任何无向图中，各顶点度数之和等于边数的两倍。证明证明G G中每条边中每条边中每条边中每条边(包括环包括环包括环包括环)均有两个端点，所以在计算均有两个端点，所以在计算均有两个端点，所以在计算均有两个端点，所以在计算GG中各顶点中
22、各顶点中各顶点中各顶点度数之和时，度数之和时，度数之和时，度数之和时，每条边均提供每条边均提供每条边均提供每条边均提供2 2度，当然，度，当然，度，当然，度，当然，mm条边，共提供条边，共提供条边，共提供条边，共提供2 2m度。度。度。度。定理定理定理定理2 2 2 2 设设D 为任意有向图，为任意有向图，为任意有向图，为任意有向图，V Vv1 1,v v2 2,v vn n，|E E|mm，则则则则 现在学习的是第19页，共34页推论推论推论推论任何图任何图任何图任何图(无向或有向无向或有向无向或有向无向或有向)中，奇度顶点的个数是偶数。中，奇度顶点的个数是偶数。中，奇度顶点的个数是偶数。中
23、，奇度顶点的个数是偶数。证明证明设设设设G G 为任意一图，令为任意一图，令为任意一图，令为任意一图，令V1 1 v v|vV Vd d(v v)为奇数为奇数V2 v|vV Vd d(v)为偶数为偶数则则则则V V1V2 2V V，V V1 1 V V2 ，由握手定理可知由握手定理可知由握手定理可知由握手定理可知 由于由于2 2mm和和，所以，所以为偶数为偶数，但因但因V V1 1中顶点度数为奇数，中顶点度数为奇数，中顶点度数为奇数，中顶点度数为奇数，所以所以所以所以|V V1 1|必为偶数。必为偶数。必为偶数。必为偶数。现在学习的是第20页，共34页例：例：例：例：(3,3,2,1)(3,3
24、,2,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,1)(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,
25、1)可以图化可以图化可以图化可以图化 若非负整数列可以对应为图的度数列，则称若非负整数列可以对应为图的度数列，则称之为可图化。之为可图化。现在学习的是第21页，共34页定理定理4 设设设设G G为任意为任意为任意为任意n n阶无向简单图，则阶无向简单图，则(G G)n-1-1。证明证明证明证明因为因为G既无平行边也无环，既无平行边也无环，所以所以所以所以G中任何顶点中任何顶点v至多与其余的至多与其余的至多与其余的至多与其余的n n-1个顶点均相邻，个顶点均相邻，于是于是于是于是d(v)n n-1，由于由于由于由于v的任意性，所以的任意性，所以(G G)n n-1。例例例例2 2 判断下列各非负
26、整数列哪些可图化的？哪些可简单图化的判断下列各非负整数列哪些可图化的？哪些可简单图化的？(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)max5,4,3,2,25，这与定理矛盾这与定理矛盾 现在学习的是第22页，共34页(3)(3,3,3,1)(3)(3,3,3,1)(3)(3,3,3,1)(3)(3
27、,3,3,1)可图化，不可简单图化。可图化，不可简单图化。可图化，不可简单图化。可图化，不可简单图化。假设可以简单图化，设假设可以简单图化，设假设可以简单图化，设假设可以简单图化，设G G 以该序列为度数列以该序列为度数列设设V v1,v2 2,v3 3,v4 4 且且 d(v1 1)d(v2 2)d(v3 3)3,3,d d(v v4)1 1，由于由于由于由于d d(v v4)1 1，因而因而v4 4只能与只能与只能与只能与v1，v v2 2，v v3之一相邻，去掉之一相邻，去掉之一相邻，去掉之一相邻，去掉v4 4后，与后，与后，与后，与v4 4关联的边也去掉，于是剩余的关联的边也去掉，于是
28、剩余的v v1 1，v v2，v3 3组成的组成的组成的组成的图的度数应该是图的度数应该是2 2、3、3，此时因为最大度为，此时因为最大度为，此时因为最大度为，此时因为最大度为3，不满足，不满足，不满足，不满足 n n-1=2的要求，因此这三个点构成的图必定有平行边或的要求，因此这三个点构成的图必定有平行边或者环，不是简单图，此时若加入者环，不是简单图，此时若加入v4 4及与及与及与及与v4关联的边构成的关联的边构成的关联的边构成的关联的边构成的图必定也不是简单图。图必定也不是简单图。图必定也不是简单图。图必定也不是简单图。即有即有即有即有(3)(3)中序列也不可简单图化。中序列也不可简单图化
29、。中序列也不可简单图化。中序列也不可简单图化。现在学习的是第23页，共34页(5)(4,4,3,3,2,2)(5)(4,4,3,3,2,2)可简单图化。下图中两个可简单图化。下图中两个6 6阶无向简单图都以阶无向简单图都以(5)中序中序列为度数列。列为度数列。现在学习的是第24页，共34页定义定义定义定义5 5 设设设设G G1，G2为两个无向图，为两个无向图，若存在双射函数若存在双射函数若存在双射函数若存在双射函数f：V V1 1V V2，对于对于对于对于vi,vjV1 1，(v vi i,v vj j)E1 1当且当且仅当仅当(f f(vi i),f(vj j)E E2 2，并且并且并且并
30、且(v vi,vj)与与(f f(vi i),f f(vj)的重数相同，的重数相同，的重数相同，的重数相同，则称则称则称则称G G1 1与与与与G2 2是同构的是同构的是同构的是同构的(isomorphicisomorphic)，记做，记做，记做，记做G1 1 G G2。说明说明(1)(1)点数、边数和度数列对影响等。点数、边数和度数列对影响等。点数、边数和度数列对影响等。点数、边数和度数列对影响等。(2)在图同构的意义下，图的数学定义与图形表示是在图同构的意义下，图的数学定义与图形表示是一一对应的。一一对应的。方法一：边方法一：边 伸缩伸缩方法二：点方法二：点 挪动挪动a abc cda a
31、b bc cd d现在学习的是第25页，共34页 ab bed dc cea adcb be1e e1 1e e2 2e2 2现在学习的是第26页，共34页完全图完全图(complete graph)定义定义6 设设G为为n阶无向阶无向简单图简单图，若，若G中每个顶点均与中每个顶点均与其其余余的的n-1个顶点相邻，则称个顶点相邻，则称G为为n阶无向完全图阶无向完全图，简，简称称n阶完全图阶完全图，记做，记做Kn(n1)。设设D为为n阶有向简单图，若阶有向简单图，若D中任意两个不同的顶点中任意两个不同的顶点之间都存在两条方向相反的边，则称之间都存在两条方向相反的边，则称D是是n阶有向完阶有向完全
32、图全图。n阶无向完全图的边数为：阶无向完全图的边数为：n(n-1)/2-1)/2n阶有向完全图的边数为：阶有向完全图的边数为：n(n-1)-1)现在学习的是第27页，共34页完全图举例完全图举例K5 53 3阶有向完全图阶有向完全图4 4阶竞赛图阶竞赛图现在学习的是第28页，共34页子图子图(subgraph)定义定义8 设设G，G 为两个图为两个图(同为无向图同为无向图或同为有向图或同为有向图)，若，若V V且且E E，则称则称G 是是G的的子图子图，G为为G 的的母图母图，记作，记作G G。若若V V或或E E，则称则称G 为为G的的真子图真子图。若若V V，则称则称G 为为G的的生成子图
33、生成子图。设设G为一图，为一图，V1 V且且V1，称以称以V1为顶点为顶点集，以集，以G中两个端点都在中两个端点都在V1中的边组成边集中的边组成边集E1的图的图为为G的的V1导出的子图（导出的子图（induced subgraph），记作记作GV1。设设E1 E且且E1，称以称以E1为边集，以为边集，以E1中边关联的中边关联的顶点为顶点集顶点为顶点集V1的图为的图为G的的E1导出的子图（导出的子图（induced subgraph），记作，记作GE1。点全选！点全选！点全选！点全选！点不一定全选！点不一定全选！点不一定全选！点不一定全选！现在学习的是第29页，共34页例：画出例：画出例：画出例
34、：画出K4的所有非同构的生成子图。的所有非同构的生成子图。解解解解 :K4的所有非同构的生成子图如图所示的所有非同构的生成子图如图所示 现在学习的是第30页，共34页导出子图举例导出子图举例在上图中，设在上图中，设G G为为(1)中图所表示，中图所表示，取取V1 1 a,b,ca,b,c，则则则则V V1 1的导出子图的导出子图GV V1 1为为(2)中图所示。中图所示。取取E E1 e1,e3，则则则则E E1 1的导出子图的导出子图G E E1 1 为为(3)中图所示。中图所示。现在学习的是第31页，共34页例例例例3 3 画出画出4阶阶3条边的所有非同构的无向简单图。条边的所有非同构的无
35、向简单图。由握手定理可知，所画的无向简单图各顶点度数之和为由握手定理可知，所画的无向简单图各顶点度数之和为23236 6，最大度小于或等于，最大度小于或等于3 3。于是所求无向简单图的。于是所求无向简单图的度数列应满足的条件是，将度数列应满足的条件是，将6 6分成分成4 4个非负整数，每个整个非负整数，每个整数均大于或等于数均大于或等于0 0且小于或等于且小于或等于3 3，并且，并且奇数的个数为偶数奇数的个数为偶数奇数的个数为偶数奇数的个数为偶数。将这样的整数列排出来只有下面三种情况：将这样的整数列排出来只有下面三种情况：将这样的整数列排出来只有下面三种情况：将这样的整数列排出来只有下面三种情
36、况：(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 将每种度数列所有非同构的图都将每种度数列所有非同构的图都将每种度数列所有非同构的图都将每种度数列所有非同构的图都画出来即得所要求的全部非同构画出来即得所要求的全部非同构画出来即得所要求的全部非同构画出来即得所要求的全部非同构的图。的图。的图。的图。现在学习的是第32页，共34页定义定义9 9 设设G 为为n阶无向简单图，以阶无向简单图，以V为顶点集，以所有为顶点集，以所有使使G成为完全图成为完全图Kn的添加边组成的集合为的添加边组成的集合为边集的图，称为边集的图，称为G
37、的的补图补图(complementary graphcomplementary graph)，记作，记作G。若图若图GG，则称为则称为G是是自补图自补图。(1)(1)为自补图为自补图(2)(2)(2)(2)和和和和(3)(3)(3)(3)互为补图互为补图互为补图互为补图，显然，显然，显然，显然(2)(2)(2)(2)和和和和(3)(3)(3)(3)不同构不同构不同构不同构，不自补，不自补，不自补，不自补现在学习的是第33页，共34页课后作业题：课后作业题：173173页页 7.17.17.157.15其中选作的是：其中选作的是：7.9 7.9、7.127.12、7.147.14、7.157.15其余的必做！其余的必做！现在学习的是第34页，共34页