离散数学（下篇共上下2篇）

《离散数学》第6章图

DiscreteMathematics内容导航CONTENTS历史人物本章导读及学习要求图的基本概念握手定理图的同构图的连通性

6.1

6.2

6.3

6.4作业

6.5图的应用通路与回路

6.7

6.6本章导读图论是一门很有实用价值的学科，在自然科学、社会科学等各领域均有很多应用。自20世纪中叶以来，受计算机科学蓬勃发展的刺激，图论发展极其迅速，应用范围不断拓广，已渗透到语言学、逻辑学、物理学、化学、电信工程、软件工程、计算机科学以及数学的其他分支中。特别是在计算机科学的形式语言、数据结构、分布式系统、操作系统等方面，图论均扮演着重要的角色。高速数字计算机

6克希荷夫定律3树凯莱4七桥问题欧拉

1游戏、博弈问题

2四色猜想5本章导读图论作为一个数学分支，有一套完整的体系和广泛的内容，本书仅介绍图论的初步知识，以便读者今后对计算机有关学科进行学习和研究时，可以以图论的基本知识作为工具。我们所讨论的图（Graph）与人们通常所熟悉的图，如圆、椭圆、函数图表等是不相同的。图论中所谓的图是指某类具体离散事物集合和该集合中的每对事物间以某种方式相联系的数学模型。如果我们用点表示具体事物，用连线表示一对具体事物之间的联系，那么，一个图就是由一个表示具体事物的点的集合和表示事物之间联系的一些线的集合所构成。学习时应掌握好图论的基本概念、基本方法和基本算法，善于把实际问题抽象为图论的问题，然后用图论的方法去解决。重点1图基本概念及分类2握手定理的理解与运用3邻接矩阵的理解与运用4通路与回路的理解与运用5图连通性的判断6连通分支的计算难点1图同构的判断与证明2单向连通图的判断3连通分支的计算学习要求内容导航CONTENTS历史人物本章导读及学习要求图的基本概念握手定理图的同构图的连通性

6.1

6.2

6.3

6.4作业

6.5图的应用通路与回路

6.7

6.6欧拉出生于牧师家庭，自幼受父亲的影响特别喜欢数学，不满10岁就开始自学《代数学》，13岁考入巴塞尔大学，是整个瑞士大学校园里年龄最小的学生，得到当时最有名的数学家约翰·伯努利（JohannBernoulli）的精心指导，15岁获学士学位，16岁获硕士学位。1727年，应圣彼得堡科学院的邀请到俄国，1731年他接替丹尼尔·伯努利（DanielBernoulli）成为物理教授，1741年受普鲁士腓特烈大帝的邀请到柏林科学院工作，1766年受俄皇叶卡杰琳娜二世的盛情邀请又回到了圣彼得堡。1783年9月18日，76岁的欧拉弯下腰捡他的烟斗，就再也没有站起来。莱昂哈德·欧拉（LeonhardEuler，1707-1783）瑞士数学家、自然科学家，18世纪数学界最杰出人物之一，图论之父欧拉不但在数学上做出了伟大贡献，而且把数学用到了几乎整个物理领域。在解决物理问题的过程中，创立了微分方程。研究了函数用三角级数表示的方法和解微分方程的级数法等，引入了空间曲线的参数方程，给出了空间曲线曲率半径的解析表达式，建立了曲面理论。1766年出版的《关于曲面上曲线的研究》是对微分几何最重要的贡献，是微分几何发展史上的一个里程碑。在分析学上的贡献不胜枚举，如引入了Γ函数和B函数、证明了椭圆积分的加法定理、最早引入了二重积分等。数论作为数学中一个独立分支的基础，也是由欧拉的一系列成果所奠定的。莱昂哈德·欧拉（LeonhardEuler，1707-1783）瑞士数学家、自然科学家，18世纪数学界最杰出人物之一，图论之父欧拉在数学的许多分支中都常常见到以他的名字命名的重要常数、公式和定理。解决了著名的图论问题：哥尼斯堡七桥问题。科学史上最多产的一位杰出数学家，从19岁到76岁发表的成熟著作有860多篇。性格乐观，开朗热情。400多篇是双目失明后研究得出的。为了纪念欧拉的数学贡献，以及对世界科学的影响，瑞士于1957年欧拉诞辰250周年之际发行了一套邮票，又于2007年发行了新的纪念邮票纪念欧拉诞辰300周年；小行星欧拉2002也是为了纪念欧拉而命名的。莱昂哈德·欧拉（LeonhardEuler，1707-1783）瑞士数学家、自然科学家，18世纪数学界最杰出人物之一，图论之父迪杰斯特拉1948年考入莱顿大学，在三年之内取得了学士学位并留校就职。早年钻研物理及数学，而后转向计算学。1962年任埃因霍芬理工大学教授，1973年成为了美国宝来公司的研究员，1984年任得克萨斯州立大学计算机科学学院教授，1999年69岁时结束了作为教授的职业生涯。1972年获得素有计算机科学界的诺贝尔奖之称的图灵奖，1974年获得美国古德纪念奖、1989年获得ACM计算机科学教育教学杰出贡献奖、2002年获得ACM分布式计算原理最具影响力论文奖。艾兹格·W·迪杰斯特拉（EdsgerWybeDijkstra，1930-2002）计算机科学家迪杰斯特拉是计算机先驱之一，开发了程序设计的框架结构。迪杰斯特拉的最短通路算法推动了计算机高级语言——ALGOL的诞生。开启了一个新的领域——程序设计教育。被西方学术界称为“结构程序设计之父”和“先知先觉”。致力于把程序设计发展成一门科学，大力提倡程序正确性证明。艾兹格·W·迪杰斯特拉（EdsgerWybeDijkstra，1930-2002）计算机科学家江泽涵1926年南开大学数学系毕业后，随南开大学数学系创始人、数学家和教育家姜立夫去厦门大学数学系任助教，1927年考取了那年清华大学留美唯一的学数学的名额，赴哈佛大学数学系攻读博士学位。1931年到北京大学数学系任教。由于教育经费拖欠，北大数学系的教学质量受到了影响，数学系对学生管理松懈，课外习题和阶段考试都形同虚设。大力整顿教学风气，在教学中坚持要学生做习题，并在课堂纪律、训练和考试等方面严格要求。这样做引起了一部分学生的不满，甚至罢课数天以示反抗。但有南开大学和清华大学两校严格教学的榜样，又得到理学院和系里的支持，改革得以贯彻，教学工作顺利完成。江泽涵（1902-1994），数学家，数学教育家，中国国拓扑学的奠基人，中国数学会的创始人之一江泽涵在用人方面不立山头，不抱门户之见。发扬北京大学老校长蔡元培先生倡导的在学术上“兼容并蓄”的精神，任用各个学科方向的有才华的年轻人在北京大学做教员。30年代他聘请了樊畿、孙树本、张禾瑞、王湘浩等北京大学毕业生留校任教，他们分别是应用数学、方程、代数等方向的尖子生。他还聘来了刚刚留学归来的概率统计学家许宝騄。抗战胜利后回北京大学重建数学系教师班子时，他又从全国多方聘请了各学科方向的教员，如吴文俊、廖山涛、程民德、孙以丰等。那时候，中国的许多数学分支的研究还是很薄弱的，有的还是空白，但是在江泽涵主持下的北京大学数学系，教师队伍力量雄厚，学科门类较齐全，教学质量和学术水平也都站到了全国的前列。江泽涵（1902-1994），数学家，数学教育家，中国国拓扑学的奠基人，中国数学会的创始人之一江泽涵作为我国代数拓扑学的开拓者，在学术研究上，取得的最大成就是在不动点理论方面的研究。他和自己的学生姜伯驹、石根华在多方面开展研究，和姜伯驹一起提出自映射的伦型概念，证明尼尔森数具有伦型不变性。在他的指导下，姜伯驹和石根华在尼尔森数的计算和尼尔森数的实现问题上取得了重大突破。他们的工作打破了50年来国际上这个课题的研究工作长期停滞的状态，在国际上得到了很高的评价，同行称他们为拓扑学界的一个新的“中国学派”。江泽涵（1902-1994），数学家，数学教育家，中国国拓扑学的奠基人，中国数学会的创始人之一内容导航CONTENTS历史人物本章导读及学习要求图的基本概念握手定理图的同构图的连通性

