《离散数学》第七章 图论-第1节.ppt

1、河南工业大学离散数学课程组河南工业大学离散数学课程组1第第7章章 图图 论论离离 散散 数数 学学河南工业大学河南工业大学信息科学与工程学院信息科学与工程学院河南工业大学离散数学课程组河南工业大学离散数学课程组第2页第第7章章 图图7.1 图的基本概念图的基本概念7.2 路与回路路与回路7.3 图的矩阵表示图的矩阵表示7.4 汉密尔顿图和欧拉图汉密尔顿图和欧拉图 7.5 平面图平面图 7.6 对偶图和着色对偶图和着色 7.7 树树7.8 根树根树河南工业大学离散数学课程组河南工业大学离散数学课程组第3页本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解1图论的图论的基本概念、基本

2、概念、基本方法基本方法基本算法基本算法3图论中的应图论中的应用用 2复杂问题的复杂问题的证明证明 河南工业大学离散数学课程组河南工业大学离散数学课程组第4页1736年瑞士数学家列昂哈德年瑞士数学家列昂哈德欧拉欧拉(leonhard Euler)发表发表了图论的第一篇论文了图论的第一篇论文“哥尼斯堡七桥问题哥尼斯堡七桥问题”。这个问。这个问题是这样的：哥尼斯堡题是这样的：哥尼斯堡(Knigsberg)城市有一条横贯全城市有一条横贯全城的普雷格尔城的普雷格尔(PreGel)河，城的各部分用七座桥连接，河，城的各部分用七座桥连接，每逢假日，城中的居民进行环城的逛游，这样就产生每逢假日，城中的居民进行

3、环城的逛游，这样就产生一个问题，能不能设计一次一个问题，能不能设计一次“逛游逛游”，使得从某地出，使得从某地出发对每座跨河桥走一次，而在遍历了七桥之后却又能发对每座跨河桥走一次，而在遍历了七桥之后却又能回到原地。回到原地。gfabcdeBCAD引例引例1 哥尼斯堡七桥问题哥尼斯堡七桥问题现实问题抽象成图现实问题抽象成图若想完成逛游，需要添加几若想完成逛游，需要添加几座桥，如何建？座桥，如何建？ABCD河南工业大学离散数学课程组河南工业大学离散数学课程组第5页引例引例2 周游世界问题周游世界问题 1859年威廉年威廉汉密尔顿爵士在给他的汉密尔顿爵士在给他的朋友的一封信中，首先谈到关于十二朋友的一

4、封信中，首先谈到关于十二面体的一个数学游戏，能不能在图中面体的一个数学游戏，能不能在图中找到一条回路，使它含有这个图的全找到一条回路，使它含有这个图的全部结点？部结点？他把结点看作是一座城市，联结两个他把结点看作是一座城市，联结两个结点的边看成是交通线，于是它的问结点的边看成是交通线，于是它的问题是题是能不能找到旅行路线，沿着交通能不能找到旅行路线，沿着交通线经过每一个城市恰好一次，再回到线经过每一个城市恰好一次，再回到原来的出发地原来的出发地？他把这个问题称为周？他把这个问题称为周游世界问题。游世界问题。河南工业大学离散数学课程组河南工业大学离散数学课程组第6页引例引例3 四色问题四色问题(

5、Four Color Problem)1852,Francis Guthrie（格色里）格色里）,注意到注意到英格兰英格兰地图可以用地图可以用4种颜色染色种颜色染色,使得相邻面使得相邻面(有一段公共有一段公共边界边界,不只是有一个公共点不只是有一个公共点)有不同颜色有不同颜色;他问其弟他问其弟 Frederick 是否是否任意任意地图都有此性质地图都有此性质?河南工业大学离散数学课程组河南工业大学离散数学课程组第7页韦尔奇韦尔奇.鲍威尔法鲍威尔法n v1v1v2v2v3v3v4v4v5v5v6v6v7v7v8v8河南工业大学离散数学课程组河南工业大学离散数学课程组第8页知识点：知识点：n图的基

