第七章 第一讲 无向图及有向图PPT讲稿.ppt

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

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

2、某地出发，通过每桥恰好一次，走遍了七桥问：能否从某地出发，通过每桥恰好一次，走遍了七桥问：能否从某地出发，通过每桥恰好一次，走遍了七桥 后又返回到原处？后又返回到原处？后又返回到原处？后又返回到原处？qq瑞士数学家瑞士数学家瑞士数学家瑞士数学家欧拉欧拉欧拉欧拉在在在在1736173617361736年发表了一篇论文讨论这个问题，指出这年发表了一篇论文讨论这个问题，指出这年发表了一篇论文讨论这个问题，指出这年发表了一篇论文讨论这个问题，指出这个问题无解。个问题无解。个问题无解。个问题无解。普雷格尔河第4页，共34页，编辑于2022年，星期一欧拉：传奇的一生欧拉：传奇的一生q年少时，听从父亲的安排

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

4、拉在三天之后把它解决了。可是过分的劳累使他得了一场病，病中右眼失明了。q欧拉到底出了多少著作，直至1936年人们也没有确切的了解。但据估计，要出版已经搜集到的欧拉著作，将需用大4开本60至80卷。彼得堡学院为了整理他的著作整整花了47年。第5页，共34页，编辑于2022年，星期一问题问题2(2(哈密顿环球旅行哈密顿环球旅行问题，问题，18571857年年):):十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020个城市，能个城市，能否从某个城市出发在十二面体上依次经过每个城否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？市恰好一次最后回到出发点？哈密顿圈（环

5、球旅行游戏）哈密顿圈（环球旅行游戏）第6页，共34页，编辑于2022年，星期一问题问题3(3(四色问题四色问题):):对任何一张地图进行着色，两个共同边界的国对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了家染不同的颜色，则只需要四种颜色就够了.问题问题4(4(关键路径问题关键路径问题):):一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体育中心一座体育中心,小至组装一台机床小至组装一台机床,一架电视机一架电视机,都要包括许多工序都要包括许多工序.这这些工序相互约束些工序相互约束,只有在某些工序完成之后只有在某些工序完成之后,一个工一个工序才能开

6、始序才能开始.即它们之间存在完成的先后次序关系即它们之间存在完成的先后次序关系,一般认为这些关系是预知的一般认为这些关系是预知的,而且也能够预计完成而且也能够预计完成每个工序所需要的时间每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目才能够完成整个工程项目,影响工程进度的要害工序是影响工程进度的要害工序是哪几个？哪几个？第7页，共34页，编辑于2022年，星期一二、图的概念二、图的概念二、图的概念二、图的概念 q设设A，B为任意的两个集合，为任意的两个集合，a,b|aAbB为为A与与B的的无序积无序积，记作，记

7、作A&B。可将无序积中的无序对可将无序积中的无序对a,b记为记为(a,b)，并且允许并且允许ab。无论无论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页，编辑于2022年，星期一定义定义1 一个一个一个一个无向图（无向图（无向图（无向图（undirected graph）是一个有序的二元组是一个有序的二元组是一个有序的二元组是一个有序的二元组,记作记作G G，其中其中（1

8、 1）V V 称为称为称为称为顶点集顶点集，其元素称为，其元素称为，其元素称为，其元素称为顶点顶点顶点顶点或或或或结点（结点（结点（结点（verticesvertices,nodes）。（2 2）E E称为称为称为称为边集边集边集边集，它是，它是无序积无序积无序积无序积V&V的多重子集，其元素称为的多重子集，其元素称为的多重子集，其元素称为的多重子集，其元素称为无向边无向边无向边无向边，简称，简称，简称，简称边（边（edgesedges）。例例例例1 1(1)(1)给定无向图给定无向图给定无向图给定无向图G G ，其中其中其中其中 V v1,v2,v3,v4,v5，E=(v1,v1),(v1,

9、v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5).第9页，共34页，编辑于2022年，星期一例例例例1 1 （2 2）E,定义定义2 一个一个有向图有向图（directed graph）是一个有序的二）是一个有序的二元组元组，记作记作D，其中其中（1）V称为顶点集，其元素称为称为顶点集，其元素称为顶点顶点或或结点结点。（2）E为边集，它是笛卡儿积为边集，它是笛卡儿积VV的多重子集，其元素的多重子集，其元素称为称为有向边有向边，简称，简称边边。第10页，共34页，编辑于2022年，星期一图的一些概念和规定图的一些概念和规定图的一些概念和规定图的一些概念和规定

