离散数学—图论1216版ppt课件

1、第8章 图论问题是要从这四块陆问题是要从这四块陆地中任何一块开始，地中任何一块开始，通过每一座桥正好一通过每一座桥正好一次，再回到起点。次，再回到起点。 欧拉在欧拉在17361736年解决了年解决了这个问题这个问题 。判定法则：如果通奇数座桥的地方不止两个，那么满足要求的路线便不存在了。如果只有两个地方通奇数座桥，则可从其中任何一地出发找到所要求的路线。若没有一个地 方通奇数座桥，则从任何一地出发，所求的路线都能实现 第8章 图论8.1.1 图图第8章 图论图 8.1-1第8章 图论第8章 图论第8章 图论第8章 图论图 8.13 第8章 图论第8章 图论第8章 图论11deg ()deg (

2、)2nniiiim1deg()2niim 证 因为每一条边提供两个次数,而所有各结点次数之和为m条边所提供,所以上式成立。在有向图中,上式也可写成: 第8章 图论121112deg()deg()deg()iinnniEOiiim 因为次数为偶数的各结点次数之和为偶数。所以前一项次数为偶数;若n2为奇数,则第二项为奇数,两项之和将为奇数,但这与上式矛盾。故n2必为偶数。证毕。第8章 图论 图 8.15 第8章 图论第8章 图论 图 8.16第8章 图论 图 8.17第8章 图论(3)G1与G2的差,定义为图G3V3,E3,记为G3=G1-G2。 其中E3=E1-E2,V3=(V1-V2)E3中边

3、所关联的顶点。 (4)G1与G2的环和,定义为图G3V3,E3,G3=(G1G2)-(G1G2),记为G3=G1G2。第8章 图论 图 8.19第8章 图论(4)若在子图G中,对V中的任意二结点u、v,当u,vE时有u,vE,则G由V唯一确定,此时称G为由结点集V导出的子图。第8章 图论 图 8.110第8章 图论图8.1-11第8章 图论HGGG第8章 图论基本路径也一定是简单路径。第8章 图论图8.2-1第8章 图论第8章 图论图中共图中共n n个结点个结点, ,故基本路径长度不超过故基本路径长度不超过n-1n-1。第8章 图论第8章 图论图图)。第8章 图论图8.22 一个无向图或者是一

4、个连通图,如图8.22(a)所示,或者是由若干个连通分图组成,如图8.22(b)所示。第8章 图论1()(1)2nmnn定义定义8.268.26在有向图中在有向图中, ,如果在任两结点偶对中如果在任两结点偶对中, ,至少至少从一个结点到另一个结点是可达的从一个结点到另一个结点是可达的, ,则称图则称图G G是单向连是单向连通的通的; ;如果在任两结点偶对中如果在任两结点偶对中, ,两结点都互相可达两结点都互相可达, ,则则称图称图G G是强连通的是强连通的; ;如果它的底图是连通的如果它的底图是连通的, ,则称图则称图G G是是弱连通的。弱连通的。第8章 图论第8章 图论第8章 图论第8章 图

5、论( , )d u第8章 图论,则停止,否则再重复2。第8章 图论第8章 图论第8章 图论第8章 图论第8章 图论图 8.27 第8章 图论表 8.21 第8章 图论第8章 图论第8章 图论图 8.28 第8章 图论第8章 图论次数全是偶数。第8章 图论第8章 图论第8章 图论第8章 图论图 8.29 第8章 图论第8章 图论第8章 图论图 8.210 第8章 图论图 8.210 第8章 图论第8章 图论图 8.211 第8章 图论第8章 图论第8章 图论图 8.212 第8章 图论第8章 图论图 8.213 第8章 图论第8章 图论12111,kiii12,kiii 第8章 图论 图 8.214 第8章 图论第8章 图论1(3)2n n第8章 图论第8章 图论第8章 图论图 8.215第8章 图论第8章 图论第8章 图论图 8.41 第8章