(1.8)--离散数学离散数学.ppt

《(1.8)--离散数学离散数学.ppt》由会员分享，可在线阅读，更多相关《(1.8)--离散数学离散数学.ppt（102页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2024/1/202024/1/20离散数学离散数学1 1离 散 数 学2024/1/202024/1/20离散数学离散数学2 2图论图论图论图论(Graph Theory)(Graph Theory)(Graph Theory)(Graph Theory)是一新的数学分支，也是一门很有实用价值的学是一新的数学分支，也是一门很有实用价值的学是一新的数学分支，也是一门很有实用价值的学是一新的数学分支，也是一门很有实用价值的学 科，它在自然科学、社会科学等各领域均有很多科，它在自然科学、社会科学等各领域均有很多科，它在自然科学、社会科学等各领域均有很多科，它在自然科学、社会科学等各领域均有很多应用

2、。应用。应用。应用。图论的产生和发展历经了二百多年的历史，大图论的产生和发展历经了二百多年的历史，大图论的产生和发展历经了二百多年的历史，大图论的产生和发展历经了二百多年的历史，大体上，可以划分为三个阶段体上，可以划分为三个阶段体上，可以划分为三个阶段体上，可以划分为三个阶段u第一阶段是从第一阶段是从第一阶段是从第一阶段是从1736173617361736年到年到年到年到19191919世纪中叶（萌芽阶段）世纪中叶（萌芽阶段）世纪中叶（萌芽阶段）世纪中叶（萌芽阶段）多数问题是围绕着游戏产生的，代表性的著名多数问题是围绕着游戏产生的，代表性的著名多数问题是围绕着游戏产生的，代表性的著名多数问题是

3、围绕着游戏产生的，代表性的著名的瑞士数学家的瑞士数学家的瑞士数学家的瑞士数学家EulerEulerEulerEuler于于于于1736173617361736年的年的年的年的K K K K nisbergnisbergnisbergnisberg七桥问七桥问七桥问七桥问题（第一篇图论论文）题（第一篇图论论文）题（第一篇图论论文）题（第一篇图论论文）（匹配问题）（匹配问题）（匹配问题）（匹配问题）2024/1/202024/1/20离散数学离散数学3 3u第二阶段从第二阶段从19世纪中叶到世纪中叶到1936年（发展与成熟）年（发展与成熟）这个时期中图论问题大量出现，如四色问题这个时期中图论问题大

4、量出现，如四色问题(1852年年)和和Hamilton问题问题(1856年年)同时出现了以图同时出现了以图为工具去解决其它领域中一些问题的成果最有代为工具去解决其它领域中一些问题的成果最有代表性的工作是表性的工作是Kirchhoff(1847年年)和和Cayley(1857年年)分分别用树的概念去研究电网络方程组问题和有机化合别用树的概念去研究电网络方程组问题和有机化合物的分子结构问题物的分子结构问题“图图(Graph)这个词第一次出现是在这个词第一次出现是在1878年的英年的英国国自然自然杂志中杂志中1936年匈牙利数学家年匈牙利数学家DKnig写出了第一本写出了第一本图论专著图论专著有限图

