第七章 图的基本概念 (2)精选文档.ppt

《第七章 图的基本概念 (2)精选文档.ppt》由会员分享，可在线阅读，更多相关《第七章 图的基本概念 (2)精选文档.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章第七章 图的基本概念图的基本概念1本讲稿第一页，共五十六页图论是近年来发展迅速而又应用广泛的一图论是近年来发展迅速而又应用广泛的一门新兴学科门新兴学科,皆在解决离散型的优化问题。它最皆在解决离散型的优化问题。它最早起源于一些数学游戏的难题研究，如早起源于一些数学游戏的难题研究，如17361736年年欧拉（欧拉（EulerEuler解决的哥尼斯堡七桥问题），以及解决的哥尼斯堡七桥问题），以及如迷宫问题，匿门博奕问题，棋盘上马的行走如迷宫问题，匿门博奕问题，棋盘上马的行走路线问题等在民间广泛流传的一些游戏难题。路线问题等在民间广泛流传的一些游戏难题。这些古老的难题，当时吸引了很多学者的注意，

2、这些古老的难题，当时吸引了很多学者的注意，在这些问题研究的基础上又继续提出了著名的在这些问题研究的基础上又继续提出了著名的四色猜想，哈密尔顿环游世界数学难题。四色猜想，哈密尔顿环游世界数学难题。本讲稿第二页，共五十六页18471847年，克希霍夫（年，克希霍夫（KirchhoffKirchhoff）用图论分析）用图论分析电路网络，这是图论最早应用于工程科学，以后随电路网络，这是图论最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示

3、出越来越大的效果。图论在各种物的问题时，显示出越来越大的效果。图论在各种物理学科，工程领域，社会科学和经济问题的广泛应理学科，工程领域，社会科学和经济问题的广泛应用，使它受到数学和工程界的特别重视。如通讯网用，使它受到数学和工程界的特别重视。如通讯网络的优化设计，交通站点的合理布局，生产组织的络的优化设计，交通站点的合理布局，生产组织的健全架构和工程作业的有效控制等问题，用图论的健全架构和工程作业的有效控制等问题，用图论的方法解决十分方便方法解决十分方便 本讲稿第三页，共五十六页图论是计算机及其相关专业的重要基础课。图论是计算机及其相关专业的重要基础课。通过图论学习可以为数据结构、数据库、通过

4、图论学习可以为数据结构、数据库、操作系统、编译程序及人工智能等后续课程的操作系统、编译程序及人工智能等后续课程的学习奠定基础。学习奠定基础。本讲稿第四页，共五十六页哥尼斯堡（哥尼斯堡（KonigstbergKonigstberg，现加里宁格勒）城市有一条横，现加里宁格勒）城市有一条横贯全城的普雷格尔（贯全城的普雷格尔（PregelPregel）河，河中有）河，河中有2 2个岛，河上有个岛，河上有7 7座桥与城市的各部分联接，如下图所示，每逢假日，城座桥与城市的各部分联接，如下图所示，每逢假日，城中居民进行环城逛游。中居民进行环城逛游。不知何时何日何人提出下面问题，能不能设计一次不知何时何日何人

5、提出下面问题，能不能设计一次“遍游遍游”使得从某地出发对每座跨河桥只走一次，使得从某地出发对每座跨河桥只走一次，而在通历了七桥之后却又能回到原地。而在通历了七桥之后却又能回到原地。哥尼斯堡七桥问题哥尼斯堡七桥问题本讲稿第五页，共五十六页哥尼斯堡七桥问题哥尼斯堡七桥问题本讲稿第六页，共五十六页 反复的奔走试行和失败，使人们对成功的可能发反复的奔走试行和失败，使人们对成功的可能发反复的奔走试行和失败，使人们对成功的可能发反复的奔走试行和失败，使人们对成功的可能发 生疑惑，猜想问题无解，但又谁也说不清其中道生疑惑，猜想问题无解，但又谁也说不清其中道生疑惑，猜想问题无解，但又谁也说不清其中道生疑惑，猜

