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

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

1、 1 2第一讲第一讲 无向图及有向图无向图及有向图知识结构知识结构图的定义图的定义图的一些概念和规定图的一些概念和规定简单图和多重图简单图和多重图顶点的度数与握手定理顶点的度数与握手定理图的同构图的同构子图与补图子图与补图 4 引例引例1 1：哥尼斯堡七桥哥尼斯堡七桥问题问题问题问题（图论应用的开始）（图论应用的开始）（图论应用的开始）（图论应用的开始）l l问：能否从某地出发，通过每桥恰好一次，走遍了七桥问：能否从某地出发，通过每桥恰好一次，走遍了七桥问：能否从某地出发，通过每桥恰好一次，走遍了七桥问：能否从某地出发，通过每桥恰好一次，走遍了七桥 后又返回到原处？后又返回到原处？后又返回到原

2、处？后又返回到原处？l l瑞士数学家瑞士数学家瑞士数学家瑞士数学家欧拉欧拉欧拉欧拉在在在在1736173617361736年发表了一篇论文讨论这个问题，年发表了一篇论文讨论这个问题，年发表了一篇论文讨论这个问题，年发表了一篇论文讨论这个问题，指出这个问题无解。指出这个问题无解。指出这个问题无解。指出这个问题无解。普雷格尔河 5欧拉：传奇的一生欧拉：传奇的一生q年少时，听从父亲的安排，年少时，听从父亲的安排，巴塞尔大学巴塞尔大学，学习，学习神学神学和和希伯来语希伯来语，结果被约翰结果被约翰伯努利欣赏，伯努利欣赏，1717岁获得硕士学位之后，才开始专岁获得硕士学位之后，才开始专供数学。供数学。q为

3、获得圣彼得堡科学院的医学部的职位空缺，的职位空缺，欧拉在巴塞尔便全力投入生理学的研究，并出席医学报告会。1727年，等他到等他到达俄罗斯时，叶卡捷琳娜一世女皇去世，他进入数学部。达俄罗斯时，叶卡捷琳娜一世女皇去世，他进入数学部。q1733年，欧拉回到瑞士，并结婚，一生共生育13个孩子，5个存活。q为了赢得巴黎奖金而投身于一个天文学问题，那是几个有影响的大数学家搞了几个月时间的，欧拉在三天之后把它解决了。可是过分的劳累使他得了一场病，病中右眼失明了。q欧拉到底出了多少著作，直至1936年人们也没有确切的了解。但据估计，要出版已经搜集到的欧拉著作，将需用大4开本60至80卷。彼得堡学院为了整理他的

4、著作整整花了47年。问题问题2(2(哈密顿环球旅行哈密顿环球旅行问题，问题，18571857年年):):十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020个城市，个城市，能否从某个城市出发在十二面体上依次经过每个能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）哈密顿圈（环球旅行游戏）问题问题3(3(四色问题四色问题):):对任何一张地图进行着色，两个共同边界的对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了国家染不同的颜色，则只需要四种颜色就够了.问题问题4(4(关键路径问

5、题关键路径问题):):一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体育一座体育中心中心,小至组装一台机床小至组装一台机床,一架电视机一架电视机,都要包括都要包括许多工序许多工序.这些工序相互约束这些工序相互约束,只有在某些工序完只有在某些工序完成之后成之后,一个工序才能开始一个工序才能开始.即它们之间存在完即它们之间存在完成的先后次序关系成的先后次序关系,一般认为这些关系是预知的一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间而且也能够预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多这时工程领导人员迫切希望了解最少需要多少时间才能够完成整

6、个工程项目少时间才能够完成整个工程项目,影响工程进度影响工程进度的要害工序是哪几个？的要害工序是哪几个？二、图的概念二、图的概念二、图的概念二、图的概念 q设设A，B为任意的两个集合，为任意的两个集合，a,b|aAbB为为A与与B的的无序积无序积，记作，记作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,

7、b),(b,b).定义定义定义定义1 1 一个一个一个一个无向图（无向图（无向图（无向图（undirected graphundirected graph）是一个有序的二元是一个有序的二元是一个有序的二元是一个有序的二元组组组组,记作记作记作记作G G，其中其中其中其中（1 1）V V 称为称为称为称为顶点集顶点集顶点集顶点集，其元素称为，其元素称为，其元素称为，其元素称为顶点顶点顶点顶点或或或或结点结点结点结点（verticesvertices,nodesnodes）。（2 2）E E称为称为称为称为边集边集边集边集，它是，它是，它是，它是无序积无序积无序积无序积V V&V V的多重子集，其

