图的基本概念无向图及有向图精选PPT.ppt

《图的基本概念无向图及有向图精选PPT.ppt》由会员分享，可在线阅读，更多相关《图的基本概念无向图及有向图精选PPT.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于图的基本概念无向图及有向图第1页，讲稿共61张，创作于星期日 图论的起源图论的起源图论是组合数学的一图论是组合数学的一个分支个分支,它起源于它起源于17361736年欧拉的第一篇年欧拉的第一篇关于图论的论文，这关于图论的论文，这篇论文解决了著名的篇论文解决了著名的 “哥尼斯堡七桥问题哥尼斯堡七桥问题”，从而使欧拉成，从而使欧拉成为图论的创始人。为图论的创始人。第2页，讲稿共61张，创作于星期日哥尼斯堡七桥问题尼斯堡七桥问题解决方式解决方式莱昂哈德莱昂哈德欧拉欧拉（Leonhard EulerLeonhard Euler）在）在17351735年圆满地解决年圆满地解决了这一问题，证明这种方法

2、并不存在，也顺带解决了了这一问题，证明这种方法并不存在，也顺带解决了一一笔画问题笔画问题。他在圣彼得堡科学院发表了图论史上第一篇重。他在圣彼得堡科学院发表了图论史上第一篇重要文献。欧拉把实际的抽象问题简化为平面上的点与线组合，要文献。欧拉把实际的抽象问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数。点出发后最后再回到这点，则这一点的线数必须是偶数。zh.wikipedia.org/wiki/File:Konigsberg_bridges.png 第4页，讲稿共6

3、1张，创作于星期日5图论的起源欧拉最后给出任意一种河欧拉最后给出任意一种河桥图能否全部走桥图能否全部走一次的一次的判定法则判定法则。如果通。如果通奇数座奇数座桥的地方桥的地方不止不止两个两个，那么满足要求的路线便不存在了。如果，那么满足要求的路线便不存在了。如果只有只有两个地方两个地方通奇数座桥，则可从其中任何通奇数座桥，则可从其中任何一地出发找到所要求的路线。若一地出发找到所要求的路线。若没有一个地方没有一个地方通奇数座桥，则从任何一地出发，所求的路通奇数座桥，则从任何一地出发，所求的路线都能实现，他还说明了怎样快速找到所要线都能实现，他还说明了怎样快速找到所要求的路线。求的路线。不少数学家

4、都尝试去解析这个事例。而这些不少数学家都尝试去解析这个事例。而这些解析，最后发展成为了数学中的解析，最后发展成为了数学中的图论图论。第5页，讲稿共61张，创作于星期日 欧 拉 图定义定义 一个图一个图,如果能够从一点出发如果能够从一点出发,经过每条边一次且仅一次再回到经过每条边一次且仅一次再回到起点起点,则称为则称为欧拉图欧拉图 欧拉在论文中给出并证明了判断欧欧拉在论文中给出并证明了判断欧拉图的充分必要条件定理拉图的充分必要条件定理,并证明了七并证明了七桥图不是欧拉图。桥图不是欧拉图。第6页，讲稿共61张，创作于星期日 从这个问题可以看出：图图：图用点代表各个事物图用点代表各个事物,用边代表用

5、边代表各个事物间的二元关系。各个事物间的二元关系。所以，图是研究集合上的二元关所以，图是研究集合上的二元关系的工具，是建立数学模型的一个系的工具，是建立数学模型的一个重要手段。重要手段。第7页，讲稿共61张，创作于星期日 2、一百多年以后 “七桥七桥”问题以后，图论的研究停滞了一百问题以后，图论的研究停滞了一百多年，直到多年，直到18471847年，基尔霍夫用年，基尔霍夫用“树树”图解图解决了电路理论中的求解联立方程的问题，十决了电路理论中的求解联立方程的问题，十年后凯莱用年后凯莱用 “树树”图计算有机化学中的问图计算有机化学中的问题。在这一时期流行着两个著名的图论问题。在这一时期流行着两个著

