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

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