10、qqG G表示无向图，但有时用表示无向图，但有时用表示无向图，但有时用表示无向图，但有时用G G泛指图泛指图(无向的或有向的无向的或有向的)。qD只能表示有向图。只能表示有向图。qqV V(G G)，E E(G G)分别表示分别表示分别表示分别表示G G的的的的顶点集顶点集顶点集顶点集和和和和边集边集边集边集。q若若|V V(G G)|n n，则称则称则称则称G G为为n n阶图阶图阶图阶图。qq若若若若|V V(G)|)|与与与与|E E(G G)|均为有限数，则称均为有限数，则称G G为为为为有限图有限图有限图有限图。qq若边集若边集若边集若边集E(G)E(G)，则称则称则称则称G G为为

11、为为零图零图，此时，又若，此时，又若，此时，又若，此时，又若G G为为为为n n阶图，则阶图，则称称G G为为为为n n阶零图阶零图，记作，记作，记作，记作N Nn n，特别地，称特别地，称N N1 1为为为为平凡图平凡图平凡图平凡图(trivial graph)。第11页，共34页，编辑于2022年，星期一关联与关联次数、环、孤立点关联与关联次数、环、孤立点 qq设设设设G 为无向图，为无向图，为无向图，为无向图，e ek k(v vi i,v vj j)E E，称称称称vi i,v vj为为为为ek的端点的端点的端点的端点，e ek k与与与与v vi i或或e ek k与与与与v vj是

12、彼此相是彼此相是彼此相是彼此相关联关联关联关联的。的。的。的。若若v vi i vj，则称则称则称则称e ek k与与v vi或或或或ek k与与与与v vj j的的的的关联次数为关联次数为关联次数为关联次数为1 1。若若若若v vi iv vj j，则称则称则称则称e ek k与与与与v vi i的的的的关联次数为关联次数为关联次数为关联次数为2 2，并称，并称，并称，并称ek k为为为为环环环环。任意的任意的任意的任意的v vl lV V，若若若若v vl l v vi i且且v vl l vj j，则称则称则称则称ek与与与与v vl l的的的的关联次数为关联次数为关联次数为关联次数为0

13、 0。q设设D D 为有向图，为有向图，ek k E E，称称称称v vi i,v vj为为为为ek的的的的端点。端点。端点。端点。若若若若v vi iv vj j，则称则称则称则称e ek k为为为为D中的中的中的中的环环环环。qq无论在无向图中还是在有向图中，无边关联的顶点均称为无论在无向图中还是在有向图中，无边关联的顶点均称为无论在无向图中还是在有向图中，无边关联的顶点均称为无论在无向图中还是在有向图中，无边关联的顶点均称为孤孤孤孤立点立点立点立点(isolated vertices)。第12页，共34页，编辑于2022年，星期一相邻与邻接相邻与邻接 qq设无向图设无向图设无向图设无向图

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

15、j j为为为为et t的的终点终点，并称，并称vi i邻接到邻接到邻接到邻接到v vj j，v vj j邻接于邻接于邻接于邻接于v vi i。若若e ek k的终点为的终点为的终点为的终点为e el l的始点，则称的始点，则称的始点，则称的始点，则称ek与与与与e el l相邻相邻相邻相邻(adjacentadjacent)。viv vj jeke el lv vi iv vj je ek kel l第13页，共34页，编辑于2022年，星期一简单图与多重图简单图与多重图 定义定义定义定义3 3 在无向图中，关联一对顶点的无向边如果多于在无向图中，关联一对顶点的无向边如果多于在无向图中，关联一