6、想问题无解，但又谁也说不清其中道 理，于是有好事者去请教年轻的数学家欧拉理，于是有好事者去请教年轻的数学家欧拉理，于是有好事者去请教年轻的数学家欧拉理，于是有好事者去请教年轻的数学家欧拉(Euler)(Euler)(Euler)(Euler)，刚开始，刚开始，刚开始，刚开始欧拉也看不出这是一个数学问题欧拉也看不出这是一个数学问题欧拉也看不出这是一个数学问题欧拉也看不出这是一个数学问题,1736,1736,1736,1736年，年，年，年，29292929岁的欧拉把这一问题化成岁的欧拉把这一问题化成岁的欧拉把这一问题化成岁的欧拉把这一问题化成数学问题，严格地论证了上述数学问题，严格地论证了上述数

7、学问题，严格地论证了上述数学问题，严格地论证了上述“七桥问题七桥问题七桥问题七桥问题”无解，并由此开创了图论无解，并由此开创了图论无解，并由此开创了图论无解，并由此开创了图论与拓扑学的思维方式和诸多概念与理论，与拓扑学的思维方式和诸多概念与理论，与拓扑学的思维方式和诸多概念与理论，与拓扑学的思维方式和诸多概念与理论，1736173617361736年遂被公认为图论学科年遂被公认为图论学科年遂被公认为图论学科年遂被公认为图论学科的历史元年，欧拉被尊为图论与拓扑学之父的历史元年，欧拉被尊为图论与拓扑学之父的历史元年，欧拉被尊为图论与拓扑学之父的历史元年，欧拉被尊为图论与拓扑学之父.本讲稿第七页，共

8、五十六页欧拉回路欧拉回路本讲稿第八页，共五十六页简单图简单图本讲稿第九页，共五十六页本讲稿第十页，共五十六页多重图多重图本讲稿第十一页，共五十六页表示实际呼叫的呼叫图可以非常大。如AT研究的一个呼叫图，大约有2亿9千万个顶点和40亿条边。本讲稿第十二页，共五十六页伪图伪图本讲稿第十三页，共五十六页有向简单图有向简单图本讲稿第十四页，共五十六页本讲稿第十五页，共五十六页有向多重图有向多重图本讲稿第十六页，共五十六页本讲稿第十七页，共五十六页7.1 无向图及有向图无向图及有向图什什么么是是图图?可可用用一一句句话话概概括括，即即：图图是是用用点点和和线线来来刻刻划划离离散散事事物物集集合合中中的的