6.1

6.2

6.3

6.4作业

6.5图的应用通路与回路

6.7

6.66.1.1图的定义现实世界中许多现象都是由某类事物及事物间的联系构成的，能用某种图形表示，这些图形由一些点和两点间的连线所组成。例6.1（1）考虑一张物种栖息地重叠图，图中用点表示每个物种，当两个物种竞争（即它们共享某些食物来源）时，就用一条线将相应的点连接起来。这种图的一部分如左下图所示，从图中看出，松鼠与浣熊竞争，乌鸦不与浣熊竞争。（2）在电子商务中，用户与商品之间的购买关系如下：有3个用户A、B和C，3件商品D、E和F，假设A购买了D，B购买了E和F，C购买了D和E，则这种购买情形可用右下图表示。猫头鹰鹰浣熊松鼠乌鸦ACFDBE定义6.1一个图(Graph)是一个序偶<V,E>，记为G=<V,E>，其中：（1）V={v1,v2,…,vn}是有限非空集合，vi称为结点(NodalPoint)，简称点(Point)，V称为结点集(NodalSet)。（2）E是有限集合，称为边集(FrontierSet)。E中的每个元素都有V中的结点对与之对应，称之为边(Edge)。注意：定义中的结点对即可以是无序的，也可以是有序的。若边e与无序结点对(u,v)相对应，则称e为无向边(UndirectedEdge)，记为e=(u,v)=(v,u)，这时称u、v是边e的两个端点(Endpoint)，也称结点ｕ与边ｅ(结点ｖ与边ｅ)是彼此相关联的。若边e与有序结点对<u,v>相对应，则称e为有向边(DirectedPoint)(或弧)，记为e=<u,v>，这时称u为e的始点(InitialPoint)(或弧尾)，v为e的终点(terminalPoint)(或弧头)，统称为e的端点。ACFDBE6.1.2图的表示对于一个图G，如果将其记为G=<V,E>，并写出V和E的集合表示，这称为图的集合表示。而为了描述简便起见，在一般情况下，往往只画出它的图形：用小圆圈表示V中的结点，用由u指向v的有向线段或曲线表示有向边<u,v>，无向线段或曲线表示无向边(u,v)，这称为图的图形表示。解题小贴士——图G＝<V,E>的集合表示与图形表示相互转换的方法（1）集合表示转换为图形表示。用小圆圈表示V中的每一个结点，结点位置可随意放，元素<u,v>用由u指向v的有向边表示，元素(u,v)用u与v相连的无向边表示。（2）图形表示转换为集合表示。图中的所有结点构成结点集，图中的无向边用无序偶对表示，有向边用序偶表示，注意箭头指向的结点是序偶的第二元素。例6.2设图G=<V,E>，这里V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6}，其中e1=(v1,v2)，e2=<v1,v3>，e3=(v1,v4)，e4=(v2,v3)，e5=<v3,v2>，e6=(v3,v3)。试画出图G的图形，并指出哪些是有向边，哪些是无向边？v3e1e2e3e5v2v1v4e4v5e6无向边：e1、e3、e4、e6有向边：e2、e5例6.3设图G=<V,E>的图形如下图所示，试写出G的集合表示。12345解