16、对顶点的无向边如果多于在无向图中，关联一对顶点的无向边如果多于1 1条，则称这条，则称这条，则称这条，则称这些边为些边为些边为些边为平行边平行边，平行边的条数称为，平行边的条数称为重数重数重数重数。在有向图中，关联一对顶点的有向边如果多于在有向图中，关联一对顶点的有向边如果多于在有向图中，关联一对顶点的有向边如果多于在有向图中，关联一对顶点的有向边如果多于1 1条，并且这条，并且这条，并且这条，并且这些边的始点和终点相同些边的始点和终点相同些边的始点和终点相同些边的始点和终点相同(也就是它们的方向相同也就是它们的方向相同也就是它们的方向相同也就是它们的方向相同)，则称这，则称这，则称这，则称这

17、些边为些边为些边为些边为平行边平行边平行边平行边(parallel edges)。含平行边的图称为。含平行边的图称为。含平行边的图称为。含平行边的图称为多重图多重图多重图多重图(multigraphmultigraph)。既不含平行边也不含环的图称为既不含平行边也不含环的图称为既不含平行边也不含环的图称为既不含平行边也不含环的图称为简单图简单图(simple graph)。例如：在图例如：在图例如：在图例如：在图 中中中中e e5与与与与e6 6是平行边，是平行边，是平行边，是平行边，不是简单图。不是简单图。第14页，共34页，编辑于2022年，星期一顶点的度数顶点的度数(degree)定义定

18、义4 设设G为一无向图，为一无向图，vV，称称v作为边的作为边的端点次数之和为端点次数之和为v的度数的度数，简称为，简称为度度，记做，记做 dG(v)。在不发生混淆时，简记为在不发生混淆时，简记为d(v)。设设D为有向图，为有向图，vV，称称v作为边的始点次数之和为作为边的始点次数之和为v的出度的出度(out-degree)，记做记做d+D(v)，简记作简记作d+(v)。称称v作为边的终点次数之和为作为边的终点次数之和为v的入度的入度(in-degree)，记做，记做 d-D(v)，简记作简记作d-(v)。称称d+(v)+d-(v)为为v的的度数度数，记做，记做d(v)。第15页，共34页，编

19、辑于2022年，星期一设设G G 为一个为一个n n阶无向图，阶无向图，阶无向图，阶无向图，V V v v1 1,v2,v vn n，称称d(v v1 1)，d d(v v2 2)，d d(v vn n)为为为为G G的的的的度数列度数列。对于顶点标定的无向图，它的度数列是唯一的。对于顶点标定的无向图，它的度数列是唯一的。对于顶点标定的无向图，它的度数列是唯一的。对于顶点标定的无向图，它的度数列是唯一的。类似地，设类似地，设类似地，设类似地，设D 为一个为一个n n阶有向图，阶有向图，V V v v1,v2 2,v vn，称称称称d d(v v1)，d d(v v2)，d d(v vn)为为为

20、为D D的的的的度数列度数列，另外称，另外称，另外称，另外称d d+(v v1)，d d+(v2 2)，d+(v vn n)与与d d-(v v1 1)，d-(v v2 2)，d d-(v vn n)分别为分别为分别为分别为D 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页，编辑于2022年，星期一图的度数的相关概念图的度数的相关概念qq在无向图在无向图在无向图在

21、无向图G中，中，中，中，最大度最大度(G G)maxmaxd d(v v)|)|v vV V(G G)最小度最小度最小度最小度(G G)minmind(v)|)|v vV V(G G)qq在有向图在有向图在有向图在有向图D D中，中，中，中，最大出度最大出度最大出度最大出度+(D D)maxmaxd d+(v v)|)|v vV(D D)最小出度最小出度最小出度最小出度+(D D)minmind+(v v)|)|vV V(D D)最大入度最大入度-(D D)maxmaxd-(v v)|)|vV V(D D)最小入度最小入度最小入度最小入度-(D)mind d-(v v)|)|v vV(D D)