6、名的图论问题：哈密尔顿回路问题和题：哈密尔顿回路问题和 “四色猜想四色猜想”问问题。题。第8页，讲稿共61张，创作于星期日3.哈密尔顿回路问题 18561856年年,英国数学家哈密尔顿设计了一英国数学家哈密尔顿设计了一个周游世界的游戏，他在一个正十二面个周游世界的游戏，他在一个正十二面体的二十个顶点上标上二十个著名城市体的二十个顶点上标上二十个著名城市的名字，要求游戏者从一个城市出发，的名字，要求游戏者从一个城市出发，经过每一个城市一次且仅一次，然后回经过每一个城市一次且仅一次，然后回到出发点。到出发点。第9页，讲稿共61张，创作于星期日哈密尔顿回路图 此路线称为：此路线称为：哈密尔顿回路哈密

7、尔顿回路，而此图称为：而此图称为：哈密尔顿图哈密尔顿图。第10页，讲稿共61张，创作于星期日4、“四 色 猜 想”问 题 人们在长期为地图人们在长期为地图(平面图平面图)上色时发现，上色时发现，最少只要四种颜色，就能使得有相邻最少只要四种颜色，就能使得有相邻国界的国家涂上不同的颜色国界的国家涂上不同的颜色 四色猜想的证明一直没有解决，直四色猜想的证明一直没有解决，直到一百多年后，在计算机出现以后，于到一百多年后，在计算机出现以后，于19761976年用计算机算了年用计算机算了12001200多小时，才多小时，才证明了四色猜想问题证明了四色猜想问题。第11页，讲稿共61张，创作于星期日 5、又过

8、了半个世纪 四色猜想问题出现后，图论的研究又四色猜想问题出现后，图论的研究又停滞了半个世纪，直到停滞了半个世纪，直到19201920年年科尼格科尼格写写了许多关于图论方面的论文，并于了许多关于图论方面的论文，并于19361936年发表了第一本关于图论的书。此后年发表了第一本关于图论的书。此后图论从理论上到应用上都有了很大发图论从理论上到应用上都有了很大发展。特别是计算机的出现使图论得到展。特别是计算机的出现使图论得到飞跃的发展。飞跃的发展。第12页，讲稿共61张，创作于星期日 学好图论十分重要 图论是组合数学的一个分支，与其它数学分支如图论是组合数学的一个分支，与其它数学分支如群论、矩阵论、集

9、合论、概率论、拓扑学、数值群论、矩阵论、集合论、概率论、拓扑学、数值分析等有着密切的联系分析等有着密切的联系 。图论给含有二元关系的系统提供了数学模型，因图论给含有二元关系的系统提供了数学模型，因而在许多领域里都具有越来越重要的地位，并且而在许多领域里都具有越来越重要的地位，并且在物理、化学、信息学、运筹学等各方面都取得在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。了丰硕的成果。从二十世际从二十世际50 50 年代以来，由于计算机的迅速发年代以来，由于计算机的迅速发展，有力地推动了图论的发展，使得图论成为数展，有力地推动了图论的发展，使得图论成为数学领域里发展最快的分支之一。学领域里

10、发展最快的分支之一。第13页，讲稿共61张，创作于星期日14第第7 7章章 图的概念图的概念本章学习：本章学习：1.1.无向无向图及有向图图及有向图2.2.通路、回路、图的连通性通路、回路、图的连通性3.3.图的矩阵表示图的矩阵表示4.4.最短路径及关键路径最短路径及关键路径 第14页，讲稿共61张，创作于星期日15今日内容无向图及有向图无向图及有向图图的一些相关概念图的一些相关概念度度握手定理握手定理子图相关概念子图相关概念图同构图同构第15页，讲稿共61张，创作于星期日16预备知识有序积有序积:AB=|xAyB:AB=|xAyB有序对有序对:无序积无序积:A&B=(x,y)|xAyB:A&

