离散数学——章学习.pptx

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

1、图论是一个古老的数学分支，它起源于游戏难题的研究。图论的内容十分丰富，应用得相当广泛，许多学科，诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等，都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展，图论在以上各学科中的作用越来越大，同时图论本身也得到了充分的发展。第1页/共148页第八章 图论 第一节 图的基本概念 第2页/共148页内容：有向图，无向图的基本概念。重点：1、有向图，无向图的定义，2、图中顶点，边，关联与相邻，顶点度数等基本概念，3、各顶点度数与边数的关系及推论，第3页/共148页内容：有向图，无向图的基本概念。5、图

2、的同构的定义。重点：4、简单图，完全图，子图，补图的概念，第4页/共148页第5页/共148页第6页/共148页2、图的表示法。有向图，无向图的顶点都用小圆圈表示。无向边连接顶点的线段。有向边以为始点，以为终点的有向线段。第7页/共148页例1、(1)无向图，图形表示如右：第8页/共148页图形表示如右：例1、(2)有向图，第9页/共148页3、相关概念。(1)有限图都是有限集的图。阶图的图。零图的图。特别，若又有，称平凡图。(2)关联(边与点关系)设边(或)，则称与(或)关联。第10页/共148页3、相关概念。(2)第11页/共148页3、相关概念。(2)孤立点无边关联的点。环一条边关联的两

3、个顶点重合，称此边为环(即两顶点重合的边)。第12页/共148页3、相关概念。(2)悬挂点只有一条边与其关联的点，所对应的边叫悬挂边。(3)平行边关联于同一对顶点的若干条边称为平行边。平行边的条数称为重数。多重图含有平行边的图。简单图不含平行边和环的图。第13页/共148页如例1的(1)中，与关联的次数均为1，与关联的次数为2，边都是相邻的，为孤立点，为悬挂点，为悬挂边，为环，为平行边，重数2，为多重图。第14页/共148页4、完全图设为阶无向简单图，若中每个顶点都与其余个顶点相邻，则称 为 阶无向完全图，记作。若有向图的任一对顶点，既有有向边又有有向边，则称为有向完全图。第15页/共148页