9、每每对对事事物物间间以以某某种种方方式式相相联联系系的的数数学学模模型型。因因为为它它显显得得太太抽抽象象，不不便便于于理理解解，所所以以有有必必要要给给出出把把图图作作为为代代数数结结构的一个定义。构的一个定义。本讲稿第十八页，共五十六页无向图的基本概念无向图的基本概念无向图无向图无向图无向图G G：一个有序二元组：一个有序二元组：一个有序二元组：一个有序二元组(V V,E E),),记记记记为为为为G G=(=(V V,E E)G G的点集合：的点集合：的点集合：的点集合：（例如：图（例如：图（例如：图（例如：图（1 1）中的）中的）中的）中的V=V=（1 1，2 2，3 3，4 4，5

10、5）是一个无向图的点的集合）是一个无向图的点的集合）是一个无向图的点的集合）是一个无向图的点的集合）G G的的的的边边边边集集集集合合合合：E E=e eij ij 且且且且e eij ij=v vi i,v vj j 为为为为右右右右图图图图无序二元组无序二元组无序二元组无序二元组 e eijijijij的的的的端端端端点点点点：有有有有e eijijijij=v=v=v=vi i i i,v,v,v,vj j j j ，则则则则称称称称v vi i i i和和和和v vj j j j为为为为e eijijijij的端点，且称的端点，且称的端点，且称的端点，且称e eijijijij 连接点

11、连接点连接点连接点 v vi i i i和和和和v vj j j j 。若若若若 v v v vi i i iv v v vj j j j ，称称称称e eijijijij与与与与v v v vi i i i（或或或或v v v vj j j j）的的的的关关关关联联联联次次次次数数数数为为为为1 1 1 1；若若若若 v v v vi i i iv v v vj j j j ，称称称称e eijijijij与与与与v v v vi i i i的的的的关关关关联联联联次次次次数数数数为为为为2 2 2 2；若若若若 v v v vi i i i不不不不是是是是e eijijijij的的的的端端

12、端端点点点点 ，称称称称e eijijijij与与与与v v v vi i i i的的的的关联次数为关联次数为关联次数为关联次数为0 0 0 0；环：两个端点重合为一点的边环：两个端点重合为一点的边环：两个端点重合为一点的边环：两个端点重合为一点的边 孤立点：不与任何边关联的点孤立点：不与任何边关联的点孤立点：不与任何边关联的点孤立点：不与任何边关联的点34512本讲稿第十九页，共五十六页关联：一条边的端点称为这条边的关联关联：一条边的端点称为这条边的关联相邻：与同一条边关联的端点称为是相邻相邻：与同一条边关联的端点称为是相邻 的，同时如果两条边有一个公共端的，同时如果两条边有一个公共端 点，

13、则称这两条边是相邻的点，则称这两条边是相邻的本讲稿第二十页，共五十六页分类分类设设设设G=G=G=G=V V V V，E E E E为一个图。为一个图。为一个图。为一个图。1 1 1 1）按结点的个数分类）按结点的个数分类）按结点的个数分类）按结点的个数分类（1 1 1 1）若）若）若）若|V(G)|,|E(G)|V(G)|,|E(G)|V(G)|,|E(G)|V(G)|,|E(G)|都是有限集合，都是有限集合，都是有限集合，都是有限集合，则称则称则称则称G G G G是有限图。是有限图。是有限图。是有限图。（2 2 2 2）若）若）若）若|V(G)|=n,|V(G)|=n,|V(G)|=n,

14、|V(G)|=n,则称则称则称则称G G G G为为为为n n n n阶图。阶图。阶图。阶图。（3 3 3 3）E(G)=E(G)=E(G)=E(G)=,则称则称则称则称G G G G为零图。为零图。为零图。为零图。若若若若|V(G)|=0,|V(G)|=0,|V(G)|=0,|V(G)|=0,称称称称G G G G为空图；为空图；为空图；为空图；若若若若|V(G)|=1,|V(G)|=1,|V(G)|=1,|V(G)|=1,称称称称G G G G为平凡图，为平凡图，为平凡图，为平凡图，而而而而|V(G)|=n,|V(G)|=n,|V(G)|=n,|V(G)|=n,称称称称G G G G为为为

15、为n n n n阶零图阶零图阶零图阶零图本讲稿第二十一页，共五十六页2 2）按同一对结点间的边数分类：）按同一对结点间的边数分类：平行边：平行边：（1 1）在无向图中，关联一对顶点的无向边）在无向图中，关联一对顶点的无向边如果多于一条，则称这些边为平行边，平行边如果多于一条，则称这些边为平行边，平行边的条数称为重数。的条数称为重数。（2 2）在有向图中，关联一对顶点的有向边）在有向图中，关联一对顶点的有向边如果多于一条，并且这些边的始点与终点相同如果多于一条，并且这些边的始点与终点相同（即方向相同），则称这些边为平行边。（即方向相同），则称这些边为平行边。本讲稿第二十二页，共五十六页定定义义7

16、.1.17.1.1 在在图图G G=中中，如如果果任任何何两两结结点点间间不不多多于于一一条条边边(对对于于有有向向图图中中，任任何何两两结结点点间间不不多多于于一一条条同同向向弧弧)，并并且且任任何何结结点点无无环环，则则图图G G称称为为简简单单图图；若若两两结结点点间间多多于于一一条条边边(对对于于有有向向图图中，两结点间多于一条同向弧中，两结点间多于一条同向弧)图图G G称为多重图。称为多重图。本讲稿第二十三页，共五十六页3 3）按图的边旁有无（字母，数量）特征分类：）按图的边旁有无（字母，数量）特征分类：定定义义7.1.27.1.2 给给每每条条边边或或弧弧都都赋赋予予权权的的图图G

17、 G=，称称为为加加权权图图，记记为为G G=，其其中中W W表表示示各各边边之权的集合。之权的集合。加加权权图图在在实实际际中中有有许许多多应应用用，如如在在输输油油管管系系统统图图中中权权表表示示单单位位时时间间流流经经管管中中的的石石油油数数量量；在在城城市市街街道道中中，权权表表示示表表示示通通行行车车辆辆密密度度；在在航航空空交交通通图图中中，权权表示两城市的距离等等。表示两城市的距离等等。本讲稿第二十四页，共五十六页4 4）按图的任意两个结点间是否有边连接分类：）按图的任意两个结点间是否有边连接分类：定义定义7.1.3 7.1.3 无向完全图：无向完全图：设设G G为为n n阶无向

18、简单图，若阶无向简单图，若D D中每个顶点均与其余的中每个顶点均与其余的n-1n-1个顶点相邻，则称个顶点相邻，则称G G为为n n阶阶无向完全图，简称无向完全图，简称n n阶完全图，记作阶完全图，记作 K Kn n本讲稿第二十五页，共五十六页定义定义7.1.4 7.1.4 有向完全图：设有向完全图：设D D为为n n阶有向简阶有向简单图，若单图，若D D中每个顶点都邻接到其余的中每个顶点都邻接到其余的n-1n-1个顶个顶点，又邻接于其余的点，又邻接于其余的n-1n-1个顶点，则称个顶点，则称D D为为n n阶有阶有向完全图。（边数为向完全图。（边数为n(n-1)n(n-1)）本讲稿第二十六页

19、，共五十六页定定义义7.1.57.1.5 在在有有向向图图G G=中中，对对任任意意结结点点v vV V，以以v v为为始始点点的的弧弧的的条条数数，称称为为结结点点v v的的出出度度，记记为为d d+(v v)；以以v v为为终终点点的的弧弧的的条条数数，称称为为v v的的入入度度，记记作作d d-(v v)；结结点点v v的的出出度度与与入入度度之之和和，称称 为为 结结 点点 的的 度度 数数，记记 为为d d(v v)，显显 然然d d(v v)=)=d d+(v v)+)+d d-(v v)。对对于于无无向向图图G G=，结结点点v vV V的的度度数数等等于于联联结结它它的的边边数