6、本概念图的基本概念n点与边的关联、点（边）相邻点与边的关联、点（边）相邻n完全图、补图，子图、生成子图完全图、补图，子图、生成子图n点度数点度数n握手定理握手定理n图的同构图的同构7-1 图的基本概念图的基本概念河南工业大学离散数学课程组河南工业大学离散数学课程组第9页一、图的基本概念一、图的基本概念n现实世界中许多现象能用某种图形表示现实世界中许多现象能用某种图形表示,这种图形这种图形是由一些点和一些连接两点间的连线所组成。是由一些点和一些连接两点间的连线所组成。n例：例：A、B、C、D四个队举行篮球比赛，四个队举行篮球比赛，为了表示为了表示个队之间比赛的情况，个队之间比赛的情况，我们作出下

7、图。我们作出下图。在图中在图中个小圆圈分别表示这个篮球队，个小圆圈分别表示这个篮球队，称之为结点。称之为结点。如果两队进行过比赛，如果两队进行过比赛，则在表示该队的两个结点则在表示该队的两个结点之间用一条线连接起来，之间用一条线连接起来，称之为边。称之为边。这样利用一这样利用一个图形使各队之间的比赛情况一目了然。个图形使各队之间的比赛情况一目了然。ABDC河南工业大学离散数学课程组河南工业大学离散数学课程组第10页一、图的基本概念一、图的基本概念n定义定义7-1.1 图的定义图的定义：一个图一个图G是一个二元组是一个二元组，其中，其中nV(G)=v1,v2,vn，是一个有限是一个有限非空非空集