8、元的多重子集，其元的多重子集，其元的多重子集，其元素称为素称为素称为素称为无向边无向边无向边无向边，简称，简称，简称，简称边（边（边（边（edgesedges）。例例例例1 1(1)(1)给定无向图给定无向图给定无向图给定无向图G G ，其中其中其中其中 V V v1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5).例例例例1 1 （2 2）E,定义定义2 一个一个有向图有向图（directed graph）是一个有序的）是一个有序的二元组二元组，记作记作D，其中其中（1）V称为顶点集，其元素称为称为顶

9、点集，其元素称为顶点顶点或或结点结点。（2）E为边集，它是笛卡儿积为边集，它是笛卡儿积VV的多重子集，其的多重子集，其元素称为元素称为有向边有向边，简称，简称边边。图的一些概念和规定图的一些概念和规定图的一些概念和规定图的一些概念和规定qG G表示无向图，但有时用表示无向图，但有时用表示无向图，但有时用表示无向图，但有时用G G泛指图泛指图泛指图泛指图(无向的或有向的无向的或有向的无向的或有向的无向的或有向的)。qD D只能表示有向图。只能表示有向图。只能表示有向图。只能表示有向图。qV V(G G)，E E(G G)分别表示分别表示分别表示分别表示G G的的的的顶点集顶点集顶点集顶点集和和和

10、和边集边集边集边集。q若若若若|V V(G G)|)|n n，则称则称则称则称G G为为为为n n阶图阶图阶图阶图。q若若若若|V V(G G)|)|与与与与|E E(G G)|)|均为有限数，则称均为有限数，则称均为有限数，则称均为有限数，则称G G为为为为有限图有限图有限图有限图。q若边集若边集若边集若边集E(G)E(G)，则称则称则称则称G G为为为为零图零图零图零图，此时，又若，此时，又若，此时，又若，此时，又若G G为为为为n n阶阶阶阶图，则称图，则称图，则称图，则称G G为为为为n n阶零图阶零图阶零图阶零图，记作，记作，记作，记作N Nn n，特别地，称特别地，称特别地，称特别

11、地，称N N1 1为为为为平凡平凡平凡平凡图图图图(trivial graphtrivial graph)。关联与关联次数、环、孤立点关联与关联次数、环、孤立点 q设设设设G G 为无向图，为无向图，为无向图，为无向图，e ek k(v vi i,v vj j)E E，称称称称v vi i,v vj j为为为为e ek k的端点的端点的端点的端点，e ek k与与与与v vi i或或或或e ek k与与与与v vj j是彼此相是彼此相是彼此相是彼此相关联关联关联关联的。的。的。的。若若若若v vi i v vj j，则称则称则称则称e ek k与与与与v vi i或或或或e ek k与与与与v

12、 vj j的的的的关联次数为关联次数为关联次数为关联次数为1 1。若若若若v vi iv vj j，则称则称则称则称e ek k与与与与v vi i的的的的关联次数为关联次数为关联次数为关联次数为2 2，并称，并称，并称，并称e ek k为为为为环环环环。任意的任意的任意的任意的v vl lV V，若若若若v vl l v vi i且且且且v vl l v vj j，则称则称则称则称e ek k与与与与v vl l的的的的关联次数关联次数关联次数关联次数为为为为0 0。q设设设设D D 为有向图，为有向图，为有向图，为有向图，e ek k E E，称称称称v vi i,v vj j为为为为e

13、ek k的的的的端点。端点。端点。端点。若若若若v vi iv vj j，则称则称则称则称e ek k为为为为D D中的中的中的中的环环环环。q无论在无向图中还是在有向图中，无边关联的顶点均无论在无向图中还是在有向图中，无边关联的顶点均无论在无向图中还是在有向图中，无边关联的顶点均无论在无向图中还是在有向图中，无边关联的顶点均称为称为称为称为孤立点孤立点孤立点孤立点(isolated verticesisolated vertices)。相邻与邻接相邻与邻接 q设无向图设无向图设无向图设无向图G G ，v vi i，v vj jV V，e ek k，e el lE E。若若若若 e et tE

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