11、B=(x,y)|xAyB无序对无序对:(x,y)=(y,x):(x,y)=(y,x)多重集多重集:a,a,a,b,b,ca,b,c:a,a,a,b,b,ca,b,c重复度重复度:a:a的重复度为的重复度为3,b3,b的为的为2,c2,c的为的为1 1第16页，讲稿共61张，创作于星期日171 1、无序积、无序积：A&BA&B设设A A、B B为两集合，称为两集合，称a,b|aAbBa,b|aAbB为为A A与与B B 的无序积，记作的无序积，记作A&BA&B。为方便起见，将无序对为方便起见，将无序对a,ba,b记作记作 (a,b)(a,b)。(a,b)(a,b)(b,a)(b,a)例：例：设设

12、A=a,b,B=c,d,A=a,b,B=c,d,则则A&BA&B？A&AA&A？A&B=(a,c),(a,d),(b,c),(b,d)A&B=(a,c),(a,d),(b,c),(b,d)A&A=(a,a),(a,b),(b,b)A&A=(a,a),(a,b),(b,b)第17页，讲稿共61张，创作于星期日182 2、无向图、无向图一个一个无向图无向图G G是一个二元组是一个二元组,即即G=,G=,其中其中:.V V是是一一个个非非空空集集合合,称称为为G G的的顶顶点点集集,V,V中中元元素素称称为为顶点顶点或或结点结点;.E E是是无无序序积积V&VV&V的的一一个个多多重重子子集集,称称

13、E E为为G G的的边边集集,E,E中元素称为中元素称为无向边无向边或简称或简称边边。用用小小圆圆圈圈表表示示V V中中顶顶点点,若若(a,b)E,(a,b)E,就就在在a,ba,b之之间间连连线线段段表表示示边边(a,b),(a,b),其其中中顶顶点点的的位位置置、连连线线的的曲曲直直及及是是否否相相交交都都无关紧要。无关紧要。第18页，讲稿共61张，创作于星期日无向图示例无向图示例 给定无向图G，其中 Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5).第19页，讲稿共61张，创作于星期日203

14、 3、有向图、有向图 一个一个有向图有向图D D是一个二元组是一个二元组,即即D=,D=,其中：其中：.V V同无向图中的顶点集同无向图中的顶点集;.E E是笛卡儿积的是笛卡儿积的多重子集多重子集,其元素称为其元素称为有向边有向边,也简也简称称边边.第20页，讲稿共61张，创作于星期日有向图示例有向图示例 给定有向图D=，其中 Va,b,c,d，E,。第21页，讲稿共61张，创作于星期日图的一些概念和规定图的一些概念和规定G G表示无向图，但有时用表示无向图，但有时用G G泛指图泛指图(无向的或有向的无向的或有向的)。D D只能表示有向图。只能表示有向图。V(G)V(G)，E(G)E(G)分别

15、表示分别表示G G的顶点集和边集。的顶点集和边集。若若|V(G)|V(G)|n n，则称则称G G为为n n阶图阶图。若若|V(G)|V(G)|与与|E(G)|E(G)|均为有限数，则称均为有限数，则称G G为为有限图有限图。若边集若边集E(G)E(G)，则称则称G G为为零图零图，此时，又若，此时，又若G G为为n n阶图，则阶图，则称称G G为为n n阶零图阶零图，记作，记作N Nn n，特别地，称特别地，称N N1 1为为平凡图平凡图 在图的定义中规定顶点集在图的定义中规定顶点集V V为非空集，但在图的运算中可能产为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定顶点集为空

16、集的图为生顶点集为空集的运算结果，为此规定顶点集为空集的图为空空图图，并将，并将空图记为空图记为。第22页，讲稿共61张，创作于星期日标定图与非标定图、基图 将图的集合定义转化成图形表示之后，将图的集合定义转化成图形表示之后，常用常用e ek k表示表示无向边无向边(v vi i,v,vj j)（或或有向边有向边 ），），并称顶点或边用字母标定的图并称顶点或边用字母标定的图为为标定图标定图，否则称为，否则称为非标定图非标定图。将有向图各有向边均改成无向边后的无将有向图各有向边均改成无向边后的无向图称为原来图的向图称为原来图的基图基图。易知标定图与非标定图是可以相互转化的，易知标定图与非标定图是