8、合集合，vi称为结点，称为结点，V(G)称为结点集合，简记为称为结点集合，简记为V。nE(G(=e1,e2,em，是一个有限集合，是一个有限集合，ei称为称为边边，ei用结点的用结点的偶对偶对表示，表示，E(G)称为边集合，简称为边集合，简记为记为E。河南工业大学离散数学课程组河南工业大学离散数学课程组第11页二、二、图的表示图的表示 n对于一个图对于一个图G，如果将其记为，如果将其记为G=，并写出，并写出V和和E的集合表示，这称为的集合表示，这称为图的集合表示图的集合表示。n而为了描述简便起见，在一般情况下，往往只画出而为了描述简便起见，在一般情况下，往往只画出它的图形：用小圆圈表示它的图形

9、：用小圆圈表示V中的结点，中的结点，n边边：用由：用由u指向指向v的有向线段或曲线表示，称的有向线段或曲线表示，称为有向边，为有向边，(u,v)：无向线段或曲线表示，称为无：无向线段或曲线表示，称为无向边，这称为向边，这称为图的图形表示。图的图形表示。河南工业大学离散数学课程组河南工业大学离散数学课程组第12页例例7-1.1 设图设图G=，这里，这里V=v1,v2,v3,v4,v5，E=e1,e2,e3,e4,e5,e6，其中，其中e1=(v1,v2)，e2=，e3=(v1,v4)，e4=(v2,v3)，e5=，e6=(v3,v3)。试画出图试画出图G的图形。的图形。解：解：G的图形如下图所示

10、。的图形如下图所示。nG中的中的e1、e3、e4、e6是无向边，是无向边，e2、e5是有向边。是有向边。v v3 3e e1 1e e2 2e e3 3e e5 5v v2 2v v1 1v v4 4e e4 4v v5 5e e6 6河南工业大学离散数学课程组河南工业大学离散数学课程组第13页例例7-1.2n设图设图G=的图形如下图所示，试写出的图形如下图所示，试写出G的的集合表示。集合表示。1 12 23 34 45 5n解解 图图G的集合表示为的集合表示为G=1,2,3,4,5，(1,4)，(1,5)，(2,3)，。河南工业大学离散数学课程组河南工业大学离散数学课程组第14页两种描述方法

11、的优缺点两种描述方法的优缺点n用用集合集合描述图的优点是描述图的优点是精确精确，但，但抽象不易理解；抽象不易理解；n用用图形图形表示图的优点是表示图的优点是形象直观形象直观，但当图中的，但当图中的结点和边的数目较大时，使用这种方法是很结点和边的数目较大时，使用这种方法是很不不方便方便的，甚至是不可能的。的，甚至是不可能的。河南工业大学离散数学课程组河南工业大学离散数学课程组第15页三、关于图的一些术语三、关于图的一些术语n若边若边e与无序结点对与无序结点对(vi,vj)对应，对应，则称则称e为无向边，为无向边，vi，vj为为e的的端点端点。n若边若边e与有序结点对与有序结点对 对应，对应，则称

12、则称e为有向边，为有向边，vi称作称作e的的起始结点，起始结点，vj称作称作e的的终终止结点，但统称为止结点，但统称为e的端点。的端点。nek与与vi或或ek与与vj是彼此相是彼此相关联的关联的。n邻接点邻接点：关联于同一边的结点称为：关联于同一边的结点称为邻接点邻接点。邻接边邻接边：关联于同一结点的边称为：关联于同一结点的边称为邻接边邻接边。关联于同一结点的边称为关联于同一结点的边称为环环或或自回路自回路。n注意：环的方向没有意义，可以看作无向边也注意：环的方向没有意义，可以看作无向边也可看作有向边。可看作有向边。无论在无向图中还是在有向图中，无边关联的结点无论在无向图中还是在有向图中，无边

13、关联的结点均称均称孤立点孤立点。v v3 3e e1 1e e2 2e e3 3e e5 5v v2 2v v1 1v v4 4e e4 4v v5 5e e6 6河南工业大学离散数学课程组河南工业大学离散数学课程组第16页四、图的分类四、图的分类 n边方向边方向无向图无向图有向图有向图混合图混合图图图多重图多重图非多重图非多重图简单图简单图n平行边平行边河南工业大学离散数学课程组河南工业大学离散数学课程组第17页n每每一条边都是一条边都是无向边无向边的图称作的图称作无向图无向图。n每每一条边都是一条边都是有向边有向边的图称作的图称作有向图有向图。n若图中既有无向边也有有向边，称为若图中既有无

14、向边也有有向边，称为混合图混合图。例例7-1.3：判断下面图是无向图、有向图或混合图：判断下面图是无向图、有向图或混合图分析：分析：判断无向图、有向图和混合图，仅看边有无方向。判断无向图、有向图和混合图，仅看边有无方向。V6V5V4V3V2V1V7V8V1V2V3V1V2V3有向图有向图无向图无向图混合图混合图河南工业大学离散数学课程组河南工业大学离散数学课程组第18页n定义定义7-1.2 含有平行边的图称为含有平行边的图称为多重图。多重图。n不允许有环和平行边的图称为不允许有环和平行边的图称为简单图简单图。n注意：不是多重图，不一定是简单图。注意：不是多重图，不一定是简单图。连接于同一对结点

15、间方向相同的多条边称为是连接于同一对结点间方向相同的多条边称为是平行边平行边。多重图多重图简单图简单图非多重图，非多重图，非简单图非简单图平行边平行边河南工业大学离散数学课程组河南工业大学离散数学课程组第19页n没有任何边的图称为没有任何边的图称为零图零图；n只有一个点的图称为只有一个点的图称为平凡图平凡图；n含有含有n个结点，个结点，m条边的图，称为条边的图，称为(n,m)图。图。(a)4阶零图阶零图 N4(b)平凡图平凡图特殊图特殊图V1V2V3(c)(3,5)图图河南工业大学离散数学课程组河南工业大学离散数学课程组第20页五、完全图五、完全图定义定义7-1.4 设设G为为n阶无向阶无向简

16、单图简单图，若，若G中每个结点均中每个结点均与其余的与其余的n-1个结点相邻，则称个结点相邻，则称G为为n阶阶无向完全图无向完全图，简称简称n阶完全图，记做阶完全图，记做Kn(n1)。设设D为为n阶有向简单图，若阶有向简单图，若D中中每个结点都邻接到其余每个结点都邻接到其余的的n-1个结点个结点，又邻接于其余的又邻接于其余的n-1个结点个结点，则称，则称D是是n阶阶有向完全图有向完全图。设设D为为n阶有向简单图，若阶有向简单图，若D的基图为的基图为n阶无向完全图阶无向完全图Kn，则称，则称D是是n阶竞赛图阶竞赛图。基图：基图：将有向图各有向边去掉方向后的无向图称为原将有向图各有向边去掉方向后的

17、无向图称为原来图的来图的基图基图。河南工业大学离散数学课程组河南工业大学离散数学课程组第21页例例7-1.4 7-1.4 下图分别给出了一个结点、二个结点、三下图分别给出了一个结点、二个结点、三个结点、四个结点和五个结点的无向完全图。个结点、四个结点和五个结点的无向完全图。完全图例完全图例河南工业大学离散数学课程组河南工业大学离散数学课程组第22页定理定理7-1.1 n阶无向完全图，阶无向完全图，n阶有向完全图，阶有向完全图，n阶有阶有向竞赛图的边数分别为向竞赛图的边数分别为 n(n-1)/2，n(n-1)，n(n-1)/2完全图边数完全图边数河南工业大学离散数学课程组河南工业大学离散数学课程

18、组第23页六、结点的度数六、结点的度数n定义定义7-1.5：在图：在图G=，viE，与，与vi关联的边的关联的边的条数称为该结点的度数，记为条数称为该结点的度数，记为deg(vi)。n（约定：（约定：每个环在其对应结点度数上增加每个环在其对应结点度数上增加2）n图图G最大度数记为最大度数记为(G)，最小度数记为最小度数记为(G)。n定义定义7-1.6：在有向图：在有向图G=中，中，v V,n以以v为起始结点的边的条数称为该点的出度，记作为起始结点的边的条数称为该点的出度，记作deg+(v);n以以v为终止结点的边的条数称为该点的入度，记作为终止结点的边的条数称为该点的入度，记作deg-(v)。

19、n每个环在其对应结点的出度增加每个环在其对应结点的出度增加1，给入度增加，给入度增加1.n显然有显然有deg(v)=deg+(v)+deg-(v)河南工业大学离散数学课程组河南工业大学离散数学课程组第24页求出下图的最大度和最小度，求出图中每个结点求出下图的最大度和最小度，求出图中每个结点的出，入度。的出，入度。v1v2v3v4deg+(v)deg-(v)deg(v)v1224v2022v3415v41231deg()nivi=14(G)=5，(G)=2例例7-1.7河南工业大学离散数学课程组河南工业大学离散数学课程组第25页 n度数列度数列 设设V=v1,v2,v3,vn是图是图G的结点集，

20、称的结点集，称 (deg(v1),deg(v2),deg(v3),deg(vn)为为G的度数列。的度数列。度数列为：度数列为：(4,4,2,1,3)1deg()nivi=14 河南工业大学离散数学课程组河南工业大学离散数学课程组第26页握手定理握手定理定理定理7-1.2 设设G=为任意图为任意图(无向的或有向无向的或有向的的)，V=v1,v2,vn，|E|=m，则，则 所有结点的度数之和所有结点的度数之和=边数的两倍边数的两倍=偶数偶数证明：证明：G中每条边中每条边(包括环包括环)均有两个端点，为均有两个端点，为2个端点的度个端点的度数各贡献数各贡献1度，所以在计算度，所以在计算G中所有结点度

21、数之和时，中所有结点度数之和时，每条边均提供每条边均提供2度，当然，度，当然，m条边，共提供条边，共提供2m度。度。=2|E|=2m河南工业大学离散数学课程组河南工业大学离散数学课程组第27页 n 这个结果是图论的第一个定理，它是由欧拉这个结果是图论的第一个定理，它是由欧拉于于1736年最先给出的。欧拉曾对此定理给出了年最先给出的。欧拉曾对此定理给出了这样一个形象论断：如果许多人在见面时握了这样一个形象论断：如果许多人在见面时握了手，两只手握在一起，握过手的总次数为偶数。手，两只手握在一起，握过手的总次数为偶数。故此定理称为图论的基本定理或握手定理。故此定理称为图论的基本定理或握手定理。今后常

22、称今后常称度数为奇数的结点度数为奇数的结点为为奇度数结点奇度数结点(Odd Degree Point)，度数为偶数的结点度数为偶数的结点为为偶度数结点偶度数结点(Even Degree Point)。河南工业大学离散数学课程组河南工业大学离散数学课程组第28页例：若图例：若图G有有n个结点，个结点，(n+1)条边，则条边，则G中至少有一中至少有一个结点的度数个结点的度数 3。n证明：证明：设图设图G中有中有n个结点分别为个结点分别为v1,v2,vn,则由握则由握手定理：手定理：=2e=2(n+1)而结点的平均度数而结点的平均度数=2(n+1)/n=2+2/n 2 所以，结点中至少有一个结点的度

23、数所以，结点中至少有一个结点的度数 3。河南工业大学离散数学课程组河南工业大学离散数学课程组第29页握手定理的推论握手定理的推论定理定理7-1.3 任何图任何图(无向的或有向的无向的或有向的)中，奇度数结点的中，奇度数结点的个数是偶数。个数是偶数。证明：证明：设设G=为任意一图，令为任意一图，令 V1是偶度数结点的集合，是偶度数结点的集合，V2是奇度数结点的集合，是奇度数结点的集合，V1V2=V，V1V2=，由由握手定理握手定理可知可知 由于由于2m，均为偶数，所以均为偶数，所以 为偶数，但为偶数，但因因V2中中deg(v)为奇数，所以为奇数，所以V2中元素的个数必为偶数，中元素的个数必为偶数

24、，即奇度数结点的个数是偶数。即奇度数结点的个数是偶数。1deg()v Vvi2deg()v Vvi2m=+1deg()v Vvi2deg()v Vvi河南工业大学离散数学课程组河南工业大学离散数学课程组第30页握手定理的推论握手定理的推论定理定理7-1.4 任何任何有向图中有向图中，所有结点的入度之和等，所有结点的入度之和等于所有结点的出度之和。于所有结点的出度之和。证明：证明：因为每一条边必给结点的入度之和增加因为每一条边必给结点的入度之和增加1，给，给结点的出度之和增加结点的出度之和增加1，所以，有向图中所有，所以，有向图中所有结点的入度之和等于边数，所有结点的出度之结点的入度之和等于边数

25、，所有结点的出度之和等于边数。因此，和等于边数。因此，所有结点的入度之和等于所有结点的入度之和等于所有结点的出度之和。所有结点的出度之和。河南工业大学离散数学课程组河南工业大学离散数学课程组第31页握手定理的应用握手定理的应用V=v1,v2,vn为无向图为无向图G的结点集，称的结点集，称deg(v1),deg(v2),deg(vn)为为G的的度数列。度数列。下面整数列是否可图化？下面整数列是否可图化？(1)(5,3,3,2,1);(2)(2,2,3,1,5)。解：解：(1)deg(i)=偶数，偶数，所以所以(1)可图化，或奇数度结点可图化，或奇数度结点为偶数，则其图化解可有多个。为偶数，则其图

26、化解可有多个。(2)中有中有3个奇度结点个奇度结点,由握手定理由握手定理,图图G中奇度结点中奇度结点必为偶数个必为偶数个,所以所以(2)不可图化。不可图化。下面整数列是否可下面整数列是否可简单图简单图化？化？(2,3,2,4,6,5);解解:是阶为是阶为6的简单图的简单图,(G)5,所以不可简单图化。所以不可简单图化。河南工业大学离散数学课程组河南工业大学离散数学课程组第32页握手定理的应用握手定理的应用练习题练习题1：设简单连通无向图设简单连通无向图G有有12条边，条边，G中有中有2个个1度结点度结点，2个个2度结点度结点，3个个4度结点度结点，其余结点度数，其余结点度数为为3求求G中有多少

27、个结点。中有多少个结点。n解：设图解：设图G有有x个结点，有握手定理个结点，有握手定理n 21+22+34+3(x-2-2-3)122n x9n 图图G有有9个结点。个结点。河南工业大学离散数学课程组河南工业大学离散数学课程组第33页证明证明：方法一：穷举法方法一：穷举法n 设设G有有x个个5度结点，度结点，n则则G有有9-x个个6度结点，由握手定理推论可知：度结点，由握手定理推论可知：nx只能取只能取 0，2，4，6，8；n9-x只能取只能取 9，7，5，3，1。n于是于是(x,9-x)为为(0,9)，(2,7)，(4,5)时均至少有时均至少有5个个6度结点，而在度结点，而在(6,3)，(8

28、,1)时满足至少有时满足至少有6个个5度结度结点。点。练习题练习题2：9阶图阶图G中，每个结点的度数不是中，每个结点的度数不是5就是就是6，证，证明明G中至少有中至少有5个个6度结点或至少有度结点或至少有6个个5度结点。度结点。河南工业大学离散数学课程组河南工业大学离散数学课程组第34页练习题练习题2：9阶图阶图G中，每个结点的度数不是中，每个结点的度数不是5就是就是6，证明证明G中至少有中至少有5个个6度结点或至少有度结点或至少有6个个5度结点。度结点。证明：证明：n方法二：反证法方法二：反证法nG至多有至多有4个个6度结点且至多有度结点且至多有5个个5度结点。由度结点。由握手定理推论可知：

29、握手定理推论可知：nG至多有至多有4个个6度结点且至多有度结点且至多有4个个5度结点。这度结点。这样样G至多有至多有8个结点，与个结点，与G为为9阶图矛盾。阶图矛盾。河南工业大学离散数学课程组河南工业大学离散数学课程组第35页v3v2v4v1v5v6删除删除v1v3v2v4v1v5v6删除边删除边(v4,v6)n(1)删除结点删除结点v，是将是将v以及与以及与v关联的边都删去。关联的边都删去。(2)删除边删除边e，是仅将边是仅将边e删去。删去。删除图中的点、边删除图中的点、边v3v2v4v1v5v6河南工业大学离散数学课程组河南工业大学离散数学课程组第36页七、子图、母图、生成子图、补图七、子

30、图、母图、生成子图、补图 定义定义7-1.7 设设G，H是图，若是图，若G，H满足满足n(1)V(H)V(G)且且E(H)E(G),称称H是是G的的子图子图，G是是H的的母图母图。n(2)若若H是是G的子图，并且的子图，并且V(H)V(G)，则称则称H是是G的的生成子图生成子图。abcdd1a1b1c1abcdd1a1b1c1abcda1b1（a)母图母图(c)子图子图(b)子图子图注意，注意，孤孤立结点一立结点一定不要漏定不要漏了，否则了，否则结点集就结点集就不同。不同。(c)生成子图生成子图河南工业大学离散数学课程组河南工业大学离散数学课程组第37页注意：注意：孤立结点一定不要漏了，孤立结

31、点一定不要漏了，否则结点集就不同。否则结点集就不同。补图补图(a)原图原图(b)补图补图定义定义7-1.8 图图G相对于完全图的补图相对于完全图的补图：设：设G为具有为具有n个结点的图，从完全图个结点的图，从完全图Kn中删去中删去G中的所有边中的所有边而得到的图，称为而得到的图，称为G的补图，表示为的补图，表示为 。例例7-1.5，求图，求图(a)的补图的补图图图G与其补与其补图图G具有相同具有相同的结点集，其边的结点集，其边集不相交，构成集不相交，构成相应完全图边集相应完全图边集的划分。的划分。河南工业大学离散数学课程组河南工业大学离散数学课程组第38页 n定义定义7-1.9 设设G=是图是

32、图G=的的子图子图，从从G中删去中删去G的边，且的边，且删去孤立结点后得到的删去孤立结点后得到的图图G(即即G中仅包含中仅包含G的边所关联的结点），的边所关联的结点），则称则称G是子图是子图G的相对于图的相对于图G的的补图补图。n例例7-1.6：子图相对于子图相对于母图的补图母图的补图母图母图abcdd1a1b1c1abcdd1a1b1c1abcda1b1子图子图dcd1a1b1c1b河南工业大学离散数学课程组河南工业大学离散数学课程组第39页八、图的同构八、图的同构(isomorphism)n图是表达事物之间关系的工具，因此，图的最图是表达事物之间关系的工具，因此，图的最本质的内容是结点和边

33、的关联关系。而在实际本质的内容是结点和边的关联关系。而在实际画图时，由于结点的位置不同，边的长短曲直画图时，由于结点的位置不同，边的长短曲直不同，同一事物间的关系可能画出不同形状的不同，同一事物间的关系可能画出不同形状的图来。图来。n形象地说，若图的结点可以任意挪动位置，而形象地说，若图的结点可以任意挪动位置，而边是完全弹性的，只要在不拉断的条件下，这边是完全弹性的，只要在不拉断的条件下，这个图可以变形为另一个图，那么这两个图是一个图可以变形为另一个图，那么这两个图是一样的，称为同构。可以用几种不同形状的图形样的，称为同构。可以用几种不同形状的图形表示同一个图。表示同一个图。河南工业大学离散数

34、学课程组河南工业大学离散数学课程组第40页图的同构例图的同构例 abcdd1a1b1c1abcdd1a1b1c1河南工业大学离散数学课程组河南工业大学离散数学课程组第41页定义定义7-1.9 图的同构图的同构(isomorphism)n图图G=和和G=是同构的。是同构的。n若存在若存在V(G)到到V(G)的双射（一一对应映射）的双射（一一对应映射）g：vivi ，且且e=(vi,vj)(或或)是是G的一条边，的一条边，当且仅当当且仅当e=(g(vi),g(vj)(或或)是是G 的一的一条边，则称条边，则称图图G=和和G =是同构的。是同构的。记做记做G G。n定义的实质定义的实质：n两个图的结

35、点和边分别存在着一一对应，两个图的结点和边分别存在着一一对应，n且关联关系也必须保持对应关系。且关联关系也必须保持对应关系。n对有向图还保持着边方向关系的对应。对有向图还保持着边方向关系的对应。n可以把同构的图看成是一个图。可以把同构的图看成是一个图。河南工业大学离散数学课程组河南工业大学离散数学课程组第42页已知已知V1=v1,v2,v3,v4,v5,V2=a,b,c,d,e，试证明图中，试证明图中，G1 G2分析分析 证明两个图同构，关键是找到证明两个图同构，关键是找到 满足要求的结点集之间的双射函数。满足要求的结点集之间的双射函数。现在还没有好的办法，只有凭经验去试。现在还没有好的办法，

36、只有凭经验去试。证明：证明：n构造结点之间的映射构造结点之间的映射g：V1V2：ng(v1)=a；g(v2)=b；g(v3)=d；g(v4)=e；g(v5)=cn且在该映射下：且在该映射下：(v1,v2)(a,b)(v1,v5)(a,c)(v2,v3)(b,d)(v3,v4)(d,e)(v5,v4)(c,e)n显然显然G1 G2。图的同构例图的同构例adcbeG1G2v4v5v1v2v3v3v4河南工业大学离散数学课程组河南工业大学离散数学课程组第43页a d c b 无无 向向 图图 b(b)a(a)c(c)d(d)例：例：河南工业大学离散数学课程组河南工业大学离散数学课程组第44页a c

37、d e 无无 向向 图图 b f g h i j 例：例：1(a)3(c)4(h)6(e)2(b)5(f)8(g)10(i)9(d)7(j)河南工业大学离散数学课程组河南工业大学离散数学课程组第45页有向图有向图例：例：abcde2(a)1(b)3(d)4(c)5(e)河南工业大学离散数学课程组河南工业大学离散数学课程组第46页图之间的同构关系是等价关系图之间的同构关系是等价关系n图之间的同构关系图之间的同构关系 可看成全体图集合上的二元可看成全体图集合上的二元关系关系n该二元关系具有该二元关系具有自反性自反性，对称性对称性和和传递性传递性，因，因而是而是等价关系等价关系。n在这个等价关系的每

38、一等价类中均取一个图作在这个等价关系的每一等价类中均取一个图作为一个代表，凡与它同构的图，在同构的意义为一个代表，凡与它同构的图，在同构的意义之下都可以看成一个图。之下都可以看成一个图。河南工业大学离散数学课程组河南工业大学离散数学课程组第47页两图同构的必要条件：两图同构的必要条件：可用于判定不同构可用于判定不同构n若若G1、G2同构，则同构，则 n1.结点数目相同，结点数目相同，n2.边数相同，边数相同，n3.度数相同的结点数目相同。度数相同的结点数目相同。n需要注意的是：需要注意的是：n破坏这些必要条件的任何一个，两个图就不会同破坏这些必要条件的任何一个，两个图就不会同构，构，n不要将两

39、个图同构的必要条件当成充分条件。但不要将两个图同构的必要条件当成充分条件。但以上列出的条件都满足，两个图也不一定同构。以上列出的条件都满足，两个图也不一定同构。n目前，还没有找到判断两个图是否同构的好的算法，目前，还没有找到判断两个图是否同构的好的算法，还只能根据定义看是否能找到满足条件的双射函数，还只能根据定义看是否能找到满足条件的双射函数，显然这是困难的。显然这是困难的。河南工业大学离散数学课程组河南工业大学离散数学课程组第48页xy判断下面的图是否同构。判断下面的图是否同构。n分析分析 n 证明两个图不同构，通常用反证法。证明两个图不同构，通常用反证法。n证明证明 n假设假设G G，双射

40、函数为，双射函数为f。由定义，。由定义，v与与f(v)的度的度数一定相同，因此有数一定相同，因此有f(x)=y。G中中x与两个度数为与两个度数为1的结点邻接，而的结点邻接，而G中中y与一个度数为与一个度数为1的结点邻接，的结点邻接，矛盾。矛盾。GGww河南工业大学离散数学课程组河南工业大学离散数学课程组第49页生成子图生成子图试问试问K4的所有非同构的的所有非同构的i(i=0，1，2，4，5，6)条边的生成子图各有几个？条边的生成子图各有几个？m=3m=4m=5m=6m=0m=1m=2河南工业大学离散数学课程组河南工业大学离散数学课程组第50页小结小结n主要内容：主要内容：n1、无向图与有向图、无向图与有向图n2、简单图与多重图、简单图与多重图n3、结点的度数与握手定理、结点的度数与握手定理n4、图的同构、图的同构n5、子图与补图、子图与补图n理解：理解：n掌握图的同构概念。掌握图的同构概念。n重点：重点：n熟练掌握握手定理及其应用熟练掌握握手定理及其应用以及生成子图的以及生成子图的概念。概念。