图G的集合表示为G=<V,E>=<{1,2,3,4,5}，{<1,1>，<1,2>，(1,4)，(1,5)，(2,3)，<3,5>，<4,3>，<4,5>}>。两种描述方法的优缺点用集合描述图的优点是精确，但抽象不易理解；用图形表示图的优点是形象直观，但当图中的结点和边的数目较大时，使用这种方法是很不方便的，甚至是不可能的。我们在学习中常常需要分析图并在图上执行各种过程和算法，也许必须用计算机来执行这些算法，因此必须把图的结点和边传输给计算机，由于集合与图形都不适合计算机处理，所以要找到一种新的表示图的方法，这就是图的矩阵表示。由于矩阵的行和列有固定的次序，因此在用矩阵表示图时，先要将图的结点进行排序，若不具体说明排序，则默认为书写集合V时结点的顺序。定义6.2设图G=<V,E>，其中V={v1,v2,…,vn}，并假定结点已经有了从v1到vn的次序，则n阶方阵AG=(aij)nxn称为G的邻接矩阵(AdjacencyMatrix)，其中解题小贴士——图的邻接矩阵表示（1）将图中的结点排序。（2）图中第i个结点到第j个结点有边，则邻接矩阵的第i行第j列元素为1。例6.4试写出右图所示图G的邻接矩阵。v1v2v5v4v3v6解若结点排序为v1v2v3v4v5v6，则其邻接矩阵说明由定义6.2可看出，图G=<V,E>的邻接矩阵依赖于V中元素的次序。对于V中各元素不同的排序，可得到同一图G的不同邻接矩阵。但是，G的任何一个邻接矩阵可以从G的另一邻接矩阵中通过交换某些行和相应的列而得到，其交换过程与将一个排序中的结点交换位置变为另一个排序是一致的。如果我们略去由结点排序不同而引起的邻接矩阵的不同，则图与邻接矩阵之间是一一对应的。因此，我们略去这种由于V中元素的次序而引起的邻接矩阵的任意性，只选V中元素的任一种次序所得出的邻接矩阵，作为图G的邻接矩阵。例图中的结点重排次序为v5v2v1v3v6v4，得另一个邻接矩阵在邻接矩阵A1G中，如果先交换第1、3行，而后交换第1、3列；接着交换第3、4行，再交换第3、4列；接着交换第5、6行，再交换第5、6列；接着交换第4、5行，再交换第4、5列。那么就能由邻接矩阵A1G得到邻接矩阵AG。6.1.3图的操作定义6.3设图G=<V,E>。设e∈E，用G-e表示从G中去掉边e得到的图，称为删除边e。又设E

E，用G-E

表示从G中删除E

中所有边得到的图，称为删除E

。设v∈V，用G-v表示从G中去掉结点v及v关联的所有边得到的图，称为删除结点v。又设V

V，用G-V

表示从G中删除V

中所有结点及关联的所有边得到的图，称为删除V

。设e=(u,v)∈E，用G\e表示从G中删除e，将e的两个端点u,v用一个新的结点w代替，使w关联除e外的u和v关联的一切边，称为边e的收缩。一个图G可以收缩为图H，是指H可以从G经过若干次边的收缩而得到。设u,v∈V(u,v可能相邻，也可能不相邻)，用G∪(u,v)表示在u,v之间加一条边(u,v)，称为加新边。解题小贴士——图的操作（1）删除边e，就是直接从图中去掉边e。（2）删除结点v，不仅要去掉结点v，还要去掉结点v关联的所有边。（3）收缩边e，就是将边e的长度缩短到零，并用一个新结点w代替e的两个端点，原来与e的两个端点关联的所有边改为与w关联。（4）加新边就是增加一条边。例6.5对右图所示的图G完成下列操作。（1）删除边(v3,v6)。（2）删除结点v6。（3）收缩边(v3,v6)。（4）加新边(v1,v3)。v1v2v5v4v3v6v1v2v5v4v3v6(1)v1v2v5v4v3(2)v1v2v5v4w(3)v1v2v5v4v3v6(4)6.1.4邻接点与邻接边定义6.4在图G=<V,E>中，若两个结点vi和vj是边e的端点，则称vi与vj互为邻接点(AdjacentPoint)，否则vi与vj称为不邻接的具有公共结点的两条边称为邻接边(AdjacentEdge)两个端点相同的边称为环(Ring)或自回路(Self-Loop)图中不与任何结点相邻接的结点称为孤立结点(IsolatedPoint)仅由孤立结点组成的图称为零图(NullGraph)仅含一个结点的零图称为平凡图(TrivialGraph)含有n个结点，m条边的图，称为(n,m)图解题小贴士——邻接点与邻接边的计算（1）一个点的邻接点就是所有以这个点为端点的边的另一个端点。（2）一条边的邻接边就是所有以这条边的两个端点为公共结点的边。注意：只有当一个结点处有环时，它才是自己的邻接点，而所有边都是自己的邻接边。例9.2.5写出下面图G所有结点的邻接点、所有边的邻接边，并指出所有的孤立结点和环。v3e1e2e3e5v2v1v5e4v4e6e7v6结点邻接点孤立结点v1v1,v2,v3,v4否v2v1,v3否v3v1,v2否v4v1否v5是v6v6否边邻接边环e1e1,e2,e3,e4,e5,e6否e2e1,e2,e3,e6否e3e1,e2,e3,e6是e4e1,e4,e5,e6否e5e1,e4,e5,e6否e6e1,e2,e3,e4,e5,e6否e7e7是图G既不是平凡图，也不是零图，而是一个(6,7)图。6.1.5图的分类边方向无向图有向图混合图图赋权图无权图权多重图线图简单图平行边环1.按边有无方向分类定义6.5每条边都是无向边的图称为无向图(UndirectedGraph)；

每条边都是有向边的图称为有向图(DirectedGraph)；