22、q称度数为称度数为1的顶点为的顶点为悬挂顶点悬挂顶点，与它关联的边称为，与它关联的边称为，与它关联的边称为，与它关联的边称为悬挂边悬挂边悬挂边悬挂边。度为偶数度为偶数度为偶数度为偶数(奇数奇数奇数奇数)的顶点称为的顶点称为的顶点称为的顶点称为偶度偶度偶度偶度(奇度奇度奇度奇度)顶点顶点顶点顶点。第17页，共34页，编辑于2022年，星期一图的度数举例图的度数举例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

23、 7是悬挂边。是悬挂边。是悬挂边。是悬挂边。d+(a)4 4，d-(a)1 1+4 4 +0 0-3 3 -1 1度数列：度数列：度数列：度数列：4 4、4 4、2 2、1 1、3 3出：出：4、0、2、1 入：入：1、3、1、2边：边：边：边：7 7度数列：度数列：5、3、3、3 边数：边数：7第18页，共34页，编辑于2022年，星期一握手定理握手定理(The Handshaking Theorem)定理定理定理定理1 1 设设设设G G为任意无向图，为任意无向图，V Vv v1 1,v v2 2,v vn，|E|mm，则则则则说明说明说明说明任何无向图中，各顶点度数之和等于边数的两倍。任

24、何无向图中，各顶点度数之和等于边数的两倍。证明证明证明证明G中每条边中每条边中每条边中每条边(包括环包括环包括环包括环)均有两个端点，所以在计算均有两个端点，所以在计算均有两个端点，所以在计算均有两个端点，所以在计算G中各顶中各顶点度数之和时，点度数之和时，每条边均提供每条边均提供2度，当然，度，当然，mm条边，共提条边，共提供供2mm度。度。度。度。定理定理定理定理2 2 2 2 设设设设D D 为任意有向图，为任意有向图，为任意有向图，为任意有向图，V V v v1,v v2 2,v vn，|E E|mm，则则则则 第19页，共34页，编辑于2022年，星期一推论推论推论推论任何图任何图任

25、何图任何图(无向或有向无向或有向无向或有向无向或有向)中，奇度顶点的个数是偶数。中，奇度顶点的个数是偶数。中，奇度顶点的个数是偶数。中，奇度顶点的个数是偶数。证明证明证明证明设设设设G G 为任意一图，令为任意一图，令为任意一图，令为任意一图，令V V1 1v v|v vVd(v v)为奇数为奇数V V2 2 v v|vVd d(v v)为偶数为偶数为偶数为偶数 则则则则V1 1V V2 2V，V V1 1 V2 2 ，由握手定理可知由握手定理可知由握手定理可知由握手定理可知 由于由于由于由于2 2 2 2m和和和和，所以，所以为偶数为偶数，但因但因但因但因V V1 1中顶点度数为奇数，中顶点

26、度数为奇数，中顶点度数为奇数，中顶点度数为奇数，所以所以所以所以|V V1|必为偶数。必为偶数。必为偶数。必为偶数。第20页，共34页，编辑于2022年，星期一例：例：例：例：(3,3,2,1)(3,3,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)

27、，(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,2,2,2,1)(3,2,2,2,1)可以图化可以图化 若非负整数列可以对应为图的度数列，则称若非负整数列可以对应为图的度数列，则称之为可图化。之为可图化。第21页，共34页，编辑于2022年，星期一定理定理4 设设G G为任意为任意为任意为任意n n阶无向简单图，则阶无向简单图，则阶无向简单图，则阶无向简单图，则(G)n n-1-1。证明证明证明证明因为因为因为因为G G既无平行边也无环

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

29、,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页，编辑于2022年，星期一(3)(3,3,3,1)(3)(3,3,3,1)(3)(3,3,3,1)(3)(3,3,3,1)可图化，不可简单图化。可图化，不可简单

30、图化。可图化，不可简单图化。可图化，不可简单图化。假设可以简单图化，设假设可以简单图化，设假设可以简单图化，设假设可以简单图化，设G G 以该序列为度数列以该序列为度数列设设设设V V v1 1,v,v2 2,v,v3 3,v,v4 4且且 d d(v v1)d d(v v2 2)d d(v3 3)3,d(v v4 4)1 1，由于由于由于由于d d(v v4 4)1 1，因而因而因而因而v v4 4只能与只能与只能与只能与v v1，v v2 2，v3 3之一相邻，去掉之一相邻，去掉之一相邻，去掉之一相邻，去掉v v4 4后，与后，与v v4 4关联的边也去掉，于是剩余的关联的边也去掉，于是剩

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