20、数，也也记记为为d d(v v)。若若v v点点有有环环，规规定该点度因环而增加定该点度因环而增加2 2。本讲稿第二十七页，共五十六页显然，对于孤立结点的度数为零。显然，对于孤立结点的度数为零。此外，对于无向图此外，对于无向图G G=，记，记(G G)或或=maxmax d d(v v)|)|v vV V(G G)或或=minmin d d(v v)|)|v vV V 它们分别称为图它们分别称为图G G 的最大度和最小度。的最大度和最小度。悬挂顶点：度数为悬挂顶点：度数为1 1的顶点。的顶点。悬挂边：与悬挂顶点关联的边。悬挂边：与悬挂顶点关联的边。偶（奇）度顶点：度为偶（奇）数的顶点。偶（奇）

21、度顶点：度为偶（奇）数的顶点。本讲稿第二十八页，共五十六页有向图的最大度与最小度：有向图的最大度与最小度：本讲稿第二十九页，共五十六页注：对简单图有注：对简单图有本讲稿第三十页，共五十六页关于无向图中的结点的度，欧拉给出一个定理，关于无向图中的结点的度，欧拉给出一个定理，这是图论中的第一个定理。这是图论中的第一个定理。定理定理7.1.17.1.1 （握手定理（握手定理)给定无（或有给定无（或有)向图向图G G=，V=vV=v1 1,v,v2 2,v,vn n,|E|=m,|E|=m,则则推论推论推论推论 在任何无向图中，奇度顶点的个数为偶数在任何无向图中，奇度顶点的个数为偶数 。本讲稿第三十一