4、例如：第16页/共148页二、顶点的度数，握手定理。1、顶点的度数(简称度)。无向图的度数记，指与，相关联的边的条数。有向图的度数，第17页/共148页二、顶点的度数，握手定理。1、顶点的度数(简称度)。最大度 最小度对有向图相应地还有，。第18页/共148页如例1的(2)中，。第19页/共148页设为图的顶点集，称 为的度数序列。2、握手定理。定理1：设图为无向图或有向图，为边数)，(则第20页/共148页定理2：设为有向图，则，。2、握手定理推论：任何图中，度为奇数的顶点个数为偶数。第21页/共148页三、子图，补图。1、子图定义：设是两个图，若，且，则称是的子图，是的母图，记作。真子图

5、且(即或)。生成子图且。第22页/共148页三、子图，补图。导出子图 非空，以为顶点集，以两端均在中的边的全体为边集的的子图，称的导出子图。非空，以为边集，以中边关联的顶点的全体为顶点集的的子图，称的导出子图。第23页/共148页例3、上图中，(1)(6)都是(1)的子图，其中(2)(6)为真子图，(1)(5)为生成子图。第24页/共148页2、补图定义。设为无向完全图，为无向简单图，其中，则称，相对于互为补图，记，。第25页/共148页如例3中，第26页/共148页四、图的同构。定义：设两个无向图，若存在双射函数，使得对于任意的，当且仅当并且与重数相同，则称与同构，记作。第27页/共148页

6、例4、第28页/共148页例5、(1)画出4个顶点，3条边的所有非同构的无向简单图。解：只有如下3个图：第29页/共148页例5、(2)画出3个顶点，2条边的所有非同构的有向简单图。解：只有如下4个图：第30页/共148页第二节 路径和回路（1）第31页/共148页内容：图的通路，回路，连通性。重点：1、通路，回路，简单通路，回路，初级通路，回路的定义，2、图的连通性的概念，3、短程线，距离的概念。第32页/共148页一、路径，回路。1、路径(回路)中顶点和边的交替序列，其中(无向图)，或(有向图)，始点，终点，称为到的通路。当时，为回路。第33页/共148页一、路径，回路。2、简单路径，简单

7、回路。简单路径(迹)：同一条边不出现两次基本路径（链）：同一顶点不出现两次简单回路(闭迹)：没有相同边的回路基本回路：通过各顶点不超过一次的回路第34页/共148页一、路径，回路。基本路径(回路)简单路径(回路)，但反之不真。3、路径，回路 的长度中边的数目。第35页/共148页例1、(1)图(1)中，从的路径有：到长度3长度6长度6第36页/共148页例1、(1)图(1)中，从的路径有：到基本路径简单路径复杂通路第37页/共148页例1、(2)长度3长度4长度7图(2)中过)有：的回路(从到第38页/共148页例1、(2)基本回路(圈)基本回路(圈)复杂回路图(2)中过)有：的回路(从到第3

8、9页/共148页4、性质。定理1：阶图中，若从顶点 到存在路径，则从到存在长度小于等于在一个的基本路径。（定理8.2-1）第40页/共148页4、性质。定理2：阶图中，若 到自身存在一个简单回路，则从 到自身存在长度小于等于的基本回路。（定理8.2-2）在一个第41页/共148页二、图的连通度。1、连通，可达。无向图中，从 到存在通路，称到是连通的(双向)。有向图中，从 到存在通路，称可达(注意方向)。第42页/共148页2、短程线，距离。短程线连通或可达的两点间长度最短的通路。距离短程线的长度，记无向图有向图第43页/共148页3、无向图的连通。为连通图是平凡图，或都是连通的。中任两点为非连

9、通图中至少有两点不连通。第44页/共148页3、无向图的连通。设是一个无向图，是中顶点之间的连通关系，则是等价关系。设将划分成个等价类：，由它们导出的子图称为的连通分支，其个数记为第45页/共148页4、有向图的连通。中任一对顶点都互相可达(双向)中任一对顶点至少一向可达略去 中有向边的方向后得到的无向图连通连通强连通单向连通弱连通强连通单向连通弱连通第46页/共148页例2、强连通单向连通第47页/共148页例2、单向连通弱连通非连通图第48页/共148页8.2 路径与回路（2）第49页/共148页内容：欧拉、哈密尔顿路径、赋权图中的最短路径。重点：1、欧拉图的定义，无向图是否具有 欧拉回路

10、的判定2、迪克斯特拉算法计算赋权图的最短路径了解：无向图是否具有哈密尔顿回路的判定。第50页/共148页一、欧拉回路问题的提出。1736年，瑞士数学家欧拉，哥尼斯堡七桥问题第51页/共148页二、定义。欧拉通路(欧拉迹)通过图中每条边一次且仅一次，并且过每一顶点的通路。欧拉回路(欧拉闭迹)通过图中每条边一次且仅一次，并且过每一顶点的回路。欧拉图 存在欧拉回路的图。第52页/共148页注意：(1)欧拉通路与欧拉回路不同。(2)欧拉图指具有欧拉回路(并非通路)的图。(3)欧拉通路(回路)必是简单通路(回路)。(4)连通是具有欧拉通路(回路)的必要条件。(5)欧拉通路(回路)是经过图中所有边的通路(

11、回路)中最短的通路(回路)。第53页/共148页三、无向图是否具有欧拉通路或回路的判定。有欧拉通路连通，中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。有欧拉回路(为欧拉图)连通，中均为偶度顶点。第54页/共148页例1、以下图形能否一笔画成？第55页/共148页例1、以下图形能否一笔画成？第56页/共148页例2、两只蚂蚁比赛问题。两只蚂蚁甲、乙分别处在图中的顶点处，并设图中各边长度相等。甲提出同乙比赛：从它们所在顶点出发，走过图中所有边最后到达顶点处。如果它们速度相同，问谁最先到达目的地？第57页/共148页四、有向图是否具有欧拉通路或回路的判定。有欧拉通路连通，除两个顶点外，其余顶点

12、的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。有欧拉回路(为欧拉图)连通，中所有顶点的入度等于出度。第58页/共148页例3、判断以下有向图是否欧拉图。第59页/共148页二、哈密尔顿图第60页/共148页一、问题的提出。1859年，英国数学家哈密尔顿，周游世界游戏。第61页/共148页二、哈密尔顿图。哈密尔顿通路 通过图中每个顶点一次且仅一次的通路。哈密尔顿回路 通过图中每个顶点一次且仅一次的回路。哈密尔顿图存在哈密尔顿回路的图。第62页/共148页注意：(1)哈密尔顿通路与哈密尔顿回路不同。(2)哈密尔顿图是指具有哈密尔顿回路(并非通路)的图。

13、(3)哈密尔顿通路(回路)必是初级通路(回路)。(4)连通是具有哈密尔顿通路(回路)的必要条件。第63页/共148页注意：(5)若图通路。具有哈密尔顿回路，则必有哈密尔顿(6)阶图的哈密尔顿通路长为，回路长为。三、判定。采用尝试的办法。第64页/共148页例1、判断下图是否具有哈密尔顿回路，通路。解：存在哈密尔顿通路，但不存在哈密尔顿回路。第65页/共148页例1、判断下图是否具有哈密尔顿回路，通路。解：是哈密尔顿图，存在哈密尔顿回路和通路。第66页/共148页例1、判断下图是否具有哈密尔顿回路，通路。解：不存在哈密尔顿回路，也不存在哈密尔顿通路。第67页/共148页 哈密尔顿回路存在的两件个

14、充分条件定理8.2-13 设 是具有 个顶点的简单无向图，若在G中每一对顶点的次数之和大于n,则在G中存在一条哈密尔顿回路。推论8.2-13 在简单无向图中，若每一顶点的次数则在G中存在一条哈密尔顿回路。第68页/共148页69三、最短路径定义 设G=(V，E)是无向简单图，如果对E中每条边e都有一个实数w(e)附着其上，则称G为权图，称w(e)为边e的权。设P是G的一条路，P上所带权的总和称为路P的权。有时记为G=(V，E，W)第69页/共148页70设权图G中每条边的权均大于等于0，u,v为G中任意的两个顶点，从u到v的所有路中权最小的路称为u到v的最短路径，求给定的两顶点之间的最短路径问

15、题称为最短路径问题。最短路径算法：由 三、最短路径第70页/共148页71问题：图G=(V,E,W),1V,求1到V其它点的最短距离。设S为最短距离已经确定的集合，T为最短距离未确定的集合。算法描述如下：(1)初始话：S=1，T=V-S。(2)求1经过S中的点。到T中点的最短距离。记为D(i)。D(i)=w(1,i)(3)选T中D(i)值最小的点i，记为k。把k加入S，T=V-S。(4)对T中的点i更新D(i)：若D(k)+W(i,k)D(i)，D(i)=D(k)+W(i,k)(5)T为空集，算法结束。三、最短路径第71页/共148页72例 用Dijkstra求下图中a到d的最短路径。abcd

16、efa62 2f3793b595ce9d67 76第72页/共148页73四、最短路径例 求下图中a到f的最短路径。第73页/共148页A,b,d,c,e,f 6第74页/共148页8.3 图的矩阵表示第75页/共148页内容：邻接矩阵，关联矩阵，可达矩阵。重点：1、有向图的邻接矩阵。2、有向图，无向图的关联矩阵。了解：有向图的可达矩阵。第76页/共148页一、有向图的邻接矩阵。1、设有向图，的邻接矩阵，其中指邻接到的边的条数(非负整数)。第77页/共148页例1、有向图(下图所示)，求。解：第78页/共148页2、性质。(1)(2)(3)(4)为中环的个数。第79页/共148页3.的元素的意

17、义设 ，则 。表示：从结点 和 两者引出的边，如果能共同终止于一些结点，则 就是这些终止结点的数目。特别地：时，对角线上的元素 就是结点 的引出次数。第80页/共148页4.的元素的意义设 ，则 。表示：从一些结点引出的边，如果能同时终止于 和 ，则 就是这样的结点数目。特别地：时，对角线上的元素 就是结点 的引出次数。第81页/共148页5、求中长度为 的通路数和回路数。(1)令矩阵乘法其中表示从到长度为2的通路数或回路数。第82页/共148页5、求中长度为 的通路数和回路数。考虑，简记为。其中表示从到长度为或回路数。的通路数中长度为为的通路总数，其中为 中长度为 的回路总数。第83页/共1

18、48页5、求中长度为 的通路数和回路数。(2)设则中元素为中到长度小于等于的通路总数，为中长度小于等于 的通路总数，其中为 中长度小于等于的回路总数。第84页/共148页例4、在例1的有向图中求，。解：，第85页/共148页二、无向图的关联矩阵。1、设无向图，的关联矩阵，第86页/共148页例2、无向图(下图所示)，求。解：第87页/共148页2、性质。(1)(2)(3)握手定理（m为边数）（每列之和为2表示每条边只有两个顶点）（每行之和表示对应点的度数）第88页/共148页(4)，当且仅当为孤立点。2、性质。(5)若第 列与第列相同，则说明 与为平行边。第89页/共148页三、有向简单图（无

19、环）的关联矩阵。1、设无环有向图，的关联矩阵，其中第90页/共148页例2、有向图(下图所示)，求。解：第91页/共148页2、性质。(1)(2)(3)第92页/共148页四、有向图的可达性矩阵。(了解)设为有向图，令，第93页/共148页四、有向图的可达性矩阵。(了解)可达性矩阵其中元素可由求得：第94页/共148页8.7 树一.无向树及生成树 第95页/共148页内容：无向树，生成树。重点：1、无向树的定义(包括等价定义)，2、无向树的性质，3、生成树的定义，由连通图构造最小生成树的方法。本章中所谈回路均指简单回路或基本回路。第96页/共148页一、无向树。1、无向树 连通且不含回路的无向

20、图。无向树简称树，常用表示。平凡树 平凡图（仅有一个结点的简单图）。森林 连通分支数大于等于2，且每个连通分支都是树的无向图。第97页/共148页例1、第98页/共148页例1、第99页/共148页2、树的六个等价定义。(1)连通且不含回路。(2)的每对顶点间具有唯一的路径。(3)连通且。(4)无回路且。定理：设，则以下命题等价。第100页/共148页2、树的六个等价定义。(5)无回路，但在中任两个不相邻的顶点之间增加一条边，就形成唯一的一条初级回路。(6)是连通的，但删除任何一条边后，就不连通了。第101页/共148页3、性质。(1)树中顶点数与边数的关系：。(2)定理：非平凡树至少2片树叶

21、。证明：设为阶非平凡树，设有 片树叶，则有个顶点度数大于等于2，由握手定理，又由(1)，代入上式，解得，即至少2片叶。第102页/共148页例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(1)第103页/共148页例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(2)第104页/共148页例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(3)第

22、105页/共148页例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(4)第106页/共148页例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(5)第107页/共148页二、生成树。1、定义：设是无向连通图，是的生成子图，若是树，称是的生成树。树枝弦余树在中的边，不在中的边，的所有的弦的集合的导出子图。第108页/共148页例4、上图中，(2)是(1)的生成树，(3)是(2)的余树。注意：(1)生成树不唯一，(2)余树不一定是

23、树。第109页/共148页2、连通图的性质。设为连通图，(1)至少有一棵生成树，(2)，(3)设是的生成树，是的余树，则中有条边。已知连通图，求其生成树步骤。第110页/共148页3、最小生成树。对于有向图或无向图的每条边附加一个实数，则称为边上的权，连同附加在各边上的实数称为带权图，记为。最小生成树 各边权和最小的生成树。定义：设无向连通带权图，是的一棵生成树，各边带权之和称为的权，记作。第111页/共148页求最小生成树的方法（克鲁斯克尔)避圈法。设阶无向连通带权图中有条边，它们带的权分别为，不妨设，(1)取在中(非环，若为环，则弃)。(2)若不与构成回路，取在中，否则弃，再查，继续这一过