有些边是无向边，而另一些边是有向边的图称为混合图(MixedGraph)。第4章的关系图都是有向图，这时邻接矩阵就是关系矩阵。例6.7试判断下面三个图是无向图、有向图，还是混合图。v3G1v2v1v3G2v2v1v3G3v2v1无向图有向图混合图说明我们仅讨论无向图和有向图，至于混合图，我们可将其中的无向边看成方向相反的两条有向边，从而转化为有向图来研究。例如可将混合图G3转化为有向图。v3v2v1v3v2v12.按有无平行边分类定义6.6在有向图中，两结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边(ParallelEdge)；在无向图中，两结点间(包括结点自身间)若有几条边，则这几条边称为平行边。两结点a、b间相互平行的边的条数称为边(a,b)或<a,b>的重数(RepeatedNumber)。含有平行边的图称为多重图(Multigraph)非多重图称为线图(LineGraph)；无环的线图称为简单图(SimpleGraph)。例6.8试判断下图所示的4个图是多重图、线图还是简单图，并指出多重图中所有平行边的重数。v3G1v2v1v4aG2bc21G33βαG4γδ多重图多重图线图简单图22332线图3.按边或结点是否含权分类定义9.2.7赋权图(WeightGraph)G是一个三重组<V,E,g>或四重组<V,E,f,g>，其中V是结点集合，E是边的集合，f是从V到非负实数集合的函数，g是从E到非负实数集合的函数。非赋权图称为无权图。例6.9下图所示的图哪个是赋权图，哪个是无权图？是赋权图的请写出相应的函数。v4v1v2v3G3v3G1v2v1v45676881069c7abd50407035G245赋权图赋权图无权图记图G1=<V1,E1,g1>，其中：g1(<v1,v2>)=5

g1(<v1,v3>)=6g1(<v1,v4>)=7

g1(<v2,v3>)=6g1(<v3,v2>)=8 g1(<v4,v1>)=8记图G2=<V2,E2,f2,g2>，其中：f2(a)=9，f2(b)=6，f2(c)=7，f2(d)=10；g2((a,b))=50，g2((a,c))=70，g2((a,d))=45，g2((b,c))=40，g2((c,d))=35注还可以将上述三种分类方法综合起来对图进行划分。有向无权多重图无向赋权简单图1069c7abd5040703545bac6.1.6子图与补图定义6.8设有图G=<V,E>和图G1=<V1,E1>。若V1V，E1E，则称G1是G的子图(Subgraph)，记为G1G若G1G，且G1≠G(即V1V或E1E)，则称G1是G的真子图(ProperSub-graph)，记为G1G若V1=V，E1E，则称G1是G的生成子图(SpanningSubgraph)设V2V且V2≠

，以V2为结点集，以两个端点均在V2中的边的全体为边集的G的子图，称为V2导出的G的子图，简称V2的导出子图(InducedSubgraph)V2导出的G的子图即为G–(V-V2)解题小贴士——子图的判断(１)子图的结点集和边集是Ｇ的结点集和边集的子集。(２)真子图的结点集和边集是Ｇ的结点集或边集的真子集。(３)生成子图与Ｇ的结点集相同而边集是子集。(４)Ｖ2的导出子图要求包含Ｇ中所有两个端点属于Ｖ２的边。例6.10判断下图中，图G1、G2和G3是否是图G的子图、真子图、生成子图、导出子图？v1v2v3v4v5Gv1v2v3v4G1v1v2v3v4v5G2v1v2v3v4G3子图子图子图真子图真子图真子图{v1,v2,v3,v4}的导出子图生成子图注每个图都是它自身的子图、生成子图和导出子图完全图定义9.2.9设G=<V,E>为一个具有n个结点的无向简单图，如果G中任意两个结点间都有边相连，则称G为无向完全图(UndirectedCompleteGraph)，简称G为完全图(CompleteGraph)，记为Kn。设G=<V,E>为一个具有n个结点的有向简单图，如果G中任意两个结点间都有两条方向相反的有向边相连，则称G为有向完全图(directedCompleteGraph)，在不发生误解的情况下，也记为Kn。对于完全图来说，其邻接矩阵除主对角元为0外，其它元素均为1

几个完全图无向完全图Kn的边数为有向完全图Kn的边数为K3K4K5K3有向补图定义6.10设G=<V,E>为简单图，G’=<V,E1>为完全图，则称G1=<V,E1-E>为G的补图(ComplementofGraph)，记为GC或。注

在定义6.10中，当G为有向图时，则G’为有向完全图；当G为无向图时，则G’为无向完全图。G的补图也可理解为从结点集V的完全图中删除G中的边剩下的图，即G与其补图GC的结点集是相同的，边集是相对于完全图的边集为全集的补集。若G1=GC，则G=G1C

，即它们互为补图。Kn的补图为n个结点的零图(n,0)。解题小贴士——补图的计算结点集相同，边集是相对于完全图边集的补集。例6.11求补图(b)213(c)2341(a)12345123452132341注意，孤立结点一定不要漏了，否则结点集就不同。利用邻接矩阵描述补图若设简单图G的邻接矩阵A=(aij)n×n，则它的补图GC的邻接矩阵有：例6.12证明：在任意6个人的集会上，总会有3个人相互认识或者有3个人互相不认识（假设认识是相互的）。证明：把参加集会的人作为结点，相互认识的人之间连边，得到图G，设GC为G的补图，这样问题就转化为证明G或中至少有一个子图是完全图K3。考虑完全图K6，结点v1与其余5个结点各有一条边相连，这5条边一定有3条在G或GC中，不妨设有3条边在G中，设这3条边为(v1,v2)、(v1,v3)、(v1,v4)。考虑结点v2,v3,v4。若v2,v3,v4在G中无边相连，则v2,v3,v4相互不认识；若v2,v3,v4在G中至少有一条边相连，例如(v2,v3)，则v1,v2,v3就相互认识。因此，总会有3个人相互认识或者有3个人互相不认识。内容导航CONTENTS历史人物本章导读及学习要求图的基本概念握手定理图的同构图的连通性

6.1

6.2

6.3

6.4作业

6.5图的应用通路与回路

6.7