5、与无限图的理论有限图与无限图的理论图论作为数图论作为数学的一个新分支已基本形成学的一个新分支已基本形成2024/1/202024/1/20离散数学离散数学4 4u1936年以后是第三阶段年以后是第三阶段(广泛应用）广泛应用）由于生产管理、军事、交通运输、计算机和通讯由于生产管理、军事、交通运输、计算机和通讯网络等方面许多离散性问题的出现，大大促进了图网络等方面许多离散性问题的出现，大大促进了图论的发展论的发展进入进入70年代以后，特别是大型电子计算机的出年代以后，特别是大型电子计算机的出现，使大规模问题的求解成为可能图的理论及其现，使大规模问题的求解成为可能图的理论及其在物理、化学、运筹学、计

6、算机科学、电子学、信在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域中各方面应用的研究都得到几乎所有学科领域中各方面应用的研究都得到“爆爆炸性发展炸性发展”主要有以下三个原因：主要有以下三个原因：2024/1/202024/1/20离散数学离散数学5 51.图论提供了一个图论提供了一个自然的结构自然的结构，由此而产生的数学，由此而产生的数学模型几乎适合于所有科学模型几乎适合于所有科学(自然科学和让会科学自然科学和让会科学)领领域，只要这个领域研究的主题是域，只要这个领域研究的主题是“对象对象”和

7、和“对象对象”之间的关系之间的关系2.图论已形成自己的丰富词汇语言，它能图论已形成自己的丰富词汇语言，它能简洁地简洁地表表示出各个领域中示出各个领域中“对象关系对象关系”结构复杂而又难结构复杂而又难懂的概念懂的概念3图论提供了大量令人跃跃欲试的图论提供了大量令人跃跃欲试的智力挑战性问智力挑战性问题题，小到初学者的简单习题，大到能使所有资深数，小到初学者的简单习题，大到能使所有资深数学家感到棘手且悬而未决的难题学家感到棘手且悬而未决的难题2024/1/202024/1/20离散数学离散数学6 6图论在计算机科学中扮演着重要的角色。如图论在计算机科学中扮演着重要的角色。如在形式语言、数据结构、分布

8、式系统、操在形式语言、数据结构、分布式系统、操作系统等方面。作系统等方面。2024/1/202024/1/20离散数学离散数学7 7图论中的第一个问题：图论中的第一个问题：哥尼斯堡七桥问题哥尼斯堡七桥问题欧拉欧拉欧拉欧拉于于于于17361736年解决了此问题，从而使他成了图论和年解决了此问题，从而使他成了图论和年解决了此问题，从而使他成了图论和年解决了此问题，从而使他成了图论和拓扑学的创始人。拓扑学的创始人。拓扑学的创始人。拓扑学的创始人。2024/1/202024/1/20离散数学离散数学8 8u问题：从某陆地出发，找经过每座桥恰好一次，问题：从某陆地出发，找经过每座桥恰好一次，回到出发地的

9、路线。回到出发地的路线。uEuler（欧拉）的解：（欧拉）的解：抽象：陆地抽象：陆地点点桥桥边边图图DACB求解：求解：图论诞生了！图论诞生了！2024/1/202024/1/20离散数学离散数学9 9哈密顿环游世界游戏与哈密顿问题哈密顿环游世界游戏与哈密顿问题哈密顿是哈密顿是18世纪英国的一位爵士世纪英国的一位爵士,他发明了一个环他发明了一个环游世界的游戏游世界的游戏,该游戏以该游戏以5英镑卖给了一个经销商英镑卖给了一个经销商.正十二面体正十二面体点表示世界点表示世界的的20个城市个城市边表示路线边表示路线是否存在是否存在从一城市从一城市出发经过出发经过每个城市每个城市恰好一次恰好一次有回到

10、出有回到出发城市的发城市的旅游路线旅游路线?一个图如果存在这样的路线一个图如果存在这样的路线,称为称为哈密顿图哈密顿图.2024/1/202024/1/20离散数学离散数学1010哈密顿环游世界游戏与哈密顿问题哈密顿环游世界游戏与哈密顿问题哈密顿是哈密顿是18世纪英国的一位爵士世纪英国的一位爵士,他发明了一个环他发明了一个环游世界的游戏游世界的游戏,该游戏以该游戏以5英镑卖给了一个经销商英镑卖给了一个经销商.一个图如果存在这样的路线一个图如果存在这样的路线,称为称为哈密顿图哈密顿图.经典问题经典问题2024/1/202024/1/20离散数学离散数学11111.四色猜想：四色猜想：世界近代三大

11、数学难题之一。四色猜想的提出世界近代三大数学难题之一。四色猜想的提出来自英国。来自英国。1852年，毕业于伦敦大学的弗南西斯年，毕业于伦敦大学的弗南西斯.格思里来到一家科研单位搞地图着色工作时，发现格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：了一种有趣的现象：“看来，每幅地图都可以用四看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜种颜色着色，使得有共同边界的国家着上不同的颜色。色。”这个结论能不能从数学上加以严格证明呢？这个结论能不能从数学上加以严格证明呢？许多数学家绞尽脑汁许多数学家绞尽脑汁难于解决。于是，人们难于解决。于是，人们开始认识到，这个貌似容

12、易的题目，其实是一个可开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题：先辈数学大师们的努力，与费马猜想相媲美的难题：先辈数学大师们的努力，为后世的数学家揭示四色猜想之谜铺平了道路。为后世的数学家揭示四色猜想之谜铺平了道路。图论与计算机科学的问题图论与计算机科学的问题图论与计算机科学的问题图论与计算机科学的问题2024/1/202024/1/20离散数学离散数学12121976年，美国数学家阿佩尔与哈肯在美国伊利年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了诺斯大学的两台不同的电子计算机上，用了1200个个小时，作了小时，作了100亿判断，终于完成

13、了四色定理的证亿判断，终于完成了四色定理的证明。四色猜想的计算机证明，轰动了世界。明。四色猜想的计算机证明，轰动了世界。它不仅解决了一个历时它不仅解决了一个历时100多年的难题，而且多年的难题，而且有可能成为数学史上一系列新思维的起点。有可能成为数学史上一系列新思维的起点。不过也有不少数学家并不满足于计算机取得的不过也有不少数学家并不满足于计算机取得的成就，他们还在寻找一种简捷明快的书面证明方法。成就，他们还在寻找一种简捷明快的书面证明方法。2006年年5月，哲学家黎鸣在其博客上发表的文月，哲学家黎鸣在其博客上发表的文章章感谢老子，我发现了感谢老子，我发现了“四色四色”难题终获难题终获简洁而绝

14、妙证明简洁而绝妙证明（http:/ 搜索引擎搜索引擎l研究方法之一：研究方法之一：图论：图论：The World Wide Web can be modeled as a directed graph in which a node represents a Web page and an edge represents a hyperlink.。2024/1/202024/1/20离散数学离散数学1818目前目前web图图的模型的模型有若干有若干种。种。2024/1/202024/1/20离散数学离散数学1919第九章第九章 图的基本概念图的基本概念 9.19.1 无向图及有向图无向图及有向

15、图无向图及有向图无向图及有向图 9.29.2 通路、回路、图的连通性通路、回路、图的连通性通路、回路、图的连通性通路、回路、图的连通性 9.39.3 图的矩阵表示图的矩阵表示图的矩阵表示图的矩阵表示 2024/1/202024/1/20离散数学离散数学20201.1.1.1.图图图图:表示若干事物之间具有的某种关系的图表示若干事物之间具有的某种关系的图表示若干事物之间具有的某种关系的图表示若干事物之间具有的某种关系的图.例例例例:若有若有若有若有A,B,C,D,EA,B,C,D,EA,B,C,D,EA,B,C,D,E五个人五个人五个人五个人,他们之间相互认识的情况为他们之间相互认识的情况为他们

16、之间相互认识的情况为他们之间相互认识的情况为:A:A:A:A与与与与C C C C、D D D D、E E E E认识认识认识认识;B;B;B;B与与与与C C C C、E E E E认识认识认识认识;C;C;C;C与与与与A A A A、D D D D认识认识认识认识;D;D;D;D与与与与A A A A、C C C C、E E E E认识认识认识认识;E;E;E;E与与与与A A A A、B B B B、D D D D认识认识认识认识.我们用我们用点点分别表示分别表示人人,相互相互认识认识用用线线连接连接,就得到下就得到下面的图面的图:ABCED9.1 9.1 无向图及有向图无向图及有向图

17、2024/1/202024/1/20离散数学离散数学2121 则则则则A A&B B=(1,3),(1,4),=(1,3),(1,4),(2,3),(2,4)(2,3),(2,4)，一、无向图及相关概念2 2、无向图、无向图、无向图、无向图如：如：如：如：A A=1,2=1,2，B B=3,4=3,4，无序积：无序积：无序积：无序积：设设设设A A,B B是两个集合，称是两个集合，称是两个集合，称是两个集合，称a a,b b|a a A A b b B B 为为为为A A与与与与B B的无序积，记作的无序积，记作的无序积，记作的无序积，记作A A&B B。习惯上记习惯上记习惯上记习惯上记 a

18、a,b b 为为为为(a a,b b)，有序对记为，有序对记为，有序对记为，有序对记为 。无论无论无论无论a a,b b取值如何，恒有取值如何，恒有取值如何，恒有取值如何，恒有(a a,b b)=()=(b b,a a)A A&A A=(1,1),(1,2),(2,2)=(1,1),(1,2),(2,2)。2024/1/202024/1/20离散数学离散数学2222一、一、无向图及相关概念无向图及相关概念（续）（续）无向图：无向图：无向图：无向图：无向图无向图无向图无向图G G是一个二元组是一个二元组是一个二元组是一个二元组 ，其中其中其中其中(1)(1)V V是一个非空集合，称为顶点集是一个

19、非空集合，称为顶点集是一个非空集合，称为顶点集是一个非空集合，称为顶点集V V(G G)，V V中中中中元素称为顶点元素称为顶点元素称为顶点元素称为顶点(vertexvertexvertexvertex)或结点；或结点；或结点；或结点；(2)(2)E E是无序积是无序积是无序积是无序积V V&V V的多重子集的多重子集的多重子集的多重子集(即集合中即集合中即集合中即集合中 的的的的元素可重复出现元素可重复出现元素可重复出现元素可重复出现)，称为边集，称为边集，称为边集，称为边集E E(G G)，E E中元素称为无向边，简称边中元素称为无向边，简称边中元素称为无向边，简称边中元素称为无向边，简称

20、边(edgeedgeedgeedge)。GraphTheoryGraphTheory图论图论图论图论2024/1/202024/1/20离散数学离散数学2323实际上，图是画出来的。实际上，图是画出来的。实际上，图是画出来的。实际上，图是画出来的。画法画法画法画法：用小圆圈表示：用小圆圈表示：用小圆圈表示：用小圆圈表示V V中中中中顶点，若顶点，若顶点，若顶点，若(a a,b b)E E，则在顶点则在顶点则在顶点则在顶点a a与与与与b b之间连线段。之间连线段。之间连线段。之间连线段。如：如：如：如：G G=，V V=v v1 1,v v2 2,v v3 3,v v44，E E=(v v1

21、1,v v2 2),(),(v v1 1,v v4 4),(),(v v2 2,v v1 1),(),(v v2 2,v v3 3),(),(v v2 2,v v3 3),(),(v v3 3,v v4 4)v v4 4v v3 3v v2 2e e1 1e e2 2e e3 3e e4 4e e5 5e e6 6v v1 1一、一、无向图及相关概念无向图及相关概念（续）（续）2024/1/202024/1/20离散数学离散数学2424完全完全二部图二部图(偶图偶图)Km,n:K3,2K3,3路路Pn:P5二部图与鸡尾酒会二部图与鸡尾酒会二部图与鸡尾酒会二部图与鸡尾酒会2024/1/20202

22、4/1/20离散数学离散数学2525一个图的图形表示法可能不是唯一的。一个图的图形表示法可能不是唯一的。一个图的图形表示法可能不是唯一的。一个图的图形表示法可能不是唯一的。表示结点的圆点和表示边的线，它们的相对位置表示结点的圆点和表示边的线，它们的相对位置表示结点的圆点和表示边的线，它们的相对位置表示结点的圆点和表示边的线，它们的相对位置是没有实际意义的。因此，对于同一个图，可能画是没有实际意义的。因此，对于同一个图，可能画是没有实际意义的。因此，对于同一个图，可能画是没有实际意义的。因此，对于同一个图，可能画出很多表面不一致的图形来。出很多表面不一致的图形来。出很多表面不一致的图形来。出很多

23、表面不一致的图形来。下面三个图实际上是一个：下面三个图实际上是一个：下面三个图实际上是一个：下面三个图实际上是一个：v1v2v3v4v4v3v1v2v2v3v4v12024/1/202024/1/20离散数学离散数学2626有限图：有限图：有限图：有限图：V V,E E均为有限集。均为有限集。均为有限集。均为有限集。3 3、相关概念、相关概念、相关概念、相关概念 n n 阶图：阶图：阶图：阶图：|V V|=n n。零图：零图：零图：零图：E E=。平凡图：平凡图：平凡图：平凡图：E E=且且且且|V V|=1=1。孤立点：孤立点：孤立点：孤立点：与任何边都不关联的顶点。与任何边都不关联的顶点。

24、与任何边都不关联的顶点。与任何边都不关联的顶点。环：环：环：环：e ek k=(=(v vi i,v vj j)中，若中，若中，若中，若v vi i=v vj j，则称，则称，则称，则称e ek k为环。为环。为环。为环。一、一、无向图及相关概念无向图及相关概念（续）（续）2024/1/202024/1/20离散数学离散数学2727v1v2v3v4v5顶点与顶点的相邻：顶点与顶点的相邻：顶点与顶点的相邻：顶点与顶点的相邻：若若若若e ek k=(=(v vi i,v vj j)E E，称称称称v vi i 与与与与v vj j 相邻。相邻。相邻。相邻。边与边的相邻：边与边的相邻：边与边的相邻：

25、边与边的相邻：若若若若e ek k 和和和和e el l 至少有一个公共端点，至少有一个公共端点，至少有一个公共端点，至少有一个公共端点，则则则则称称称称e ek k与与与与e el l 相邻。相邻。相邻。相邻。一、一、无向图及相关概念无向图及相关概念（续）（续）顶点与边的关联：顶点与边的关联：顶点与边的关联：顶点与边的关联：若若若若e ek k=(=(v vi i,v vj j)E E，称称称称e ek k与与与与v vi i(v vj j)关联。关联。关联。关联。2024/1/202024/1/20离散数学离散数学2828平行边：平行边：平行边：平行边：无向图中，关联一对顶点的无向边多于无

26、向图中，关联一对顶点的无向边多于无向图中，关联一对顶点的无向边多于无向图中，关联一对顶点的无向边多于1 1条，条，条，条，称这些边为平行边。平行边的条数称为重数。称这些边为平行边。平行边的条数称为重数。称这些边为平行边。平行边的条数称为重数。称这些边为平行边。平行边的条数称为重数。有向图中，关联一对顶点的有向边多于有向图中，关联一对顶点的有向边多于有向图中，关联一对顶点的有向边多于有向图中，关联一对顶点的有向边多于1 1条，条，条，条，并且有向边的始点和终点相同，并且有向边的始点和终点相同，并且有向边的始点和终点相同，并且有向边的始点和终点相同，称这些边为平行边。称这些边为平行边。称这些边为平

27、行边。称这些边为平行边。多重图：多重图：多重图：多重图：含平行边的图。含平行边的图。含平行边的图。含平行边的图。简单图：简单图：简单图：简单图：既不含平行边也不含环的图。既不含平行边也不含环的图。既不含平行边也不含环的图。既不含平行边也不含环的图。一、一、无向图及相关概念无向图及相关概念（续）（续）2024/1/202024/1/20离散数学离散数学29293 3、无向图中的度：无向图中的度：无向图中的度：无向图中的度：(1)(1)(1)(1)设设设设G=G=为为为为无向图，与顶点无向图，与顶点无向图，与顶点无向图，与顶点v vi i 关联的边的条关联的边的条关联的边的条关联的边的条数数数数(

28、每个环计算两次每个环计算两次每个环计算两次每个环计算两次)称为称为称为称为v vi i 的的的的度度度度，记作，记作，记作，记作d d(v vi i)。奇点奇点-度数为奇数的点度数为奇数的点偶点偶点-度数为偶数的点度数为偶数的点一、一、无向图及相关概念无向图及相关概念（续）（续）2024/1/202024/1/20离散数学离散数学3030(2)(2)最大度：最大度：最大度：最大度：(3)(3)最小度：最小度：最小度：最小度：(G G)=max maxd d(v v)|)|v v V V (G G)=min mind d(v v)|)|v v V V(4)(4)度与边数的关系：度与边数的关系：度

29、与边数的关系：度与边数的关系：(握手定理握手定理握手定理握手定理)图论中的第一个定理图论中的第一个定理图论中的第一个定理图论中的第一个定理任何图中，顶点度数之和等于边数之和的两倍。任何图中，顶点度数之和等于边数之和的两倍。任何图中，顶点度数之和等于边数之和的两倍。任何图中，顶点度数之和等于边数之和的两倍。即：即：即：即：推论：推论：推论：推论：任何图中，度为奇数的顶点个数为偶数。任何图中，度为奇数的顶点个数为偶数。任何图中，度为奇数的顶点个数为偶数。任何图中，度为奇数的顶点个数为偶数。一、一、无向图及相关概念无向图及相关概念（续）（续）2024/1/202024/1/20离散数学离散数学313

30、1例例例例2 2：已知图：已知图：已知图：已知图G G有有有有1010条边，条边，条边，条边，4 4个个个个3 3度的顶点，其余顶点度的顶点，其余顶点度的顶点，其余顶点度的顶点，其余顶点 的度数均小于等于的度数均小于等于的度数均小于等于的度数均小于等于2 2，问，问，问，问G G至少有多少个顶点。至少有多少个顶点。至少有多少个顶点。至少有多少个顶点。设设设设G G含有含有含有含有x x个顶点，图个顶点，图个顶点，图个顶点，图G G边数为边数为边数为边数为1010，由握手定理知，由握手定理知，由握手定理知，由握手定理知，G G 中各顶点度数之和为中各顶点度数之和为中各顶点度数之和为中各顶点度数之

31、和为2020，则，则，则，则 43+(43+(x x-4)-4)220220，x x88,故故故故G G有有有有至少至少至少至少8 8个顶点。个顶点。个顶点。个顶点。解：解：解：解：一、一、无向图及相关概念无向图及相关概念（续）（续）2024/1/202024/1/20离散数学离散数学3232设设设设V V=v v1 1,v v2 2,v vn n 为图为图为图为图G G的顶点集，的顶点集，的顶点集，的顶点集，称称称称(d d(v v1 1),),d d(v v2 2),),d d(v vn n)为为为为G G的度数序列。的度数序列。的度数序列。的度数序列。(5)(5)度数序列：度数序列：度数

32、序列：度数序列：一、一、无向图及相关概念无向图及相关概念（续）（续）例例例例1 1：下列哪些能成为图的度数序列。：下列哪些能成为图的度数序列。：下列哪些能成为图的度数序列。：下列哪些能成为图的度数序列。(1)2,2,2,3,3,(2)0,1,2,3,3,(3)1,3,4,4,5(1)2,2,2,3,3,(2)0,1,2,3,3,(3)1,3,4,4,5(1),(2),(3)(1),(2),(3)中度为奇数的顶点个数分别是中度为奇数的顶点个数分别是中度为奇数的顶点个数分别是中度为奇数的顶点个数分别是2,3,32,3,3，解：解：解：解：因此由握手定理因此由握手定理因此由握手定理因此由握手定理,而

33、而而而(2)(2)和和和和(3)(3)不能，不能，不能，不能，(1)(1)能构成图的度数序列能构成图的度数序列能构成图的度数序列能构成图的度数序列。2024/1/202024/1/20离散数学离散数学3333一、一、无向图及相关概念无向图及相关概念（续）（续）(补充）补充）奇点的数目为偶数只是图的度系列的必要条件，奇点的数目为偶数只是图的度系列的必要条件，奇点的数目为偶数只是图的度系列的必要条件，奇点的数目为偶数只是图的度系列的必要条件，ErdErd s s等给出了一个充分必要条件：等给出了一个充分必要条件：等给出了一个充分必要条件：等给出了一个充分必要条件：定理：定理：定理：定理：和为偶数的

34、系列和为偶数的系列和为偶数的系列和为偶数的系列dd1 1,d,d2 2,d,dn n(p-1(p-1 d d1 1 d d2 2 d dn n)是图的度系列当且仅当是图的度系列当且仅当是图的度系列当且仅当是图的度系列当且仅当dd2 2-1,d-1,d3 3-1,d-1,dd d1 1+1+1-1,d-1,dd d1 1+2+2,d,dn n 也是图的度系列。也是图的度系列。也是图的度系列。也是图的度系列。5,5,3,3,2,2,25,5,3,3,2,2,2 4,2,2,1,1,24,2,2,1,1,24,2,2,2,1,14,2,2,2,1,1 1,1,1,0,11,1,1,0,12024/1

35、/202024/1/20离散数学离散数学34345,5,3,3,2,2,25,5,3,3,2,2,2 4,2,2,1,1,24,2,2,1,1,24,2,2,2,1,14,2,2,2,1,1 1,1,1,0,11,1,1,0,12024/1/202024/1/20离散数学离散数学35354,3,3,3,2,2,2,14,3,3,3,2,2,2,12,2,2,1,2,2,12,2,2,1,2,2,12,2,2,2,2,1,12,2,2,2,2,1,11,1,2,2,1,11,1,2,2,1,12,2,1,1,1,12,2,1,1,1,11,0,1,1,11,0,1,1,12024/1/20202

36、4/1/20离散数学离散数学36364,3,3,3,2,2,2,14,3,3,3,2,2,2,12,2,2,1,2,2,12,2,2,1,2,2,12,2,2,2,2,1,12,2,2,2,2,1,11,1,2,2,1,11,1,2,2,1,12,2,1,1,1,12,2,1,1,1,11,0,1,1,11,0,1,1,12024/1/202024/1/20离散数学离散数学3737给定图唯一确定度系列，但反之不然。给定图唯一确定度系列，但反之不然。给定图唯一确定度系列，但反之不然。给定图唯一确定度系列，但反之不然。是否存在度系列唯一确定一个图呢？是否存在度系列唯一确定一个图呢？是否存在度系列唯

37、一确定一个图呢？是否存在度系列唯一确定一个图呢？回答是肯定的。回答是肯定的。回答是肯定的。回答是肯定的。结论：结论：结论：结论：每个有每个有每个有每个有4 4个元素的度系列唯一确定一个图；个元素的度系列唯一确定一个图；个元素的度系列唯一确定一个图；个元素的度系列唯一确定一个图；两个以上图对应的度系列至少含有两个以上图对应的度系列至少含有两个以上图对应的度系列至少含有两个以上图对应的度系列至少含有5 5个元素。个元素。个元素。个元素。3,2,2,13,2,2,12,2,2,22,2,2,22024/1/202024/1/20离散数学离散数学3838如果图如果图如果图如果图GG的每个点的度均为的每

38、个点的度均为的每个点的度均为的每个点的度均为k k，则称，则称，则称，则称GG为为为为k k正则图正则图正则图正则图。0 0正则图：正则图：正则图：正则图：1 1正则图：正则图：正则图：正则图：2 2正则图：正则图：正则图：正则图：圈圈圈圈C Cn n2024/1/202024/1/20离散数学离散数学39394 4、无向完全图无向完全图无向完全图无向完全图（完全图完全图完全图完全图）：）：）：）：设设设设G=G=是是是是n n 阶阶阶阶无向简单图，无向简单图，无向简单图，无向简单图，若若若若G G中任何顶点都与其余的中任何顶点都与其余的中任何顶点都与其余的中任何顶点都与其余的n n-1-1个

39、顶点相邻，个顶点相邻，个顶点相邻，个顶点相邻，则称则称则称则称G G 为为为为n n 阶阶阶阶无向完全图。记作无向完全图。记作无向完全图。记作无向完全图。记作K Kn n一、一、无向图及相关概念无向图及相关概念（续）（续）K Kn n的边数：的边数：的边数：的边数：2024/1/202024/1/20离散数学离散数学4040有向图：有向图：有向图：有向图：有向图有向图有向图有向图D D是一个二元组是一个二元组是一个二元组是一个二元组 ，其中其中其中其中(1)(1)V V是一个非空集合，称为顶点集是一个非空集合，称为顶点集是一个非空集合，称为顶点集是一个非空集合，称为顶点集V V(D D)；(2

40、)(2)E E是笛卡尔积是笛卡尔积是笛卡尔积是笛卡尔积V V V V的多重子集，的多重子集，的多重子集，的多重子集，称为边集称为边集称为边集称为边集E E(D D)，E E中元素称为有向边，中元素称为有向边，中元素称为有向边，中元素称为有向边，也简称边也简称边也简称边也简称边(弧，弧，弧，弧，arcarcarcarc)。1 1、有向图、有向图、有向图、有向图二、有向图及相关概念二、有向图及相关概念2024/1/202024/1/20离散数学离散数学4141二、有向图及相关概念（续）二、有向图及相关概念（续）有向图画法有向图画法有向图画法有向图画法：用小圆圈表示用小圆圈表示用小圆圈表示用小圆圈表

41、示V V中顶点，若中顶点，若中顶点，若中顶点，若 E E，则在顶点则在顶点则在顶点则在顶点a a与与与与b b之之之之间画一条有向边，其箭头从间画一条有向边，其箭头从间画一条有向边，其箭头从间画一条有向边，其箭头从a a指向指向指向指向b b。如：如：如：如：D D=，V V=v v1 1,v v2 2,v v3 3,v v4 4 ，E E=,v v4 4v v3 3v v2 2e e1 1e e2 2e e3 3e e4 4e e5 5e e6 6v v1 12024/1/202024/1/20离散数学离散数学4242一、基本图类与相关概念（续）一、基本图类与相关概念（续）有限图：有限图：有

42、限图：有限图：V V,E E均为有限集。均为有限集。均为有限集。均为有限集。2 2、相关概念、相关概念、相关概念、相关概念 n n 阶图：阶图：阶图：阶图：|V V|=n n。零图：零图：零图：零图：E E=。平凡图：平凡图：平凡图：平凡图：E E=且且且且|V V|=1=1。孤立点：孤立点：孤立点：孤立点：与任何边都不关联的顶点。与任何边都不关联的顶点。与任何边都不关联的顶点。与任何边都不关联的顶点。环：环：环：环：e ek k=中，若中，若中，若中，若v vi i=v vj j，则称，则称，则称，则称e ek k为环。为环。为环。为环。2024/1/202024/1/20离散数学离散数学4

43、343二、有向图类及相关概念（续）二、有向图类及相关概念（续）顶点与顶点的相邻：顶点与顶点的相邻：顶点与顶点的相邻：顶点与顶点的相邻：边与边的相邻：边与边的相邻：边与边的相邻：边与边的相邻：若若若若e ek k 和和和和e el l 至少有一个公共端点，至少有一个公共端点，至少有一个公共端点，至少有一个公共端点，则则则则称称称称e ek k与与与与e el l 相邻。相邻。相邻。相邻。若若若若e ek k为有向边，即为有向边，即为有向边，即为有向边，即e ek k=E E，称称称称v vi i 邻接到邻接到邻接到邻接到v vj j，v vj j邻接于邻接于邻接于邻接于v vi i。还称还称还称

44、还称v vi i 是是是是e ek k的始点，的始点，的始点，的始点，v vj j是是是是e ek k的终点。的终点。的终点。的终点。顶点与边的关联：顶点与边的关联：顶点与边的关联：顶点与边的关联：若若若若e ek k=E E，称称称称e ek k与与与与v vi i(v vj j)关联。关联。关联。关联。2024/1/202024/1/20离散数学离散数学4444二、有向图及相关概念（续）二、有向图及相关概念（续）平行边：平行边：平行边：平行边：有向图中，关联一对顶点的有向边多于有向图中，关联一对顶点的有向边多于有向图中，关联一对顶点的有向边多于有向图中，关联一对顶点的有向边多于1 1条，条

45、，条，条，并且有向边的始点和终点相同，并且有向边的始点和终点相同，并且有向边的始点和终点相同，并且有向边的始点和终点相同，称这些边为平行边。称这些边为平行边。称这些边为平行边。称这些边为平行边。多重图：多重图：多重图：多重图：含平行边的图。含平行边的图。含平行边的图。含平行边的图。简单图：简单图：简单图：简单图：既不含平行边也不含环的图。既不含平行边也不含环的图。既不含平行边也不含环的图。既不含平行边也不含环的图。2024/1/202024/1/20离散数学离散数学45453 3、有向图中的度：有向图中的度：有向图中的度：有向图中的度：以顶点以顶点以顶点以顶点v vi i 为终点为终点为终点为

46、终点的边的条数称为的边的条数称为的边的条数称为的边的条数称为v vi i 的的的的入度入度入度入度，记作，记作，记作，记作d d-(v vi i)。入度和出度之和称为顶点入度和出度之和称为顶点入度和出度之和称为顶点入度和出度之和称为顶点v vi i 的的的的度度度度，记作，记作，记作，记作d d(v vi i)。显然显然显然显然 d d(v vi i)=d d+(v vi i)+)+d d-(v vi i)。(1)(1)(1)(1)设设设设D=D=为为为为有向图，以顶点有向图，以顶点有向图，以顶点有向图，以顶点v vi i 为始点的边的为始点的边的为始点的边的为始点的边的条数称为条数称为条数称

47、为条数称为v vi i 的的的的出度出度出度出度，记作，记作，记作，记作d d+(v vi i)。二、有向图及相关概念（续）二、有向图及相关概念（续）2024/1/202024/1/20离散数学离散数学4646(2)(2)出度与入度的关系：出度与入度的关系：出度与入度的关系：出度与入度的关系：在有向图中，各顶点的入度之和等于各顶点在有向图中，各顶点的入度之和等于各顶点在有向图中，各顶点的入度之和等于各顶点在有向图中，各顶点的入度之和等于各顶点的出度之和。即：的出度之和。即：的出度之和。即：的出度之和。即：二、有向图及相关概念（续）二、有向图及相关概念（续）2024/1/202024/1/20离

48、散数学离散数学47474 4、有向完全图：有向完全图：有向完全图：有向完全图：设设设设D=D=是是是是n n 阶阶阶阶有向简单图，有向简单图，有向简单图，有向简单图，若对若对若对若对 u u,v v V V(u u v v)，既有有向边，既有有向边，既有有向边，既有有向边 ，又有又有又有又有有向边有向边有向边有向边 ，则称则称则称则称D D为为为为n n 阶阶阶阶有向完全图。有向完全图。有向完全图。有向完全图。二、有向图及相关概念（续）二、有向图及相关概念（续）2024/1/202024/1/20离散数学离散数学4848三、子图与母图三、子图与母图设设设设G=G=，G G =是两个是两个是两个

49、是两个图。图。图。图。1 1、若、若、若、若V V V V且且且且E E E E，则称则称则称则称G G 是是是是G G的的的的子图子图子图子图，G G是是是是G G 的的的的母图母图母图母图，记作，记作，记作，记作G G G G。一个图和二个子图一个图和二个子图一个图和二个子图一个图和二个子图2 2、若、若、若、若G G G G且且且且G G G G ，则称，则称，则称，则称G G 是是是是G G的的的的真子图真子图真子图真子图。2024/1/202024/1/20离散数学离散数学4949三、子图与母图设设设设G=G=，G G =是两个是两个是两个是两个图。图。图。图。3 3、若、若、若、若

50、E E E E且且且且V V =V V，则称，则称，则称，则称G G 是是是是G G的的的的生成子图生成子图生成子图生成子图。一个图的两个生成子图一个图的两个生成子图一个图的两个生成子图一个图的两个生成子图2024/1/202024/1/20离散数学离散数学5050三、子图与母图设设设设G=G=，G G =是两个是两个是两个是两个图。图。图。图。4 4、设、设、设、设V V11 V V且且且且V V1 1 ，以，以，以，以V V1 1为顶点集，为顶点集，为顶点集，为顶点集，以两端点均在以两端点均在以两端点均在以两端点均在V V1 1中的全体边为边集的中的全体边为边集的中的全体边为边集的中的全体