15、vj j为为为为e et t的的的的终点终点终点终点，并称，并称，并称，并称v vi i邻接到邻接到邻接到邻接到v vj j，v vj j邻接于邻接于邻接于邻接于v vi i。若若若若e ek k的终点为的终点为的终点为的终点为e el l的始点，则称的始点，则称的始点，则称的始点，则称e ek k与与与与e el l相邻相邻相邻相邻(adjacentadjacent)。v vi iv vj je ek ke el lv vi iv vj je ek ke el l简单图与多重图简单图与多重图 定义定义定义定义3 3 在无向图中，关联一对顶点的无向边如果多于在无向图中，关联一对顶点的无向边如果

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

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

18、边，是平行边，是平行边，不是简单图。不是简单图。不是简单图。不是简单图。顶点的度数顶点的度数(degree)定义定义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

19、)，简记作简记作d-(v)。称称d+(v)+d-(v)为为v的的度数度数，记做，记做d(v)。16设设设设G G 为一个为一个为一个为一个n n阶无向图，阶无向图，阶无向图，阶无向图，V V v v1 1,v v2 2,v vn n，称称称称d d(v v1 1)，d d(v v2 2)，d d(v vn n)为为为为G G的的的的度数列度数列度数列度数列。对于顶点标定的无向图，它的度数列是唯一的。对于顶点标定的无向图，它的度数列是唯一的。对于顶点标定的无向图，它的度数列是唯一的。对于顶点标定的无向图，它的度数列是唯一的。类似地，设类似地，设类似地，设类似地，设D D 为一个为一个为一个为一个

20、n n阶有向图，阶有向图，阶有向图，阶有向图，V V v v1 1,v v2 2,v vn n，称称称称d d(v v1 1)，d d(v v2 2)，d d(v vn n)为为为为D D的的的的度数列度数列度数列度数列，另外称另外称另外称另外称d d+(v v1 1)，d d+(v v2 2)，d d+(v vn n)与与与与d d-(v v1 1)，d d-(v v2 2)，d d-(v vn n)分别为分别为分别为分别为D D的的的的出度列出度列出度列出度列和和和和入度列入度列入度列入度列。度数列为度数列为4,4,2,1,34,4,2,1,3。度数列，出度数列，出度列，入度度列，入度列分

21、别为列分别为5,3,3,35,3,3,34,0,2,14,0,2,11,3,1,21,3,1,2图的度数的相关概念图的度数的相关概念q在无向图在无向图在无向图在无向图G G中，中，中，中，最大度最大度最大度最大度(G G)maxmaxd d(v v)|)|v vV V(G G)最小度最小度最小度最小度(G G)minmind d(v v)|)|v vV V(G G)q在有向图在有向图在有向图在有向图D D中，中，中，中，最大出度最大出度最大出度最大出度+(D D)maxmaxd d+(v v)|)|v vV(V(D D)最小出度最小出度最小出度最小出度 +(D D)minmind d+(v v

22、)|)|v vV V(D D)最大入度最大入度最大入度最大入度-(D D)maxmaxd d-(v v)|)|v vV V(D D)最小入度最小入度最小入度最小入度 -(D D)minmind d-(v v)|)|v vV V(D D)q称度数为称度数为称度数为称度数为1 1的顶点为的顶点为的顶点为的顶点为悬挂顶点悬挂顶点悬挂顶点悬挂顶点，与它关联的边称为，与它关联的边称为，与它关联的边称为，与它关联的边称为悬悬悬悬挂边挂边挂边挂边。度为偶数。度为偶数。度为偶数。度为偶数(奇数奇数奇数奇数)的顶点称为的顶点称为的顶点称为的顶点称为偶度偶度偶度偶度(奇度奇度奇度奇度)顶点顶点顶点顶点。图的度数举

23、例图的度数举例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 2、1 1、3 3出：出：4、0、2、1 入：入：1、3、1、2边：边：边：边：7 7度数列：度数列：5、3、3、3 边数：边数：7握手定理握手定理(The Handshaking T

24、heorem)定理定理定理定理1 1 设设设设G G 为任意无向图，为任意无向图，为任意无向图，为任意无向图，V V v v1 1,v v2 2,v vn n，|E E|mm，则则则则说明说明说明说明 任何无向图中，各顶点度数之和等于边数的两倍。任何无向图中，各顶点度数之和等于边数的两倍。任何无向图中，各顶点度数之和等于边数的两倍。任何无向图中，各顶点度数之和等于边数的两倍。证明证明证明证明 G G中每条边中每条边中每条边中每条边(包括环包括环包括环包括环)均有两个端点，所以在计算均有两个端点，所以在计算均有两个端点，所以在计算均有两个端点，所以在计算GG中中中中各顶点度数之和时，各顶点度数之