24、程，直到形成树为止。第112页/共148页解：例5、求以下连通图的最小生成树及。第113页/共148页解：例5、求以下连通图的最小生成树及。第114页/共148页解：例6、求以下连通图的最小生成树及。第115页/共148页解：例6、求以下连通图的最小生成树及。第116页/共148页注意：的最小生成树可能不唯一，但的不同最小生成树权的值一样。第117页/共148页第八章 小结与例题第118页/共148页一、无向图与有向图。1、基本概念。有向图与无向图的定义；关联与邻接(相邻)；顶点的度数；零图与平凡图；简单图与多重图；完全图；子图，补图；图的同构。第119页/共148页一、无向图与有向图。2、运

25、用。(1)灵活运用握手定理及其推论，(2)判断两个图是否同构，(3)画出满足某些条件的子图，补图等。第120页/共148页二、通路，回路，图的连通性。1、基本概念。通路和回路；无向图和有向图中顶点之间的可达关系；短程线，距离；有向图连通的分类。第121页/共148页二、通路，回路，图的连通性。2、运用。(1)判断有向图或无向图中通路(回路)的类型。(2)求短程线和距离。(3)判断有向图连通的类型。第122页/共148页三、欧拉图。1、基本概念。欧拉通路，欧拉回路，欧拉图。2、运用。判定无向图是否具有欧拉通路或回路。第123页/共148页四、哈密尔顿图。1、基本概念。哈密尔顿通路，哈密尔顿回路，