22、页，共五十六页定理定理7.1.27.1.2 （握手定理（握手定理)给定有向图给定有向图G G=，V=v V=v1 1,v,v2 2,v,vn n,|E|=m|E|=m，则，则本讲稿第三十二页，共五十六页定义定义7.1.6 7.1.6 度数列：设度数列：设G=G=V,EV,E为为n n阶无向图，阶无向图，V=V=vv1 1,v,v2 2,v,vn n，称（，称（d(vd(v1 1),d(v),d(v2 2),),d(v,d(vn n)）为）为G G的的度数列。度数列。注：对于顶点标定的无向图的度数列是唯一的。注：对于顶点标定的无向图的度数列是唯一的。定义定义7.1.7 7.1.7 度数列的可图化

23、：对于给定的非整度数列的可图化：对于给定的非整数列数列d=dd=d1 1,d,d2 2,d,dn n ，若存在以，若存在以V=vV=v1 1,v,v2 2,v,vn n 为为顶点集的顶点集的n n阶无向图，使得阶无向图，使得d(vd(vi i)=d)=di i，则称，则称d d是可图是可图化的；若所得图是简单图，称化的；若所得图是简单图，称d d是可简单图化的。是可简单图化的。本讲稿第三十三页，共五十六页D D可图化的充分必要条件：可图化的充分必要条件：定理定理7.1.3 7.1.3 设非负整数列设非负整数列d=dd=d1 1,d,d2 2,d,dn n 则则d d是可图化的当且仅当是可图化的

24、当且仅当D D可简单图化的必要条件：可简单图化的必要条件：定理定理7.1.4 7.1.4 设设G G为任意为任意n n阶无向图，则阶无向图，则 本讲稿第三十四页，共五十六页举例举例求解下列各题求解下列各题:1 1、图、图G G的度数列为的度数列为2 2，2 2，3 3，5 5，6 6，则边数则边数m m为多少为多少?2 2、（3,3,2,3)3,3,2,3)、(5,2,3,1,4)(5,2,3,1,4)能能称称为为图图的的度序列吗？为什么？度序列吗？为什么？3 3、图、图G G有有1212条边，度数为条边，度数为3 3的结点有的结点有6 6个，个，余者度数均小于余者度数均小于3 3，问：问：G

25、 G至少有几个结点？至少有几个结点？本讲稿第三十五页，共五十六页3 3、由握手定理知、由握手定理知 deg(v)=2m=24 deg(v)=2m=24，度数为度数为3 3的结点有的结点有6 6个，占去个，占去1818度，度，还有还有6 6度由其余结点占有，度由其余结点占有，而而由由题题意意，其其余余结结点点的的度度数数均均小小于于3 3，可可为为0 0，1 1，2 2，当其余结点的度数均为当其余结点的度数均为2 2时所用结点数最少，时所用结点数最少，所所以以应应有有3 3个个结结点点占占有有此此6 6度度，即即G G中中至至少少有有9 9个个结结点。点。本讲稿第三十六页，共五十六页证证证证明明

26、明明：在在在在n n n n（n2n2n2n2）个个个个人人人人的的的的团团团团体体体体中中中中，总总总总有有有有两两两两个个个个人人人人在在在在此此此此团团团团体体体体中恰好有相同个数的朋友。中恰好有相同个数的朋友。中恰好有相同个数的朋友。中恰好有相同个数的朋友。解：解：解：解：以结点代表人，以结点代表人，以结点代表人，以结点代表人，二二二二人人人人如如如如果果果果是是是是朋朋朋朋友友友友，则则则则在在在在代代代代表表表表他他他他们们们们的的的的结结结结点点点点间间间间连连连连上上上上一一一一条条条条边边边边，这这这这样可得无向简单图样可得无向简单图样可得无向简单图样可得无向简单图G G G