25、和时，各顶点度数之和时，各顶点度数之和时，每条边均提供每条边均提供每条边均提供每条边均提供2 2度，当然，度，当然，度，当然，度，当然，mm条边，条边，条边，条边，共提供共提供共提供共提供2 2mm度。度。度。度。定理定理定理定理2 2 2 2 设设设设D D 为任意有向图，为任意有向图，为任意有向图，为任意有向图，V V v v1 1,v v2 2,v vn n，|E E|mm，则则则则 推论推论推论推论推论推论 任何图任何图任何图任何图(无向或有向无向或有向无向或有向无向或有向)中，奇度顶点的个数是偶数。中，奇度顶点的个数是偶数。中，奇度顶点的个数是偶数。中，奇度顶点的个数是偶数。证明证明

26、证明证明 设设设设G G 为任意一图，令为任意一图，令为任意一图，令为任意一图，令V V1 1 v v|v vV Vd d(v v)为奇数为奇数为奇数为奇数 V V2 2 v v|v vV Vd d(v v)为偶数为偶数为偶数为偶数 则则则则V V1 1V V2 2V V，V V1 1 V V2 2 ，由握手定理可知由握手定理可知由握手定理可知由握手定理可知 由于由于由于由于2 2 2 2mm和和和和，所以，所以为偶数为偶数，但因但因但因但因V V1 1中顶点度数为奇数，中顶点度数为奇数，中顶点度数为奇数，中顶点度数为奇数，所以所以所以所以|V V1 1|必为偶数。必为偶数。必为偶数。必为偶数

27、。例：例：例：例：(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,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)是否可图化？是否可图化？是否可图化？是否可图化？解：解：解：解：(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,2,2,1,1)(3,2,2,1,1)不可以图化不可以图化不可以图化不

28、可以图化 (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 4 设设设设G G为任意为任意为任意为任意n n阶无向简单图，则阶无向简单图，则阶无向简单图，则阶无向简单图，则(G G)n n-1-1。证明证明证明证明 因为因为因为因为G G既无既无既无既无平行边平行边平行边平行边也无也无也无也无环环环环

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

30、,5,4,4,2,1)不可图化。不可图化。不可图化。不可图化。(2)(5,4,3,2,2)(2)(5,4,3,2,2)可图化，不可简单图化。若它可简单图化，可图化，不可简单图化。若它可简单图化，可图化，不可简单图化。若它可简单图化，可图化，不可简单图化。若它可简单图化，设所得图为设所得图为设所得图为设所得图为G G，则则则则(G G)max5,4,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)可图化，不可简单图化。可图化，不可简单图化。可图化，不可简单图

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

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

33、此时若加入者环，不是简单图，此时若加入者环，不是简单图，此时若加入v v4 4及与及与及与及与v v4 4关联的边构成的关联的边构成的关联的边构成的关联的边构成的图必定也不是简单图。图必定也不是简单图。图必定也不是简单图。图必定也不是简单图。即有即有即有即有(3)(3)中序列也不可简单图化。中序列也不可简单图化。中序列也不可简单图化。中序列也不可简单图化。(5)(4,4,3,3,2,2)(5)(4,4,3,3,2,2)可简单图化。下图中两个可简单图化。下图中两个可简单图化。下图中两个可简单图化。下图中两个6 6阶无向简单图都以阶无向简单图都以阶无向简单图都以阶无向简单图都以(5)(5)中中中中

34、序列为度数列。序列为度数列。序列为度数列。序列为度数列。定义定义定义定义5 5 设设设设G G1 1 ，G G2 2 为两个无向图，为两个无向图，为两个无向图，为两个无向图，若存在若存在若存在若存在双射函数双射函数双射函数双射函数f f：V V1 1V V2 2，对于对于对于对于v vi i,v vj jV V1 1，(v vi i,v vj j)E E1 1当且仅当当且仅当当且仅当当且仅当(f f(v vi i),),f f(v vj j)E E2 2，并且并且并且并且(v vi i,v vj j)与与与与(f f(v vi i),),f f(v vj j)的重数相同，的重数相同，的重数相同