17、可以相互转化的，任何无向图任何无向图G G的各边均加上箭头就可以得的各边均加上箭头就可以得到到以以G G为基图的有向图为基图的有向图。第23页，讲稿共61张，创作于星期日关联与关联次数、环、孤立点 设设G G为无向图，为无向图，ek(vi,vj)E)E，称称vi,vj为为ek的端点，的端点，ek与与vi或或ek与与vj是是彼此相关联彼此相关联的。的。若若vivj，则称则称ek与与vi或或ek与与vj的的关联次数关联次数为为1 1。若若vivj，则称则称ek与与vi的的关联次数为关联次数为2 2，并称，并称ek为为环环。任意的任意的vlVV，若若vlvi且且vlvj，则称则称ek与与vl的的关关

18、联次数为联次数为0 0。第24页，讲稿共61张，创作于星期日关联与关联次数、环、孤立点 设设D D为有向图，为有向图，ek EE，称称vi,vj为为ek的的端点端点。若若vivj，则称则称ek为为D D中的中的环环。无论在无向图中还是在有向图中，无边关联的无论在无向图中还是在有向图中，无边关联的顶点均称为顶点均称为孤立点孤立点。第25页，讲稿共61张，创作于星期日相邻与邻接 设无向图设无向图G GVE，vi，vjVV，ek，elEE。若若 etEE，使得使得et(vi，vj)，则称则称vi与与vj是彼此相是彼此相邻的邻的若若ek与与el至少有一个公共端点，则称至少有一个公共端点，则称ek与与e

19、l是彼此是彼此相邻的相邻的。设有向图设有向图D DVE，vi，vjVV，ek，elEE。若若 etEE，使得使得et ，则称则称vi为为et的始点，的始点，vj为为et的终点，并称的终点，并称vi邻接到邻接到vj，vj邻接于邻接于vi。若若ek的终点为的终点为el的始点，则称的始点，则称ek与与el相邻相邻。第26页，讲稿共61张，创作于星期日27例：点边之间的关联次数例：点边之间的关联次数第27页，讲稿共61张，创作于星期日28例：点点、边边之间的相邻关系例：点点、边边之间的相邻关系第28页，讲稿共61张，创作于星期日顶点的度数定义定义 设设G G为一无向图，为一无向图，vVV，称称v作作为

20、边的端点次数之和为为边的端点次数之和为v的度数，简称为度，的度数，简称为度，记做记做 dG(v)。在不发生混淆时，简记为在不发生混淆时，简记为d(v)。设设D DVE为有向图，为有向图，vVV，称称v作为边的作为边的始点次数之和始点次数之和为为v的的出度出度，记做，记做d+D(v)，简记作简记作d+(v)。称称v作为边的作为边的终点次数之和终点次数之和为为v的的入度入度，记做，记做 d-D(v)，简记作简记作d-(v)。称称d+(v)+)+d-(v)为为v v的度数的度数，记做，记做d(v)。第29页，讲稿共61张，创作于星期日30d(v1)=4d(v2)=4d(v3)=3d(v4)=1d(v

21、5)=0第30页，讲稿共61张，创作于星期日31d+(v1)=2d+(v2)=1d+(v3)=3d+(v4)=1d+(v5)=1d-(v1)=1d-(v2)=3d-(v3)=0d-(v4)=3d-(v5)=1d(v1)=3d(v2)=4d(v3)=3d(v4)=4d(v5)=2第31页，讲稿共61张，创作于星期日32最大(出/入)度,最小(出/入)度在无向图在无向图G G中中，最大度:(G)=max dG(v)|vV(G)最小度:(G)=min dG(v)|vV(G)在有向图在有向图D D中，中，最大出度:+(D)=max dD+(v)|vV(D)最小出度:+(D)=min dD+(v)|vV