27、 G，每个人的朋友数即图中代表它的结点的度数，每个人的朋友数即图中代表它的结点的度数，每个人的朋友数即图中代表它的结点的度数，每个人的朋友数即图中代表它的结点的度数，于于于于是是是是问问问问题题题题转转转转化化化化为为为为n n n n阶阶阶阶无无无无向向向向简简简简单单单单图图图图G G G G中中中中必必必必有有有有两两两两个个个个结结结结点点点点的的的的度度度度数相同。数相同。数相同。数相同。本讲稿第三十七页，共五十六页用反证法：用反证法：设设G G中各结点的度数均不相同，中各结点的度数均不相同，则度数列为则度数列为0 0，1 1，2 2，n-1n-1，即即图图中中有有度度数数为为0 0

28、的的孤孤立立结结点点，这这与与有有n-1n-1度度结结点点（因因为为是是简简单单图图，应应和和其其余余各各点点均均相相联联结）相矛盾，结）相矛盾，所以必有两个顶点的度数相同。所以必有两个顶点的度数相同。本讲稿第三十八页，共五十六页定定义义7.1.87.1.8 给给定定无无向向图图G G1 1=和和G G2 2=，于是，于是(1)(1)如如果果V V2 2 V V1 1和和E E2 2 E E1 1，则则称称G G2 2为为G G1 1的的子子图图，记为记为G G2 2 G G1 1。(2)(2)如如果果V V2 2 V V1 1，E E2 2 E E1 1且且E E2 2E E1 1，则则称称

29、G G2 2为为G G1 1的真子图，记为的真子图，记为G G2 2 G G1 1。(3)(3)如如果果V V2 2=V V1 1，E E2 2 E E1 1，则则称称G G2 2为为G G1 1的的生生成成子子图图，记为，记为G G2 2 G G1 1。本讲稿第三十九页，共五十六页(3)如如果果V2 V1和和V2 ，以以V2为为顶顶点点集集，以以两两个个端端点点都都在在V2中中的的全全体体边边为为边边集集的的G的的子子图图，称为称为V2 导出的导出子图。导出的导出子图。(4)如如果果E2 E1和和E2 ，以以E2为为边边集集，以以E2中中的的边边关关联联的的顶顶点点的的全全体体为为顶顶点点集

30、集的的G的的子子图图，称为称为E2 导出的导出子图。导出的导出子图。本讲稿第四十页，共五十六页本讲稿第四十一页，共五十六页定定义义7.1.97.1.9 给给定定图图G G=，若若存存在在图图G G1 1=，并并且且E E1 1E E=和和图图 是是完完全全图图，则则G G1 1称称为为相相对对于于完完全全图图的的G G 的的补补图图，简简称称G G1 1是是G G 的补图，并记为的补图，并记为G G1 1=。显然，显然，G G与与 互为补图。互为补图。本讲稿第四十二页，共五十六页在在图图的的定定义义中中，强强调调的的是是结结点点集集、边边集集以以及及边边与与结结点点的的关关联联关关系系，既既没

31、没有有涉涉及及到到联联结结两两个个结结点点的的边边的的长长度度、形形状状和和位位置置，也也没没有有给给出出结结点点的的位位置置或或者者规规定定任任何何次次序序。因因此此，对对于于给给定定的的两两个个图图，在在它它们们的的图图形形表表示示中中，即即在在用用小小圆圆圈圈表表示示结结点点和和用用直直线线或或曲曲线线表表示示联联结结两两个个结结点点的的边边的的图图解解中中，看看起起来来很很不不一一样样，但但实实际际上上却却是是表表示示同同一一个个图图。因因而而，引引入入两两图图的的同同构构概概念便是十分必要的了。念便是十分必要的了。本讲稿第四十三页，共五十六页定定义义7.1.107.1.10 给给定定