32、成的图必定也不是简单图。图必定也不是简单图。图必定也不是简单图。图必定也不是简单图。即有即有即有即有(3)(3)中序列也不可简单图化。中序列也不可简单图化。中序列也不可简单图化。中序列也不可简单图化。第23页，共34页，编辑于2022年，星期一(5)(4,4,3,3,2,2)(5)(4,4,3,3,2,2)可简单图化。下图中两个可简单图化。下图中两个可简单图化。下图中两个可简单图化。下图中两个6阶无向简单图都以阶无向简单图都以阶无向简单图都以阶无向简单图都以(5)(5)中序列为中序列为中序列为中序列为度数列。度数列。度数列。度数列。第24页，共34页，编辑于2022年，星期一定义定义定义定义5

33、 5 设设设设G G1 ，G G2 2 为两个无向图，为两个无向图，若存在双射函数若存在双射函数f f：V V1 1V2 2，对于对于对于对于v vi i,v vj jV V1 1，(v vi i,v vj j)E E1 1当且当且当且当且仅当仅当仅当仅当(f(v vi i),f f(v vj j)E2 2，并且并且并且并且(v vi i,v vj j)与与与与(f(v vi),),f f(v vj j)的重数相同，的重数相同，的重数相同，的重数相同，则称则称G1 1与与与与G G2 2是同构的是同构的是同构的是同构的(isomorphicisomorphic)，记做，记做，记做，记做G G1

34、 1 G G2。说明说明说明说明(1)(1)点数、边数和度数列对影响等。点数、边数和度数列对影响等。点数、边数和度数列对影响等。点数、边数和度数列对影响等。(2)(2)在图同构的意义下，图的数学定义与图形表示是一在图同构的意义下，图的数学定义与图形表示是一在图同构的意义下，图的数学定义与图形表示是一在图同构的意义下，图的数学定义与图形表示是一一对应的。一对应的。一对应的。一对应的。方法一：边方法一：边 伸缩伸缩方法二：点方法二：点 挪动挪动a ab bcd da abc cd d第25页，共34页，编辑于2022年，星期一 ab be ed dc ce ead dc cb be1e1e e2

35、2e e2 2第26页，共34页，编辑于2022年，星期一完全图完全图(complete graph)定义定义6 设设G为为n阶无向阶无向简单图简单图，若，若G中每个顶点均与中每个顶点均与其其余余的的n-1个顶点相邻，则称个顶点相邻，则称G为为n阶无向完全图阶无向完全图，简，简称称n阶完全图阶完全图，记做，记做Kn(n1)。设设D为为n阶有向简单图，若阶有向简单图，若D中任意两个不同的顶中任意两个不同的顶点之间都存在两条方向相反的边，则称点之间都存在两条方向相反的边，则称D是是n阶有阶有向完全图向完全图。n阶无向完全图的边数为：阶无向完全图的边数为：n(n-1)/2-1)/2n阶有向完全图的边