26、哈密尔顿图。2、运用。判断无向图是否具有哈密尔顿通路或回路。第124页/共148页五、图的矩阵表示。1、基本概念。无向图的关联矩阵，有向图的关联矩阵和邻接矩阵。2、运用。(1)关联矩阵的行和、顶点度数间的关系。(2)由有向图的邻接矩阵的次幂求从一顶点到另一顶点的长度为 的通路数。第125页/共148页六、无向树及生成树。1、基本概念。无向树；树叶，分支点；森林；平凡树；生成树，最小生成树。2、运用。(3)根据握手定理及树的某些性质，求顶点数或某些顶点的度数。(4)求生成树，最小生成树。第126页/共148页七、应用1、赋权图的最短路径迪克斯特拉算法2、最小生成树克鲁斯克尔算法第127页/共14

27、8页例1、设图，其中，分别由下面给出。判断哪些是简单图，哪些是多重图？(1)(2)(3)简单图多重图不是第128页/共148页例1、设图，其中，分别由下面给出。判断哪些是简单图，哪些是多重图？(4)(5)(6)简单图多重图不是第129页/共148页例2、下列各序列中，可以构成无向简单图的度数序列的有哪些？(1)可以(2)不可以(3)可以(4)不可以(5)不可以第130页/共148页例3、右图所示的无向图中，分别求：不同的基本通路(路径)。(1)之间所有解：有7条，分别为，和，。(2)之间的短程线。(3)。解：。解：。第131页/共148页例4、下图所示的六个图中，强连通，单向连通，弱连通的分别