22、(D)最大入度:-(D)=max dD-(v)|vV(D)最小入度:-(D)=min dD-(v)|vV(D)简记为,+,+,-,-第32页，讲稿共61张，创作于星期日33握手定理（图论基本定理）握手定理（图论基本定理）定理定理7.1 7.1 设图G=为无向图或有向图，V=v1,v2,vn,|E|=m，则说明说明任何无向图中，各顶点度数之和等于边数的两倍。证明证明G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然，m条边，共提供2m度。推论：推论：任何图中，度为奇数的顶点个数为偶数。第33页，讲稿共61张，创作于星期日问题研究问题：问题：在一个部门的25个

23、人中间，由于意见不同，是否可能每个人恰好与其他5个人意见一致？解答：解答：不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。说明：说明：(1)很多离散问题可以用图模型求解。(2)为了建立一个图模型，需要决定顶点和边分别代表什么。(3)在一个图模型中，边经常代表两个顶点之间的关系。第34页，讲稿共61张，创作于星期日35握手定理握手定理定理7.2 设有向图D=，V=v1,v2,vn,|E|=m，则 第35页，讲稿共61张，创作于星期日度数列设设G G为一个为一个n阶无向图，阶无向图，V V v1 1,v2 2,vn

24、，称称d(v1 1)，d(v2 2)，d(vn n)为为G G的的度数列度数列。对于对于顶点标定顶点标定的无向图，它的度数列是唯一的。的无向图，它的度数列是唯一的。反之，对于给定的非负整数列反之，对于给定的非负整数列d d1 1,d2 2,dn，若存在若存在V V v1 1,v2 2,vn 为顶点集的为顶点集的n阶无向图阶无向图G G，使得使得d(vi)di，则称则称d是是可图化可图化的。的。特别地，若所得图是简单图，则称特别地，若所得图是简单图，则称d是是可简单图化可简单图化的。的。类似地，设类似地，设D D为一个为一个n n阶有向图，阶有向图，V V v1 1,v2 2,vn，称称d(v1

25、 1)，d(v2 2)，d(vn)为为D D的度数列，另外称的度数列，另外称d+(v1 1)，d+(v2 2)，d+(vn)与与d-(v1 1)，d-(v2 2)，d-(vn)分别为分别为D D的的出度列出度列和和入度列入度列。第36页，讲稿共61张，创作于星期日度数列举例按顶点的标定顺序，度数列为 4,4,2,1,3。第37页，讲稿共61张，创作于星期日度数列举例按字母顺序，度数列：5,3,3,3出度列：4,0,2,1入度列：1,3,1,2第38页，讲稿共61张，创作于星期日39 (4，4，3，1，0)(3，4，3，4，2)练习：练习：第39页，讲稿共61张，创作于星期日可图化的充要条件定理

26、 设非负整数列d(d1，d2，dn)，则d是可图化的当且仅当 证明必要性。由握手定理显然得证。充分性。由已知条件可知，d中有偶数个奇数度点。奇数度点两两之间连一边，剩余度用环来实现。5331第40页，讲稿共61张，创作于星期日41例例7.17.1：1.1.(3,3,2,3),(5,2,3,1,4)(3,3,2,3),(5,2,3,1,4)能成为图的度数序能成为图的度数序列吗？为什么？列吗？为什么？2.2.已知图已知图G G中有中有1010条边，条边，4 4个个3 3度顶点，其余顶点的度数度顶点，其余顶点的度数均小于等于均小于等于2 2，问，问G G中至少有多少个顶点？为什么？中至少有多少个顶点