36、数为：阶有向完全图的边数为：n(n-1)-1)第27页，共34页，编辑于2022年，星期一完全图举例完全图举例K5 53 3阶有向完全图阶有向完全图4 4阶竞赛图阶竞赛图第28页，共34页，编辑于2022年，星期一子图子图(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，称以称以V1为顶点为

37、顶点集，以集，以G中两个端点都在中两个端点都在V1中的边组成边集中的边组成边集E1的图为的图为G的的V1导出的子图（导出的子图（induced subgraph），记作记作GV1。设设E1 E且且E1，称以称以E1为边集，以为边集，以E1中边关联的顶中边关联的顶点为顶点集点为顶点集V1的图为的图为G的的E1导出的子图（导出的子图（induced subgraph），记作，记作GE1。点全选！点全选！点全选！点全选！点不一定全选！点不一定全选！第29页，共34页，编辑于2022年，星期一例：画出例：画出例：画出例：画出K4 4的所有非同构的生成子图。的所有非同构的生成子图。的所有非同构的生成子图

38、。的所有非同构的生成子图。解解解解 :K K4 4的所有非同构的生成子图如图所示的所有非同构的生成子图如图所示的所有非同构的生成子图如图所示的所有非同构的生成子图如图所示 第30页，共34页，编辑于2022年，星期一导出子图举例导出子图举例在上图中，设在上图中，设在上图中，设在上图中，设G G为为(1)中图所表示，中图所表示，取取取取V V1 a,b,c，则则则则V V1 1的导出子图的导出子图的导出子图的导出子图G G V V1 1 为为为为(2)(2)中图所示。中图所示。中图所示。中图所示。取取取取E E1 1 e1 1,e e3，则则则则E E1 1的导出子图的导出子图的导出子图的导出子

39、图G G E1 1 为为(3)中图所示。中图所示。第31页，共34页，编辑于2022年，星期一例例例例3 画出画出4阶阶3条边的所有非同构的无向简单图。条边的所有非同构的无向简单图。由握手定理可知，所画的无向简单图各顶点度数之和为由握手定理可知，所画的无向简单图各顶点度数之和为由握手定理可知，所画的无向简单图各顶点度数之和为由握手定理可知，所画的无向简单图各顶点度数之和为232323236 6 6 6，最大度小于或等于，最大度小于或等于，最大度小于或等于，最大度小于或等于3 3 3 3。于是所求无向简单图的度数列应满。于是所求无向简单图的度数列应满。于是所求无向简单图的度数列应满。于是所求无向

40、简单图的度数列应满足的条件是，将足的条件是，将足的条件是，将足的条件是，将6 6 6 6分成分成分成分成4 4 4 4个非负整数，每个整数均大于或等于个非负整数，每个整数均大于或等于个非负整数，每个整数均大于或等于个非负整数，每个整数均大于或等于0 0 0 0且小于或等于且小于或等于且小于或等于且小于或等于3 3 3 3，并且，并且，并且，并且奇数的个数为偶数奇数的个数为偶数。将这样的整数。将这样的整数。将这样的整数。将这样的整数列排出来只有下面三种情况：列排出来只有下面三种情况：列排出来只有下面三种情况：列排出来只有下面三种情况：(1)2(1)2(1)2(1)2，2 2 2 2，1 1 1

41、1，1 1 1 1(2)3(2)3(2)3(2)3，1 1 1 1，1 1 1 1，1 1 1 1(3)2(3)2(3)2(3)2，2 2 2 2，2 2 2 2，0 0 0 0 将每种度数列所有非同构的图将每种度数列所有非同构的图将每种度数列所有非同构的图将每种度数列所有非同构的图都画出来即得所要求的全部非都画出来即得所要求的全部非都画出来即得所要求的全部非都画出来即得所要求的全部非同构的图。同构的图。同构的图。同构的图。第32页，共34页，编辑于2022年，星期一定义定义9 9 设设G 为为n阶无向简单图，以阶无向简单图，以V为顶点集，以所有为顶点集，以所有使使G成为完全图成为完全图Kn的

42、添加边组成的集合为的添加边组成的集合为边集的图，称为边集的图，称为G的的补图补图(complementary graphcomplementary graph)，记作，记作G。若图若图GG，则称为则称为G是是自补图自补图。(1)(1)(1)(1)为自补图为自补图为自补图为自补图(2)(2)(2)(2)和和和和(3)(3)(3)(3)互为补图互为补图互为补图互为补图，显然，显然，显然，显然(2)(2)(2)(2)和和和和(3)(3)(3)(3)不同构不同构不同构不同构，不自补，不自补，不自补，不自补第33页，共34页，编辑于2022年，星期一课后作业题：课后作业题：173173页页 7.17.17.157.15其中选作的是：其中选作的是：7.9 7.9、7.127.12、7.147.14、7.157.15其余的必做！其余的必做！第34页，共34页，编辑于2022年，星期一