6.6结点的度数定义6.11（1）图G=<V,E>中以结点v∈V为端点的边数(有环时计算两次)称为结点v的度数(Degree)，简称度，记为deg(v)。（2）有向图G=<V,E>中以结点v为始点的边数称为v的出度(Out-Degree)，记为deg+(v)；以结点v为终点的边数称为v的入度(In-Degree)，记为deg-(v)。显然，deg(v)=deg+(v)+deg-(v)。（3）对于图G=<V,E>，度数为1的结点称为悬挂结点(HangingPoint)，以悬挂结点为端点的边称为悬挂边(HangingEdge)。若G是无向图，则A中第i行元素是由结点vi为端点的边所决定，其中为1的元素数目等于vi的度数，即若G是有向图，则A中第i行元素是由结点vi为始点的边所决定，其中为1的元素数目等于vi的出度，即A中第i列元素是由结点vi为终点的边所决定，其中为1的元素数目等于vi的入度，即利用邻接矩阵描述设图G＝<V,E>，V＝{v1,v2,…,vn}的邻接矩阵为（1）结点v的度数就是以v为端点的边数（有环时计算两次）。（2）结点v的出度就是以v为始点的边数。（3）结点v的入度就是以v为终点的边数。解题小贴士——结点度数的计算vdeg(v)deg+(v)deg-(v)v1101v2431v3312v4422v5000例6.13求下图中所有结点的度数、出度和入度，指出悬挂结点和为悬挂边，并用邻接矩阵验证之。v1v2v3v4v5悬挂结点悬挂边定理6.1(握手定理)图中结点度数的总和等于边数的二倍，即设图G=<V,E>，则有证明

因为每条边都有两个端点(环的两个端点相同)，所以加上一条边就使得各结点的度数之和增加2，因此结论成立。这个结果是图论的第一个定理，它是由欧拉于1736年最先给出的。欧拉曾对此定理给出了这样一个形象论断：如果许多人在见面时握了手，两只手握在一起，被握过手的总次数为偶数。故此定理称为图论的基本定理或握手定理。推论6.1图中度数为奇数的结点个数为偶数。证明

设图G=<V,E>，V1={v|v∈V且deg(v)为奇数}， V2={v|v∈V且deg(v)为偶数}。显然，V1∩V2=Φ，且V1∪V2=V，于是，式中2|E|和（偶数之和为偶数）均为偶数，因而也为偶数。于是|V1|为偶数，即度数为奇数的结点个数为偶数。度数为奇数的结点称为奇度数结点(OddDegreePoint)度数为偶数的结点称为偶度数结点(EvenDegreePoint)定理6.2有向图中各结点的出度之和等于各结点的入度之和，等于边数，即设有向图G=<V,E>，则有证明因为每条有向边具有1个始点和1个终点（环的始点和终点是同1个结点），因此，每条有向边对应1个出度和1个入度。图G中有|E|条有向边，则G中必产生|E|个出度，这|E|个出度即为各结点的出度之和，G中也必产生|E|个入度，这|E|个入度即为各结点的入度之和。因而，在有向图中，各结点的出度之和等于各结点的入度之和，都等于边数|E|。以上两个定理及其推论都是非常重要的，应牢记、理解并灵活运用。定义6.12设V={v1,v2,…,vn}为图G的结点集，称(deg(v1),deg(v2),…,deg(vn))为G的度数序列(DegreeSequence)。v1v2v3v4v5上图的度数序列为(1,4,3,4,0)。解题小贴士——握手定理的应用（1）所有结点度数的总和等于边数的2倍。（2）奇度数结点的个数一定是偶数。（3）有向图中各结点的出度之和等于各结点的入度之和，等于边数。例6.14（1）(3,5,1,4)，(1,2,3,4,5)能成为图的度数序列吗？为什么？（2）已知图G中有15条边，2个度数为4的结点，4个度数为3的结点，其余结点的度数均小于等于2，问G中至少有多少个结点？为什么？解

（1）由于这两个序列中，奇数的个数均为奇数，由推论6.1知，它们都不能成为图的度数序列。（2）图中边数为15，由握手定理知，G中所有结点的度数之和为30，2个度数为4的结点，4个度数为3的结点占去20度，还剩下10度。若其余全是度数为2的结点，还需要5个结点来占用这10度，所以G至少有11个结点。内容导航CONTENTS历史人物本章导读及学习要求图的基本概念握手定理图的同构图的连通性

6.1

6.2

6.3

6.4作业

6.5图的应用通路与回路

6.7

6.6图的同构图是表达事物之间关系的工具，因此，图的最本质的内容是结点和边的关联关系。而在实际画图时，由于结点的位置不同，边的长短曲直不同，同一事物间的关系可能画出不同形状的图来。例如下面的两个图G1和G2实际上是同一个图，都是K4。G11234G21234定义6.13设两个图G=<V,E>和G’=<V’,E’>，如果存在双射函数g：V→V’，使得对于任意的e=(vi,vj)(或者<vi,vj>)∈E当且仅当e’=(g(vi),g(vj))(或者<g(vi),g(vj)>)∈E’，并且e与e’的重数相同，则称G与G’同构(Isomor-phism)，记为G≌G’。对于同构，形象地说，若图的结点可以任意挪动位置，而边是完全弹性的，只要在不拉断的条件下，一个图可以变形为另一个图，那么这两个图是同构的。两个图同构的必要条件（1）结点数目相同（2）边数相同（3）度数相同的结点数相同解题小贴士——图同构的判断找到结点集之间的双射，满足两结点间有边当且仅当它们的函数值间有边并且方向和重数一致。解题小贴士——

图不同构的判断至少满足下列情况之一的两个图是不同构的。（1）结点数目不同。（2）边数不同。（3）度数相同的结点数不同。（4）有两个度数相同的结点的邻接点的度数不完全相同。例9.2.14

证明下图中，G≌G’。证明

构造结点之间的双射函数g

