《离散数学》课件-第7章 图论.pdf

云南大学滇池学院《离散数学》 第9章 图论 第7章 图论 • 7.1 图的基本概念 • 7.2 路与回路 以及图的连通性 • 7.3 图的矩阵表示 • 7.4 欧拉图与汉密尔顿图 • 7.5 平面图（含二部图及匹配） • 7.6 树与生成树 • 7.7 根树及其应用 返回总目录 云南大学滇池学院《离散数学》 第9章 图论 第7章 图论 图论是一个重要的数学分支。数学家欧拉1736年发 表了关于图论的第一篇论文，解决了著名的哥尼斯堡七 桥问题。克希霍夫对电路网络的研究、凯来在有机化学 的计算中都应用了树和生成树的概念。随着科学技术的 发展，图论在运筹学、网络理论、信息论、控制论和计 算机科学等领域都得到广泛的应用。本章首先给出图、 简单图、完全图、子图、路和图的同构等概念，接着研 究了连通图性质和规律，给出了邻接矩阵、可达性矩阵、 连通矩阵和完全关联矩阵的定义。最后将介绍欧拉图与 哈密尔顿图、二部图、平面图和图的着色、树和根树。 返回章目录 云南大学滇池学院《离散数学》 第9章 图论 7.1 图的基本概念 • 7.1.1 图的基本概念 • 7.1.2 图的结点的度数及其性质 • 7.1.3 简单图、多重图、完全图和正则图 • 7.1.4 图的同构 • 7.1.5 补图、子图和生成子图 云南大学滇池学院《离散数学》 第9章 图论 现实世界中许多现象能用某种图形表示,这种图形是由 一些点和一些连接两点间的连线所组成。 【引例】a，b ，c，d 4个篮球队进行友谊比赛。为了表示４个 队之间比赛的情况，我们作出图 7.1.1的图形。在图中４个小圆 圈分别表示这４个篮球队，称之为结点 （亦可叫顶点）。如果两 队进行过比赛，则在表示该队的两个结点之间用一条线连接起来， 称之为边。这样利用一个图形使各队之间的比赛情况一目了然。 图7.1.1 云南大学滇池学院《离散数学》 第9章 图论 如果图 7.1.1中的４个结点a，b ，c，d分别表示４个 人，当某两个人互相认识时，则将其对应点之间用边连接 起来。这时的图又反映了这４个人之间的认识关系。 我们也可以点代表工厂, 以连接两点的连线表示这两工 厂间有业务往来关系。这样便可用图形表示某一城市中各 工厂间的业务往来关系。 这种用图形来表示事物之间的某种关系的方法我们也 曾经在二元关系一章中使用过。对于这种图形,我们的兴趣 在于有多少个点和哪些点对间有线连接,至于连线的长短曲 直和点的位置都无关紧要。对它们进行数学抽象我们就得 到以下作为数学概念的图的定义。 云南大学滇池学院《离散数学》 第9章 图论 7.1图的基本概念  无序对与多重集合 无序对: 2个无顺序关系的元素a和b构成的序偶, 记为(a, b) 【注】：在无序对(a,b) 中，a,b是无序的，它们的顺序可 以颠倒，即(a, b)=(b, a) 。 无序积: AB={(x,y ) | x Ay B} 例如 A={a,b,c}, B={1,2} AB=BA={(a,1), (b,1), (c,1), (a,2), (b,2), (c,2)} AA={(a,a), (a,b), (a,c), (b,b), (b,c), (c,c)} BB={(1,1),