27、？为什么？解：解：1.1.由于这两个序列中，奇数度顶点个数均为奇数，由握手定由于这两个序列中，奇数度顶点个数均为奇数，由握手定理的推论可知，它们都不能成为图的度数序列。理的推论可知，它们都不能成为图的度数序列。2.2.显然，显然，图图G中的其余顶点度数均为中的其余顶点度数均为2时时G图的顶点数最图的顶点数最少少.设设G图至少有图至少有x个顶点个顶点.由握手定理可知，由握手定理可知，34+2(x-4)=210解得解得:x=8所以所以G至少有至少有8个顶点。个顶点。第41页，讲稿共61张，创作于星期日简单图与多重图 定义定义 在在无向图无向图中，关联一对顶点的无向边如果多于中，关联一对顶点的无向边

28、如果多于1 1条，则称条，则称这些边为这些边为平行边平行边，平行边的条数称为，平行边的条数称为重数重数。在在有向图有向图中，关联一对顶点的有向边如果多于中，关联一对顶点的有向边如果多于1 1条，并条，并且这些边的始点和终点相同且这些边的始点和终点相同(也就是它们的方向相同也就是它们的方向相同)，则称这些边为则称这些边为平行边平行边。含平行边的图称为含平行边的图称为多重图多重图。既不含平行边也不含环的图称为既不含平行边也不含环的图称为简单图简单图。第42页，讲稿共61张，创作于星期日43简单图与多重图示例 第43页，讲稿共61张，创作于星期日完全图定义定义7 7.7 7 设G为n阶无向简单图，若

29、G中每个顶点均与其余的n-1个顶点相邻，则称G为n阶无向完全图，简称n阶完全图阶完全图，记做Kn(n1)。设D为n阶有向简单图，若D中每个顶点都邻接到其余的n-1个顶点，又邻接于其余的n-1个顶点，则称D是n阶有向完全图阶有向完全图。设D为n阶有向简单图，若D的基图为n阶无向完全图Kn，则称D是n阶竞赛图阶竞赛图。第44页，讲稿共61张，创作于星期日完全图举例n阶无向完全图的边数为：阶无向完全图的边数为：n(n-1)/2-1)/2n阶有向完全图的边数为：阶有向完全图的边数为：n(n-1)-1)n阶竞赛图的边数为：阶竞赛图的边数为：n(n-1)/2-1)/2K53阶有向完全图4阶竞赛图第45页，

30、讲稿共61张，创作于星期日正则图定义定义设设G G为为n阶无向简单图，若阶无向简单图，若vV(G)V(G)，均有均有d(v)k，则称则称G G为为k-正则图正则图。举例举例 n阶零图是阶零图是0-0-正则图正则图n阶无向完全图是阶无向完全图是(n-1)-1)-正则图正则图彼得森图是彼得森图是3-3-正则图正则图说明说明 n阶阶k-正则图中，边数正则图中，边数mkn/2/2。当当k为奇数时，为奇数时，n必为偶数。必为偶数。第46页，讲稿共61张，创作于星期日子图定义定义设设G ，G 为两个图为两个图(同为无向图或同同为无向图或同为有向图为有向图)，若，若V V且且E E，则称则称G G 是是G

31、G的的子图子图，G为为G 的的母图母图，记作，记作G G。若若V V或或E E，则称则称G 为为G的的真子图真子图。若若V V，则称则称G 为为G的的生成子图生成子图。设设G 为一图，为一图，V1 1 V且且V1 1，称以称以V1 1为顶点集，为顶点集，以以G中两个端点都在中两个端点都在V1 1中的边组成边集中的边组成边集E1 1的图为的图为G的的V1 1导出导出的子图的子图，记作，记作G V1 1。设设E1 1 E且且E1 1，称以称以E1 1为边集，以为边集，以E1 1中边关联的顶点中边关联的顶点为顶点集为顶点集V1 1的图为的图为G的的E1 1导出的子图导出的子图，记作，记作G E1 1