如下：g(1)=a，g(2)=b，g(3)=c，g(4)=dg(5)=e，g(6)=f，g(7)=g，g(8)=h容易验证，g满足同构的定义，所以G≌G’。8G1256G’b347acegdfh例9.2.15证明下图中G与G’不同构。证明假设G≌G’，双射函数为g。由同构的定义，v与g(v)的度数一定相同，因此有g(3)=d。G中3与一个度数为1的结点6邻接，而G’中d与两个度数为1的结点e、f邻接，矛盾。125634GabefcdG’注意图同构的三个必要条件不是充分条件。在上图的G与G’两个图，虽然满足以上三个条件，但不同构。寻找一种简单而有效的方法来判断图的同构，是图论中一个重要而未解决的问题。内容导航CONTENTS历史人物本章导读及学习要求图的基本概念握手定理图的同构图的连通性

6.1

6.2

6.3

6.4作业

6.5图的应用通路与回路

6.7

6.6引言右图是中国铁路交通图的一部分，如果一个旅客要从成都乘火车到北京，那么他一定会经过其他车站；而旅客不可能从成都乘火车到达三亚。这就引出了图的通路与连通的概念。成都昆明重庆广州长沙武汉上海兰州西安沈阳北京天津郑州厦门三亚海口乌鲁木齐通路与回路是图论中两个重要的基本概念。本节所述定义一般来说既适合有向图，也适合无向图，否则，将加以说明或分开定义。６.４.１通路与回路的概念定义6.14给定图G=<V,E>中结点和边相继交错出现的序列Γ=v0e1v1e2v2…ekvk。（1）若Γ中边ei的两端点是vi-1和vi（G是有向图时要求vi-1与vi分别是ei的始点和终点），i=1,2,…,k，则称Γ为结点v0到结点vk的通路(Entry)。v0和vk分别称为此通路的始点和终点，统称为通路的端点。通路中边的数目k称为此通路的长度(Length)。当v0=vn时，此通路称为回路(Circuit)。（2）若通路中的所有边互不相同，则称此通路为简单通路(SimpleEntry)或一条迹；若回路中的所有边互不相同，则称此回路为简单回路(SimpleCircuit)或一条闭迹。（3）若通路中的所有结点互不相同（从而所有边互不相同），则称此通路为基本通路(BasicEntry)或者初级通路、路径；若回路中除v0=vk外的所有结点互不相同（从而所有边互不相同），则称此回路为基本回路(BasicCircuit)或者初级回路、圈。说明（1）回路是通路的特殊情况。因而，当我们说某条通路，它可能是回路；但当我们说一基本通路时，一般是指它不是基本回路的情况。（2）基本通路（回路）一定是简单通路（回路），但反之不真。因为没有重复的结点肯定没有重复的边，但没有重复的边不能保证一定没有重复的结点。（3）在不会引起误解的情况下，一条通路v0e1v1e2v2…envn也可以用边的序列e1e2…en来表示，这种表示方法对于有向图来说较为方便。在线图中，一条通路v0e1v1e2v2…envn也可以用结点的序列v0v1v2…vn来表示。解题小贴士——简单（基本）通（回）路的判断（1）简单通（回）路没有相同的边。（2）基本通（回）路没有相同的结点，当然也没有相同的边。例6.17（1）判断图G1中的下列回路是否是简单回路、基本回路？并求其长度。v3e5v4e7v1e4v3e3v2e1v1e4v3不是简单回路v3e3v2e2v2e1v1e4v3是简单回路，不是基本回路v3e3v2e1v1e4v3是基本回路v1v4v2v3e7e6e1e4e5e3e2G1长度为6长度为4长度为3用边的序列表示e3e2e1e4用结点的序列表示v3v2v2v1v3例6.17（2）判断图G2中的下列通路是否是简单通路、基本通路？并求其长度。

v1e1v2e6v5e7v3e2v2e6v5e8v4不是简单通路v1e5v5e7v3e2v2e6v5e8v4是简单通路，不是基本通路v1e1v2e6v5e7v3e3v4是基本通路v2v5v3v4e2e3e4e5e6e7e1G2v1e8长度为6长度为5长度为4用边的序列表示e5e7e2e6e8用结点的序列表示v1v5v3v2v5v4６.４.２通路与回路的计算定理6.3设G=<V,E>为线图，V={v1,v2,…,vn}，A=(aij)n×n为G的邻接矩阵，Am=()n×n。则为从结点vi到结点vj长度为m的通路数目；为结点vi到自身的长度为m的回路数目；为G中长度为m的通路（含回路）总数。分析观察图G的邻接矩阵A=(aij)n×naij表示从结点vi到结点vj长度为1的通路数目aii表示结点vi到自身的长度为1的回路（即为环）数目而A中所有元素之和为A中长度为1的通路（包括回路）数目。若G是有向图，它也是边的数目；若G是无向图，它是边的数目的二倍减去G中自回路的数目，因为当vi

≠vj时，一条边(vi,vj)即是一条从vi到vj的长度为1的通路，也是一条从vj到vi的长度为1的通路，而(vi,vi)只是一条长度为1的通路，而不能再看作两条。分析下面寻找G中长度为2的通路（包含回路）数目首先计算从结点vi到结点vj的长度为2的通路数目注意到从vi到vj长度为2的通路，中间必经过一结点vp对于任意的p(1≤p≤n)，若存在通路vivpvj，必有aip=1且apj=1，即aip×apj=1。反之，若不存在通路vivpvj，则必有aip=0或apj=0，即aip×apj=0。于是从结点vi到vj长度为2的通路总数为：分析由矩阵的乘法规则可知，恰为A2中第i行第j列的元素。因而在矩阵中，为G中长度为2的通路（含回路）总数，主对角线上元素之和为G中长度为2的回路总数。分析若从结点vi到结点vj存在长度为3的通路，中间必经过一结点vk，使得从vi到vk存在长度为2的通路，从vk到vj存在长度为1的通路。因而，

≥1且akj=1，即×akj≥1。若或akj

=0，从而