35、，的重数相同，则称则称则称则称G G1 1与与与与G G2 2是同构的是同构的是同构的是同构的(isomorphicisomorphic)，记做，记做，记做，记做G G1 1 G G2 2。说明说明说明说明(1)(1)点数、边数和度数列对影响等。点数、边数和度数列对影响等。点数、边数和度数列对影响等。点数、边数和度数列对影响等。(2)(2)在图同构的意义下，图的数学定义与图形表示在图同构的意义下，图的数学定义与图形表示在图同构的意义下，图的数学定义与图形表示在图同构的意义下，图的数学定义与图形表示是一一对应的。是一一对应的。是一一对应的。是一一对应的。方法一：边方法一：边 伸缩伸缩方法二：点方

36、法二：点 挪动挪动a ab bc cd da ab bc cd d a ab be ed dc ce ea ad dc cb be e1 1e e1 1e e2 2e e2 2完全图完全图(complete graph)定义定义6 设设G为为n阶无向阶无向简单图简单图，若，若G中每个顶点均中每个顶点均与与其余其余的的n-1个顶点相邻，则称个顶点相邻，则称G为为n阶无向完阶无向完全图全图，简称，简称n阶完全图阶完全图，记做，记做Kn(n1)。设设D为为n阶有向简单图，若阶有向简单图，若D中任意两个不同的中任意两个不同的顶点之间都存在两条方向相反的边，则称顶点之间都存在两条方向相反的边，则称D是是

37、n阶有向完全图阶有向完全图。n阶无向完全图的边数为：阶无向完全图的边数为：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

38、且且V1，称以称以V1为顶为顶点集，以点集，以G中两个端点都在中两个端点都在V1中的边组成边集中的边组成边集E1的图为的图为G的的V1导出的子图（导出的子图（induced subgraph），记作记作GV1。设设E1 E且且E1，称以称以E1为边集，以为边集，以E1中边关联中边关联的顶点为顶点集的顶点为顶点集V1的图为的图为G的的E1导出的子图导出的子图（induced subgraph），记作，记作GE1。点全选！点全选！点全选！点全选！点不一定全选！点不一定全选！点不一定全选！点不一定全选！例：画出例：画出例：画出例：画出K K4 4的所有非同构的生成子图。的所有非同构的生成子图。的所有

39、非同构的生成子图。的所有非同构的生成子图。解解解解 :K K4 4的所有非同构的生成子图如图所示的所有非同构的生成子图如图所示的所有非同构的生成子图如图所示的所有非同构的生成子图如图所示 导出子图举例导出子图举例在上图中，设在上图中，设在上图中，设在上图中，设G G为为为为(1)(1)中图所表示，中图所表示，中图所表示，中图所表示，取取取取V V1 1 a,b,ca,b,c，则则则则V V1 1的导出子图的导出子图的导出子图的导出子图G G V V1 1 为为为为(2)(2)中图所示。中图所示。中图所示。中图所示。取取取取E E1 1 e e1 1,e e3 3，则则则则E E1 1的导出子图

40、的导出子图的导出子图的导出子图G G E E1 1 为为为为(3)(3)中图所示。中图所示。中图所示。中图所示。例例例例3 3 画出画出画出画出4 4阶阶阶阶3 3条边的所有非同构的无向条边的所有非同构的无向条边的所有非同构的无向条边的所有非同构的无向简单图简单图简单图简单图。由由由由握手定理握手定理握手定理握手定理可知，所画的无向简单图各顶点度数之和可知，所画的无向简单图各顶点度数之和可知，所画的无向简单图各顶点度数之和可知，所画的无向简单图各顶点度数之和为为为为2 2 2 23 3 3 36 6 6 6，最大度小于或等于，最大度小于或等于，最大度小于或等于，最大度小于或等于3 3 3 3。

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

42、整数列排出来只有下面三种情。将这样的整数列排出来只有下面三种情况：况：况：况：(1)2(1)2(1)2(1)2，2 2 2 2，1 1 1 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 将每种度数列所有非同构的将每种度数列所有非同构的将每种度数列所有非同构的将每种度数列所有非同构的图都画出来即得所要求的全图都画出来即得所要求的全图都画出来即得所要求的全图都画出来即得所要求的全部非同构的图。部非同构的图。部非同构的图。部非同构的图。定义定义9 9 设设G 为为n阶

43、无向简单图，以阶无向简单图，以V为顶点集，以为顶点集，以所有使所有使G成为完全图成为完全图Kn的添加边组成的集合为的添加边组成的集合为边集的图，边集的图，称为称为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)不同构不同构不同构不同构，不自补，不自补，不自补，不自补 34课后作业题：课后作业题：173173页页 7.17.157.17.15其中选作的是：其中选作的是：7.9 7.9、7.127.12、7.147.14、7.157.15其余的必做！其余的必做！