32、。第47页，讲稿共61张，创作于星期日48在上图中，在上图中，(2)，(3)均为均为(1)的子图；的子图；(3)是生成子图；是生成子图；(5)，(6)均为均为(4)的子图；的子图；(5)是生成子图；是生成子图；第48页，讲稿共61张，创作于星期日导出子图举例在上图中，设在上图中，设G G为为(1)(1)中图所表示，中图所表示，取取V V1 1a,b,ca,b,c，则则V V1 1的导出子图的导出子图GVGV1 1 为为(2)(2)中图中图所示。所示。取取E E1 1ee1 1,e,e3 3，则则E E1 1的导出子图的导出子图GEGE1 1 为为(3)(3)中图中图所示。所示。第49页，讲稿共

33、61张，创作于星期日补图定义7.9 设G为n阶无向简单图，以V为顶点集，以所有为边集使G成为完全图Kn的添加边组成的集合的图，称为G的补图，记作G。若图GG，则称为G是自补图。(1)(1)为自补图为自补图(2)(2)和和(3)(3)互为补图互为补图第50页，讲稿共61张，创作于星期日51在下图中，在下图中，(1)是是(2)的补图，当然的补图，当然(2)也是也是(1)的补图，的补图，就是说，就是说，(1)，(2)互为补图。同样，互为补图。同样，(3)，(4)互为补互为补图。图。第51页，讲稿共61张，创作于星期日52图的同构图的同构在在图图论论的的研研究究中中，我我们们更更关关心心的的是是图图的

34、的结结构构,而而这这种种结结构构与与顶顶点点与与边边的的具具体体元元素素或或与与图图的的图图形形的的画画法无关法无关.对此对此,我们引进我们引进同构同构的概念的概念.第52页，讲稿共61张，创作于星期日53图同构(graph isomorphism)定义7.10:设两个无向（有向）图G1=,G2=,若存在双射f:V1V2,满足 uV1,vV1,e=(u,v)E1 e=(f(u),f(v)E2 (e=E1 e=E2)并且e与e的重数相同，则称G1与G2同构,记作G1G2说明:同构的图,其图论性质完全一样第53页，讲稿共61张，创作于星期日54图的同构图的同构第54页，讲稿共61张，创作于星期日5

35、5第55页，讲稿共61张，创作于星期日56(1)(2)(3)(4)(5)和和(6)不同构不同构,因为在因为在(6)中中有三个彼此不邻接的顶点有三个彼此不邻接的顶点,而在而在(5)找不到找不到三个彼此不邻接的顶点三个彼此不邻接的顶点.图同构课例图同构课例:第56页，讲稿共61张，创作于星期日57判断两个图同构的必要条件是判断两个图同构的必要条件是:(1)顶点数相同顶点数相同;(2)边数相同边数相同;(3)对应顶点的度数也相同对应顶点的度数也相同.第57页，讲稿共61张，创作于星期日例7.2(1)画出4阶3条边的所有非同构的无向简单图。由握手定理可知，所画的无向简单图各顶点度数之和为236，最大度

36、小于或等于3。于是所求无向简单图的度数列应满足的条件是，将6分成4个非负整数，每个整数均大于或等于0且小于或等于3，并且奇数的个数为偶数。将这样的整数列排出来只有下面三种情况：(1)2，2，1，1(2)3，1，1，1(3)2，2，2，0 将每种度数列所有非同构的图都画出来即得所要求的全部非同构的图。对于给定的正整数n和m(mn(n-1)/2)，构造出所有非同构的n阶m条边的所有非同构的无向(有向)简单图，这是目前还没有解决的难题。第58页，讲稿共61张，创作于星期日(2)(2)画出画出3 3阶阶2 2条边的所有非同构的有向简单图条边的所有非同构的有向简单图由握手定理可知，所画有向简单图各顶点度数之和为4，最大出度和最大入度均小于或等于2。度数列及入度出度列为1,2,1入度列为 0,1,1 或 0,2,0 或 1,0,1出度列为 1,1,0 或 1,0,1 或 0,2,02,2,0入度列为 1,1,0出度列为 1,1,0第59页，讲稿共61张，创作于星期日60作业P173 7.6 7.7 7.8第60页，讲稿共61张，创作于星期日感感谢谢大大家家观观看看第61页，讲稿共61张，创作于星期日