28、有哪些？强连通单向连通弱连通第132页/共148页例4、下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？单向连通强连通强连通第133页/共148页例5、画一个欧拉图，使它具有：(1)偶数个顶点，偶数条边。(2)奇数个顶点，奇数条边。解：解：第134页/共148页例5、画一个欧拉图，使它具有：(3)偶数个顶点，奇数条边。(4)奇数个顶点，偶数条边。解：解：第135页/共148页例6、今有七个人，已知下列事实：会讲英语；会讲英语和汉语；会讲英语、意大利语和俄语；会讲日语和汉语；会讲德语和意大利语；会讲法语、日语和俄语；会讲法语和德语。试问这七个人应如何排座位，才能使每个人都能和他身边的两

29、个人交谈？第136页/共148页解：语言就连一条边，这样得到无向图，再求的哈密尔顿回路。用七个顶点表示七个人，若两人之间有共同图的哈回路第137页/共148页例7、下图中哪些是欧拉图，哪些是哈密尔顿图?(1)解：不是欧拉图，不是哈密尔顿图，第138页/共148页例7、下图中哪些是欧拉图，哪些是哈密尔顿图?解：是欧拉图，是哈密尔顿图.(2)第139页/共148页例7、下图中哪些是欧拉图，哪些是哈密尔顿图?解：不是欧拉图，是哈密尔顿图，(3)第140页/共148页例7、下图中哪些是欧拉图，哪些是哈密尔顿图?解：不是欧拉图，是哈密尔顿图.(4)第141页/共148页例8、已知图的邻接矩阵，(1)第1

30、42页/共148页例8、已知图的邻接矩阵，(2)从 到长度为2的通路数。解：因，所以从 到 长度为2的通路数为2。第143页/共148页例8、已知图的邻接矩阵，(3)从 到长度为3的通路数。解：因，所以从 到 长度为3的通路数为5。第144页/共148页例9、下列各图中各有多少个顶点。(1)16条边，每个顶点的度数均为2。解：设顶点数为，解得。解：设顶点数为，(2)21条边，3个度数为4的顶点，其余顶点的度数均为3。，由握手定理，由握手定理，有，解得。有第145页/共148页146例 10 用Dijkstra求下图中a到d的最短路径。abcdefa62 2f3793b595ce9d67 76第146页/共148页解：例11.求以下连通图的最小生成树及。第147页/共148页感谢您的观看！第148页/共148页