32、无无向向图图(或或有有向向图图)G G1 1=和和G G2 2=。若若存存在在双双射射f f:V V1 1 V V2 2 ，使使得得对对任任意意v v，u uV V1 1，有有(u u，v v)E E1 1(f f(u u)，f f(v v)E E2 2(或或 E E1 1 )E E2 2),),并并且且(u u，v v)与与(f f(u u)，f f(v v)的的重重数数相同，则称相同，则称G G1 1同构于同构于G G2 2，记为，记为G G1 1G G2 2。显显然然，两两图图的的同同构构是是相相互互的的，即即G G1 1同同构构于于G G2 2，G G2 2同构于同构于G G1 1。由

33、由同同构构的的定定义义可可知知，不不仅仅结结点点之之间间要要具具有有一一一一对对应应关关系系，而而且且要要求求这这种种对对应应关关系系保保持持结结点点间间的的邻邻接接关关系系。对对于于有有向向图图的的同同构构还还要要求求保保持边的方向。持边的方向。本讲稿第四十四页，共五十六页一一般般说说来来，证证明明两两个个图图是是同同构构的的并并非非是是轻轻而易举的事情，往往需要花些气力。而易举的事情，往往需要花些气力。判断图判断图 10.1.13 10.1.13 是否为同构图。是否为同构图。本讲稿第四十五页，共五十六页根据图的同构定义，可以给出图同构的必要条件根据图的同构定义，可以给出图同构的必要条件(1

34、)结点数目相等；结点数目相等；(2)边数相等；边数相等；(3)度数相同的结点数目相等。度数相同的结点数目相等。注：图的同构即存在结点间的一一映射，保持了注：图的同构即存在结点间的一一映射，保持了结点与边之间的关联关系（有向图中还保持边的方向）结点与边之间的关联关系（有向图中还保持边的方向）和边的重数。判断图同构，寻找双射。和边的重数。判断图同构，寻找双射。本讲稿第四十六页，共五十六页返回返回图图 1.1.14本讲稿第四十七页，共五十六页例如图例如图1.1.141.1.14中的中的(a)(a)和和(b)(b)满足上述三个满足上述三个条件，但并不同构。条件，但并不同构。因为在因为在(a a)中度数

35、为中度数为3 3的结点的结点x x与两个度数为与两个度数为1 1的结点邻接，而的结点邻接，而(b b)中度数为中度数为3 3的结点的结点y y仅与一仅与一个度数为个度数为1 1的结点邻接。的结点邻接。说明这仅仅是必要条件而不是充分条件。说明这仅仅是必要条件而不是充分条件。寻找一种简单有效的方法来判定图的同构，寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。至今仍是图论中悬而未决的重要课题。本讲稿第四十八页，共五十六页判断下图是否同构判断下图是否同构本讲稿第四十九页，共五十六页例题：判断下图是否同构例题：判断下图是否同构本讲稿第五十页，共五十六页例题：判断下图是否同构例题：判断下图是否同构本讲稿第五十一页，共五十六页判定彼德森图的同构问题判定彼德森图的同构问题本讲稿第五十二页，共五十六页图 10.1.13返回返回本讲稿第五十三页，共五十六页本讲稿第五十四页，共五十六页两个有向图同构的概念可以类似定义（仅两个有向图同构的概念可以类似定义（仅注意有向边的方向注意有向边的方向)（1 1）画出）画出4 4个顶点个顶点3 3条边的所有可能非同构条边的所有可能非同构的无向简单图。的无向简单图。（2 2）画出）画出3 3个顶点个顶点2 2条边的所有可能非同构条边的所有可能非同构的有向简单图。的有向简单图。本讲稿第五十五页，共五十六页本讲稿第五十六页，共五十六页