《(1.3.1)--ch7-1离散数学离散数学.pdf》由会员分享，可在线阅读，更多相关《(1.3.1)--ch7-1离散数学离散数学.pdf（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离离 散散 数数 学学 Discrete MathematicsDiscrete Mathematics 图论最早起源于一些数学游戏的难题研究：图论最早起源于一些数学游戏的难题研究：哥尼斯堡七桥问题哥尼斯堡七桥问题 迷宫问题、棋盘上马的行走路线问题迷宫问题、棋盘上马的行走路线问题 四色猜想、汉密尔顿四色猜想、汉密尔顿(环游世界环游世界)等等 图图 图的基本概念图的基本概念 图的连通性图的连通性 图的矩阵表示图的矩阵表示 特殊图特殊图 图的定义图的定义 图的同构图的同构 图与子图及其分类图与子图及其分类 通路与回路通路与回路 无向图的连通性无向图的连通性 有向图的连通性有向图的连通性 邻接矩阵、
2、可达矩阵、关联矩阵邻接矩阵、可达矩阵、关联矩阵 欧拉图欧拉图 哈密尔顿图哈密尔顿图 树树 定义、判定、简单应用定义、判定、简单应用 生成树生成树 术语、性质术语、性质 最小生成树最小生成树 根树根树 二叉树二叉树 现实世界中许多现象能用某种图形表示现实世界中许多现象能用某种图形表示,这种图形是由这种图形是由一些一些点点和一些连接两点间的和一些连接两点间的连线连线所组成所组成.例例1.a,b,c,d 4个篮球队进行友谊比赛个篮球队进行友谊比赛.为了表示为了表示4个队之间比赛的情况个队之间比赛的情况,我们作出下图我们作出下图 的图形的图形.在图中在图中4个小圆圈分别表示这个小圆圈分别表示这4个篮球
3、队个篮球队,如果两队进行过如果两队进行过比赛比赛,则在表示该队的圆圈之间用一条线连接起来则在表示该队的圆圈之间用一条线连接起来,这样利这样利用一个图形使各队之间的比赛情况一目了然用一个图形使各队之间的比赛情况一目了然.(2)又如又如4个结点个结点a,b,c,d分别表示分别表示4个人个人,当某两个人互相当某两个人互相认识时认识时,则将其对应点之间用边连接起来则将其对应点之间用边连接起来.这时的图又反映这时的图又反映了这了这4个人之间的认识关系个人之间的认识关系.(3)也可以点代表工厂也可以点代表工厂,以连接两点的连线表示这两工厂以连接两点的连线表示这两工厂间有业务往来关系间有业务往来关系.这样便
4、可用图形表示某一城市中各工厂这样便可用图形表示某一城市中各工厂间的业务往来关系间的业务往来关系.对于这种图形对于这种图形,我们的兴趣在于有多少个点和哪些点对间我们的兴趣在于有多少个点和哪些点对间有线连接有线连接,至于连线的长短曲直和点的位置都无关紧要至于连线的长短曲直和点的位置都无关紧要.对它对它们进行数学抽象我们就得到以下作为数学概念的图的定义们进行数学抽象我们就得到以下作为数学概念的图的定义.定义定义7-1.1 一个图一个图G是一个三元组是一个三元组(),(),GV G E G 记作记作 其中其中(),(),GGV G E G(1)V(G)是一个非空的集合是一个非空的集合,V(G)中元素称
5、为中元素称为顶点顶点或或结点结点;(2)E(G)是边集合是边集合;(3)G 是从边集合到结点无序偶是从边集合到结点无序偶(有序偶有序偶)集合上的函数集合上的函数.注注:1)图也可简记为图也可简记为G=,这里这里V是结点集是结点集,E是边集是边集.2)图可以用一个抽象的三元组来表示图可以用一个抽象的三元组来表示,也可以用一个具体也可以用一个具体的图形来表示且表示不唯一的图形来表示且表示不唯一.1.图的定义图的定义 7-1 图的基本概念图的基本概念 例例2 设设G=,其中其中 V(G)=a,b,c,d,E(G)=e1,e2,e3,e4,e5,e6,e7,G(e1)=(a,b),G(e2)=(a,c
6、),G(e3)=(b,d),G(e4)=(b,c),G(e5)=(d,c),G(e6)=(a,d),G(e7)=(b,b).(1)无序偶无序偶:结点对结点对(vj,vk)无顺序无顺序.(2)有序偶有序偶:结点对结点对 有顺序有顺序.(3)无向边无向边:若边若边ei与结点无序偶与结点无序偶(vi,vk)相关联相关联,称该边为称该边为无向边无向边.(4)有向边有向边:若边若边ei与结点有序偶与结点有序偶相关联相关联,称该边为称该边为有向边有向边.vi 称为称为ei的的起始结点起始结点,vk 称为称为ei 的的终止结点终止结点.图图G的结点与边之间的关系的结点与边之间的关系(5)邻接点邻接点:由一条
7、边连接的两个结点由一条边连接的两个结点;特别的对有向图特别的对有向图,若有有向边若有有向边,则称则称u 邻接邻接v;而不可称而不可称v 邻接邻接u.(6)孤立结点孤立结点:不与任何结点相邻接的结点不与任何结点相邻接的结点.(7)邻接边邻接边:连接同一结点的两条边连接同一结点的两条边.(8)自回路自回路(环环):连接同一结点的边连接同一结点的边.环的方向是没有意义的环的方向是没有意义的.环既可以看作是有向边环既可以看作是有向边,也可以看作是无向边也可以看作是无向边.(1)零图零图:仅由若孤立结点构成的图仅由若孤立结点构成的图.2.图的分类图的分类(2)平凡图平凡图:仅由一个孤立结点构成的图仅由一
8、个孤立结点构成的图.(3)无向图无向图:每一条边都是无向边的图每一条边都是无向边的图.(4)有向图有向图:每一条边都是有向边的图每一条边都是有向边的图.(5)混合图混合图:图中一些边是有向边图中一些边是有向边,一些边是无向边一些边是无向边.定义定义7-1.4 含有平行边的任何一个图称为含有平行边的任何一个图称为多重图多重图.不含不含平行边和环平行边和环的图称为的图称为简单图简单图.简单图简单图 多重图多重图 多重图多重图 连接同一对结点间的多条边称为连接同一对结点间的多条边称为平行边平行边(多重边多重边).注意注意:有向图中的平行边指的是两结点间多于一条有向图中的平行边指的是两结点间多于一条同
9、向边同向边.定义定义7-1.5 简单简单无向无向图图G=中中,若每对结点间都有若每对结点间都有 有有n个结点的个结点的无向完全图无向完全图,记为记为Kn.边相连边相连,则称该图为则称该图为完全图完全图.设设G=是是简单有向图简单有向图,如果对如果对G的任何两个不同的结点的任何两个不同的结点 u和和v,u邻接于邻接于v,v也邻接于也邻接于u,则称则称D是一个是一个有向完全图有向完全图.注注.n个结点的图称为个结点的图称为n阶图阶图.定理定理7-1.4 n 个结点的无向完全图个结点的无向完全图 Kn的边数为的边数为 1(1)2En n注意注意 n 个结点的有向完全图的边数为个结点的有向完全图的边数
10、为(1).n n (补补)定义定义 给每条边给每条边(或弧或弧)赋与权的图赋与权的图G=称为称为加权图加权图,记为记为G=,其中其中W 表示各边权的集合表示各边权的集合.定义定义7-1.2 在图在图G中中,与结点与结点v(vV)关联的边数关联的边数,称为该结点的称为该结点的度数度数,记为记为deg(v).约定约定:每个环在其对应结点上度数增加每个环在其对应结点上度数增加2.最大度最大度(G)=maxdeg(v)|vV(G);最小度最小度(G)=mindeg(v)|vV(G).二、二、结点的度数结点的度数 设设V=v1,v2,vn 为图为图G的结点集的结点集,称称(deg(v1),deg(v2)
11、,deg(vn)为为G的的度数序列度数序列.deg(a)=3 deg(b)=5 deg(c)=3 deg(d)=3(G)=5(G)=3 定理定理7-1.1(握手定理握手定理)每个图中每个图中,所有结点的度数之和恰好所有结点的度数之和恰好 等于该图的边数的两倍等于该图的边数的两倍,即有即有 deg()2v VvE定理定理7-1.2 在任何图中在任何图中,度数为奇数的结点度数为奇数的结点(奇度结点奇度结点)个个 数必为偶数数必为偶数.应用：应用：(1)(1,2,3,4,5),(1,2,2,3,4)能称为图的度数序列吗能称为图的度数序列吗?(2)已知图已知图G中有中有15条边条边,2个度数为个度数为
12、4的结点的结点,4个度数为个度数为3的结点的结点,其余结点的度数均小于或等于其余结点的度数均小于或等于2,问问:G中至少有多少中至少有多少个结点个结点?为什么为什么?定义定义7-1.3 在有向图中在有向图中,射入一个结点的边数射入一个结点的边数称为该结点的称为该结点的 由一个结点由一个结点射出的边数射出的边数称为该结点的称为该结点的出度出度,记为记为 入度入度,记为记为 结点结点v 的入度和的入度和出度之和称为结点出度之和称为结点v 的度数的度数,即即 定理定理7-1.3 在任何有向图中在任何有向图中,所有结点的入度之和必等于所有结点的入度之和必等于 它们的出度之和它们的出度之和.(1)已知有
13、向图已知有向图G的度数序列和出度序列分别为的度数序列和出度序列分别为(3,3,2,3,3),应用应用:deg().v deg().v deg()deg()deg()vvv+deg()deg()v Vv VvvE (2)设设G是是4阶有向简单图阶有向简单图,度数序列为度数序列为(3,3,3,3),它的入度列它的入度列(1,2,1,2,1),求求G的入度序列的入度序列.(或出度列或出度列),能为能为(1,1,1,1)吗吗.例例4 deg(a)3，deg+(a)1，deg-(a)2；deg(b)3，deg+(b)1，deg-(b)2；deg(c)3，deg+(c)2，deg-(c)1；deg(d)1
14、，deg+(d)1，deg-(d)0；deg(e)2，deg+(e)1，deg-(e)1；deg(f)deg+(f)deg-(f)0.图的定义思维形式注记图图的定义思维形式注记图 图图 边边 顶点顶点 度数度数 度数为奇数的度数为奇数的 结点数为偶数结点数为偶数 入度之和等于入度之和等于出度之和出度之和 2 Edeg()v Vv 度数序列度数序列 可图化可图化 三、子图与补图三、子图与补图 定义定义7-1.6 给定简单图给定简单图G,由由G中所有结点和所有能使中所有结点和所有能使G成为成为 完全图的添加边完全图的添加边组成的图称为组成的图称为G的的相对于完全图的补图相对于完全图的补图.记作记作
15、 G例如例如下面两图互为补图下面两图互为补图.定义定义7-1.7 给定图给定图G=,如果有图如果有图,GV E,EE VV使得使得,则称则称 G是是G的的子图子图.若若=,VV EE,则称则称 G是是G的的生成子图生成子图.子图子图 生成子图生成子图 定义定义7-1.8,GV E设图设图 是图是图G=的子图的子图.若对若对 另外一个图另外一个图,GV E使得使得 EEEV,且且 中仅包含中仅包含 的边所关联的结点的边所关联的结点.E则称则称 GG是的子图是的子图 关于图关于图G的的补图补图.例如例如.但但(b)不是不是(c)相对于相对于(a)的补图的补图.(a)b c a g h d e f(
16、b)b c g h d e f (c)b c a g h d f 下图中下图中(b)和和(c)都是都是(a)的子图的子图;(c)是是(b)相对于相对于(a)的补图的补图,图与子图及其分类的思维形式注记图图与子图及其分类的思维形式注记图 图图 G图图G 结点集结点集V(G)边集边集E(G)顶点和边顶点和边 的关系的关系 存在存在 孤立结点孤立结点 存在存在 零图零图 只有一个只有一个 平凡图平凡图 有序有序 有向图有向图,无向图无向图,混合图混合图 平行边平行边 简单图、多重图简单图、多重图 每一对顶点每一对顶点 都有边相连都有边相连 完全图完全图 添加边组成添加边组成 补图补图 数字数字 加权
17、图、无权图加权图、无权图 个数个数 n 个个 n 阶图阶图 子图子图 顶点集与顶点集与 边集是边集是 G的子集的子集 定义定义7-1.9 四、图的同构四、图的同构 给定图给定图G1和和G2,若存在一一若存在一一 对应的映射对应的映射 f :V1V2,使得使得 则称则称G1同构于同构于G2记为记为G1 G2.12(,)(),()ijijev vEef vf vE(或或 )12,(),()ijijev vEef vf vE 例例 下图所示的下图所示的(a)、(b)两图是同构的两图是同构的.f(1)=v3,f(2)=v1,f(3)=v4,f(4)=v2.,同构的图有如下一些性质同构的图有如下一些性质
18、 (1)结点数相等结点数相等;(2)边数相等边数相等;(3)度数相同的结点数相等度数相同的结点数相等.注意注意:以上三个性质是两个图同构的必要条件以上三个性质是两个图同构的必要条件,而非充分条件而非充分条件.(a)中的中的x应与应与(b)中的中的y对应对应,因为度数都是因为度数都是3.但但(a)中的中的x与两个度数与两个度数为为1的点的点u,v 邻接邻接,而而(b)中的中的y仅与一个度数为仅与一个度数为1的点的点w邻接邻接.图的同构的思维形式注记图图的同构的思维形式注记图 图的同构图的同构 定义定义 必要条件必要条件 结点数相等结点数相等 边数相等边数相等 度数相同的结点数相等度数相同的结点数相等 小结小结 1.基本概念基本概念 图、有向图、无向图、简单图、多重图、完全图、图、有向图、无向图、简单图、多重图、完全图、孤立结点、零图、平凡图、结点的度数、子图、孤立结点、零图、平凡图、结点的度数、子图、生成子图、补图、图的同构等生成子图、补图、图的同构等.2.基本定理（握手定理）会应用基本定理（握手定理）会应用.3.会判断所给图是否为同构的会判断所给图是否为同构的.