×akj=0，则从vi经过vp到vj没有长度为3的通路。于是从结点vi到vj长度为3的通路总数为：分析这正是A2×A=A3中第i行第j列的元素而为G中长度为3的通路（含回路）总数主对角线上元素之和为G中长度为3的回路总数。对m用数学归纳法。当m=1时，显然成立。设m=k时，定理成立。证明m=k＋1时定理成立。因为，故而是结点vi到vp长度为k的通路数目，apj是结点vp到vj长度为1的通路数目，故是从结点vi经过vp到结点vj的长度为k＋1的通路数目，那么是从结点vi到结点vj的长度为k＋1的通路数目。定理6.3证明解题小贴士——结点vi到vj长度m的通路数目的计算写出邻接矩阵A计算A的m次幂A

mA

m中第

i行第

j列元素即为所求例6.18求下图中图G1和G2的从结点v1到结点v3长度为2和3的通路数目及所有长度为2和3的通路数目。v4v2v1v3G1v1v4v2v3G2例6.18解在图中，G1是无向线图，G2是有向线图，它们的邻接矩阵分别为：

例6.18解下面计算邻接矩阵的幂，

因而G1中从结点v1到结点v3长度为2通路数目为1，长度为2的通路（含回路）总数为21，其中9条为回路。例6.18解G2中从结点v1到结点v3长度为2通路数目为2，长度为2的通路（含回路）总数为13，其中5条为回路。例6.18解因而G1中从结点v1到结点v3长度为3的通路数目为2，长度为3的通路（含回路）总数为48，其中10条为回路。例6.18解G2中从结点v1到结点v3长度为3的通路数目为4，长度为3的通路（含回路）总数为22，其中4条为回路。６.４.３可达与距离定义定义6.15在图G=<V,E>中，vi,vj∈V。（1）如果vi到vj存在通路，则称vi到vj是可达的，否则称vi到vj不可达。

规定：任何结点到自己都是可达的。（2）如果vi到vj可达，则称长度最短的通路为vi到vj的短程线(Geodesic)；vi到vj的短程线的长度称为vi到vj的距离(Distance)，记为d(vi,vj)。如果vi到vj不可达，则通常记为d(vi,vj)=∞。d(vi,vj)满足下列性质：

d(vi,vj)≥0；

d(vi,vk)＋d(vk,vj)≥d(vi,vj)。对于无向图，一定有若vi到vj可达，则vj到vi可达；也有d(vi,vj)=d(vj,vi)。对于有向图，vi到vj可达，不一定有vj到vi可达；也不一定有d(vi,vj)=d(vj,vi)。

d(vi,vi)=0；说明在图G1中，d(v1,v2)=2，d(v2,v1)=1，d(v4,v1)=d(v1,v4)=1， d(v2,v4)=2，d(v4,v2)=3在图G2中，d(v1,v3)=2，d(v3,v4)=1，d(v2,v4)=2

v1v4v2v3e7e6e1e4e5e3e2G1v2v5v3v4e2e3e4e5e6e7e1G2v1e8定理6.4在一个具有n个结点的图中，如果从结点vi到结点vj（vi≠

vj）存在一条通路，则从vi到vj存在一条长度不大于n-1的通路。证明设为从vi到vj的长度为k的一条通路，其中=vi，=vj，此通路上有k+1个结点。若k≤n-1，这条通路即为所求。若k＞n-1，则此通路上的结点数k+1＞n，由鸽笼原理知，必存在一个结点在此通路中不止一次出现，设，其中，0≤s＜t≤k。去掉到中间的通路，至少去掉一条边，得通路，此通路比原通路的长度至少少1。如此重复进行下去，必可得一条从vi到vj的长度不大于n-1的通路。几个结论推论6.2

在一个具有n个结点的图中，如果从结点vi到结点vj（vi≠vj）存在一条通路，则从vi到vj存在一条长度不大于n-1的基本通路。定理6.5

在一个具有n个结点的图中，如果存在经过结点vi回路，则存在一条经过vi的长度不大于n的回路。推论6.3

在一个具有n个结点的图中，如果存在经过结点vi回路，则存在一条经过vi的长度不大于n的基本回路。利用邻接矩阵判断可达利用定理6.4和定理6.5，我们可以通过计算图的邻接矩阵及其幂的方法来判断vi到vj是否可达，以及vi到vj的距离。设矩阵

Bm=I＋A＋A2＋A3＋…＋Am

（I为n阶单位阵）则Bm中的元素表示图G中结点vi到结点vj的长度小于等于m的通路总数，若i=j，为G中结点vi到自身的长度小于等于m的回路总数。定理6.6设G=<V,E>为线图，V={v1,v2,…,vn}，A

=(aij)n×n为G的邻接矩阵，Am=()n×n

，m=1,2,…,n-1；Bn-1=()n×n=I+A+A2+A3+…+An-1。则有：如果＞0，那么vi到vj可达，否则不可达；并且解题小贴士——结点间可达的判断与距离的计算使用定理6.6，利用邻接矩阵及其幂与和的计算即可。例6.19判断右图中图G中结点之间的可达关系，并求任两结点间的距离。计算图G的邻接矩阵及其2、3次幂分别为：v1v4v2v3d(v1,v2)=d(v1,v3)=d(v2,v1)=d(v2,v3)=d(v2,v4)=d(v3,v1)=1d(v1,v4)=d(v3,v2)=2d(v3,v4)=3d(v4,v1)=d(v4,v2)=d(v4,v3)=∞例6.19计算v1到v1,v2,v3,v4都是可达的；v2到v1,v2,v3,v4都是可达的；v3到v1,v2,v3,v4都是可达的；v4到v4都是可达的，v4到v1,v2,v3都是不可达的。定义6.16设G=<V,E>是一个线图，其中V={v1,v2,...,vn}，并假定结点已经有了从v1到vn的次序，称n阶方阵P=(pij)n×n为图G的可达性矩阵(AccessibilityMatrix)，其中 i,j=1,2,…,n，可达无向图的可达性矩阵是对称的，而有向图的可达性矩阵则不一定对称。与邻接矩阵不同，可达性矩阵不能给出图的完整信息，但由于它简便，在应用上还是很重要的。v1v4v2v3v1v4v2v3确定矩阵P中元素如果我们知道矩阵Bn-1，则只需将其中的非零元素写成1，就可得到可达性矩阵，即例6.19图v1v4v2v3定理6.7设G=<V,E>为线图，A、P分别是G的邻接矩阵和可达性矩阵，则有这里，A(i)表示做矩阵布尔积的i次幂。解题小贴士——可达性矩阵的计算使用定理6.7，利用邻接矩阵及其布尔乘积与布尔并的计算即可。例6.20求右图中图G中的可达性矩阵。解图G的邻接矩阵及其2、3次布尔乘法幂分别为：v1v4v2v3与我们利用B3求得的结果完全一致6.4.4无向赋权图的最短通路在赋权图中，边的权也称为边的长度，一条通路的长度指的就是这条通路上各边的长度之和。从结点vi到vj的长度最小的通路，称为vi到vj的最短通路。1.求给定两结点间的最短通路——Dijkstra算法如何求出简单无向赋权图G＝<V,E>中从结点v1到vn的最短通路，目前公认最好的算法是由迪杰斯特拉（Dijkstra）在1959年提出的，称为Dijkstra算法，其基本思想如下。将结点集合V分为两部分：一部分称为具有P（永久性）标号的集合，另一部分称为具有T（暂时性）标号的集合。所谓结点v的P标号是指从v1到v的最短通路的长度；而结点u的T标号是指从v1到u的某条通路的长度（最短通路长度的上界）。首先将v1取为P标号，其余结点为T标号，然后逐步将具有T标号的结点改为P标号。当结点vn也被改为P标号时，则找到了从v1到vn的一条最短通路。算法6.1Dijkstra算法（1）初始化：将v1置为P标号，d(v1)＝0，P＝{v1}，

vi∈V，i≠1，置vi为T标号，即T＝V－P且（2）找最小：寻找具有最小值的T标号的结点。若为vk，则将vk的T标号改为P标号，且P＝P∪{vk}，T＝T－{vk}。（3）修改：修改与vk相邻的结点的T标号值。

vi∈V，（4）重复（2）和（3），直到vn改为P标号为止。说明当vn归入P而正好P=V时，不仅求出了从v1到vn的最短通路，而且实际上求出了从v1到所有结点的最短通路。上述算法的正确性是显然的。因为在每一步，设P中每一结点的标号是从v1到该结点的最短通路的长度（开始时，P={v1}，d(v1)=0，这个假设是正确的），故只要证明上述d(vi)是从v1到vi的最短通路的长度即可。事实上，任何一条从v1到vi通路，若通过T的第一个结点是vp，而vp≠vi的话，由于所有边的长度非负，则这种通路的长度不会比d(vi)小。例6.21求简单无向赋权图中v1到v6的最短通路。解根据Dijkstra算法，求解过程如下。v1v3v21v5v4v6122457364(v1)1(v1)∞

∞∞

003(v1,v2)(v1)∞

6(v1,v2)8(v1,v2)103(v1)∞

4(v1,v2,v3)8(v1,v2)1(v1,v2)03(v1)4(v1,v2,v3)1(v1,v2)47(v1,v2,v3,v5)10(v1,v2,v3,v5)03(v1)4(v1,v2,v3)1(v1,v2)4(v1,v2,v3,v5)9(v1,v2,v3,v5,v4)7故v1到v6的最短通路为v1v2v3v5v4v6，其长度为9。实际上，也求出了v1到所有结点的最短通路，例如，v1到v5的最短通路为v1v2v3v5，其长度为4，等等。2.求任意两结点间的最短通路——Floyd算法算法6.2Floyd算法从矩阵D(0)＝(wij)n×n（这里wij＝w(vi,vj)，称为图的长度矩阵）开始，依次构造出n个矩阵D(1),D(2),…,D(n)，这里n为图中结点的个数。第k个矩阵D(k)＝()n×n的元素

表示从结点vi到vj而中间结点仅属于v1到vk的k个结点的所有通路中的最短通路长度。若已知D(k-1)＝()n×n，则D(k)＝()n×n的元素规定为运算过程从k＝1开始，让i和

j分别取遍从1到n的所有值，然后k增加1，如此反复进行，直到k＝n为止。这时D(n)＝()n×n的元素

就是从vi到vj的最短通路长度。算法的正确性是显然的。Floyd算法算法求出了任意两个结点间的最短通路的长度，从而很容易得出相应的最短通路。例6.22求简单无向赋权图中的所有最短通路。解根据根据Floyd算法，有：v1v4v21v5v3v634221322故v2到v6的最短通路长度为5，其最短通路为v2v3v6，其余类似。内容导航CONTENTS历史人物本章导读及学习要求图的基本概念握手定理图的同构图的连通性

6.1

6.2

6.3

6.4作业

6.5图的应用通路与回路

6.7

6.66.5.1无向图的连通性定义6.17若无向图G中的任何两个结点都是可达的，则称G是连通图(ConnectedGraph)，否则称G是非连通图(UnconnectedGraph)或分离图(SeparatedGraph)。

无向完全图Kn（n≥1）都是连通图，而多于一个结点的零图都是非连通图。

利用邻接矩阵A和可达性矩阵P，显然有：

非平凡无向线图G是连通图当且仅当它的可达性矩阵P的所有元素均为1。6.5.1无向图的连通性定义9.3.4若无向图G中的任何两个结点都是可达的，则称G是连通图(ConnectedGraph)，否则称G是非连通图(UnconnectedGraph)或分离图(SeparatedGraph)。无向完全图Kn（n≥1）都是连通图多于一个结点的零图都是非连通图非平凡无向线图G是连通图当且仅当它的可达性矩阵P的所有元素均为1。定理6.8无向图G=<V,E>中结点之间的可达关系R定义如下：R={<u,v>|u,v∈V，u到v可达}