离散数学6-8章课件

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

2、，补图的概念，一、图的概念。1、定义。无序积2、图的表示法。有向图，无向图的顶点都用小圆圈表示。无向边连接顶点的线段。有向边以为始点，以为终点的有向线段。图形表示如右：例1、(2) 有向图，3、相关概念。(1) 有限图都是有限集的图。阶图的图。零图的图。特别，若又有，称平凡图。(2) 关联 (边与点关系)设边(或)，则称与(或)关联。3、相关概念。(2)3、相关概念。(2) 悬挂点只有一条边与其关联的点，所对应的边叫悬挂边。(3) 平行边关联于同一对顶点的若干条边称为平行边。平行边的条数称为重数。多重图含有平行边的图。简单图不含平行边和环的图。如例1的(1)中，与关联的次数均为1，与关联的次数

3、为2，边都是相邻的，为孤立点，为悬挂点，为悬挂边，为环，为平行边，重数2， 为多重图。例如：二、顶点的度数，握手定理。1、顶点的度数 (简称度)。无向图的度数记，指与，相关联的边的条数。有向图的度数，二、顶点的度数，握手定理。1、顶点的度数 (简称度)。最大度 最小度对有向图相应地还有，。如例1的(2)中，。设为图的顶点集，称 为的度数序列。2、握手定理。定理1：设图为无向图或有向图，为边数)，(则定理2：设为有向图，则，。2、握手定理推论：任何图中，度为奇数的顶点个数为偶数。 三、子图，补图。导出子图非空，以为顶点集，以两端均在中的边的全体为边集的的子图，称的导出子图。非空，以为边集，以中边

4、关联的顶点的全体为顶点集的的子图，称的导出子图。例3、上图中，(1)(6)都是(1)的子图，其中(2)(6)为真子图，(1)(5)为生成子图。如例3中，四、图的同构。定义：设两个无向图，若存在双射函数，使得对于任意的，当且仅当并且与重数相同，则称与同构，记作。例4、例5、(1) 画出4个顶点，3条边的所有非同构的无向简单图。解：只有如下3个图：例5、(2) 画出3个顶点，2条边的所有非同构的有向简单图。解：只有如下4个图：第二节 路径和回路（1） 内容：图的通路，回路，连通性。重点：1、通路，回路，简单通路，回路，初级通路，回路的定义，2、图的连通性的概念，3、短程线，距离的概念。一、路径，回

5、路。1、路径 (回路)中顶点和边的交替序列，其中(无向图)，或(有向图)，始点，终点，称为到的通路。当时，为回路。一、路径，回路。2、简单路径，简单回路。简单路径 (迹)：同一条边不出现两次基本路径（链）：同一顶点不出现两次简单回路 (闭迹)：没有相同边的回路基本回路：通过各顶点不超过一次的回路一、路径，回路。基本路径 (回路)简单路径 (回路)，但反之不真。3、路径，回路的长度中边的数目。例1、(1)图(1)中，从的路径有：到长度3长度6长度6例1、(1)图(1)中，从的路径有：到基本路径简单路径复杂通路例1、(2)长度3长度4长度7图(2)中过)有：的回路 (从到例1、(2)基本回路(圈)

6、基本回路(圈)复杂回路图(2)中过)有：的回路 (从到4、性质。定理1：阶图中，若从顶点到存在路径，则从到存在长度小于等于在一个的基本路径。（定理8.2-1）4、性质。定理2：阶图中，若到自身存在一个简单回路，则从到自身存在长度小于等于的基本回路。（定理8.2-2）在一个二、图的连通度。1、连通，可达。无向图中，从到存在通路，称到是连通的(双向)。有向图中，从到存在通路，称可达(注意方向)。2、短程线，距离。短程线连通或可达的两点间长度最短的通路。距离短程线的长度，记无向图有向图3、无向图的连通。为连通图是平凡图，或都是连通的。中任两点为非连通图中至少有两点不连通。3、无向图的连通。设是一个无

7、向图，是中顶点之间的连通关系，则是等价关系。设将划分成个等价类：，由它们导出的子图称为的连通分支，其个数记为4、有向图的连通。中任一对顶点都互相可达(双向)中任一对顶点至少一向可达略去中有向边的方向后得到的无向图连通连通强连通单向连通弱连通强连通单向连通弱连通例2、强连通单向连通例2、单向连通弱连通非连通图8.2 路径与回路（2）内容：欧拉、哈密尔顿路径、赋权图中的最短路径。重点：1、欧拉图的定义，无向图是否具有 欧拉回路的判定2、迪克斯特拉算法计算赋权图的最短路径了解：无向图是否具有哈密尔顿回路的判定。一、欧拉回路问题的提出。1736年，瑞士数学家欧拉，哥尼斯堡七桥问题二、定义。欧拉通路 (

8、欧拉迹)通过图中每条边一次且仅一次，并且过每一顶点的通路。欧拉回路 (欧拉闭迹)通过图中每条边一次且仅一次，并且过每一顶点的回路。欧拉图存在欧拉回路的图。注意：(1) 欧拉通路与欧拉回路不同。(2) 欧拉图指具有欧拉回路(并非通路)的图。(3) 欧拉通路(回路)必是简单通路(回路)。(4) 连通是具有欧拉通路(回路)的必要条件。(5) 欧拉通路(回路)是经过图中所有边的通路(回路)中最短的通路(回路)。三、无向图是否具有欧拉通路或回路的判定。有欧拉通路连通，中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。有欧拉回路(为欧拉图)连通，中均为偶度顶点。例1、以下图形能否一笔画成？例1、以下图形

9、能否一笔画成？例2、两只蚂蚁比赛问题。两只蚂蚁甲、乙分别处在图中的顶点处，并设图中各边长度相等。甲提出同乙比赛：从它们所在顶点出发，走过图中所有边最后到达顶点处。如果它们速度相同，问谁最先到达目的地？四、有向图是否具有欧拉通路或回路的判定。有欧拉通路连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。有欧拉回路(为欧拉图)连通，中所有顶点的入度等于出度。例3、判断以下有向图是否欧拉图。二、哈密尔顿图一、问题的提出。1859年，英国数学家哈密尔顿，周游世界游戏。二、哈密尔顿图。哈密尔顿通路通过图中每个顶点一次且仅一次的通路。哈密

10、尔顿回路通过图中每个顶点一次且仅一次的回路。哈密尔顿图存在哈密尔顿回路的图。注意：(1) 哈密尔顿通路与哈密尔顿回路不同。(2) 哈密尔顿图是指具有哈密尔顿回路(并非通路)的图。(3) 哈密尔顿通路(回路)必是初级通路(回路)。 (4) 连通是具有哈密尔顿通路(回路)的必要条件。注意：(5) 若图通路。具有哈密尔顿回路，则必有哈密尔顿(6) 阶图的哈密尔顿通路长为，回路长为。三、判定。采用尝试的办法。例1、判断下图是否具有哈密尔顿回路，通路。解：存在哈密尔顿通路，但不存在哈密尔顿回路。例1、判断下图是否具有哈密尔顿回路，通路。解：是哈密尔顿图，存在哈密尔顿回路和通路。例1、判断下图是否具有哈密

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

12、称为u到v的最短路径，求给定的两顶点之间的最短路径问题称为最短路径问题。 最短路径算法：由E.W.Dijkstra（迪克斯特拉）于1959年给出的标号法（Dijkstra算法）。 三、最短路径72问题：图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(

13、k)+W(i,k) (5) T为空集，算法结束。三、最短路径73例 用Dijkstra求下图中a到d的最短路径。abcdefa62 2f37 93b595ce9d677674四、最短路径例 求下图中a到f的最短路径。A,b,d,c,e,f 68.3 图的矩阵表示内容：邻接矩阵，关联矩阵，可达矩阵。重点：1、有向图的邻接矩阵。2、有向图，无向图的关联矩阵。了解：有向图的可达矩阵。一、有向图的邻接矩阵。1、设有向图，的邻接矩阵，其中指邻接到的边的条数 (非负整数)。例1、有向图(下图所示)，求。解：2、性质。(1)(2)(3)(4)为中环的个数。3. 的元素的意义设 ，则 。 表示：从结点 和 两

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

15、，其中为中长度小于等于的回路总数。例4、在例1的有向图中求，。解：，二、无向图的关联矩阵。1、设无向图，的关联矩阵，例2、无向图(下图所示)，求。解：2、性质。(1)(2)(3)握手定理（m为边数）（每列之和为2表示每条边只有两个顶点）（每行之和表示对应点的度数）(4)，当且仅当为孤立点。2、性质。(5) 若第列与第列相同，则说明与为平行边。三、有向简单图（无环）的关联矩阵。1、设无环有向图，的关联矩阵，其中例2、有向图(下图所示)，求。解：2、性质。(1)(2)(3)四、有向图的可达性矩阵。(了解)设为有向图，令，四、有向图的可达性矩阵。(了解)可达性矩阵其中元素可由求得：8.7 树一 .

16、无向树及生成树 内容：无向树，生成树。重点：1、无向树的定义 (包括等价定义)，2、无向树的性质，3、生成树的定义，由连通图构造最小生成树的方法。本章中所谈回路均指简单回路或基本回路。一、无向树。1、无向树连通且不含回路的无向图。无向树简称树，常用表示。平凡树平凡图（仅有一个结点的简单图）。森林 连通分支数大于等于2，且每个连通分支都是树的无向图。例1、例1、2、树的六个等价定义。(1)连通且不含回路。(2)的每对顶点间具有唯一的路径。(3)连通且。(4)无回路且。定理：设，则以下命题等价。2、树的六个等价定义。(5)无回路，但在中任两个不相邻的顶点之间增加一条边，就形成唯一的一条初级回路。(

17、6)是连通的，但删除任何一条边后，就不连通了。3、性质。(1) 树中顶点数与边数的关系：。(2) 定理：非平凡树至少2片树叶。证明：设为阶非平凡树，设有片树叶，则有个顶点度数大于等于2，由握手定理，又由(1)，代入上式，解得，即至少2片叶。例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(1)例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(2)例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个

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

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

20、成树及。解：例6、求以下连通图的最小生成树及。解：例6、求以下连通图的最小生成树及。注意：的最小生成树可能不唯一，但的不同最小生成树权的值一样。第八章 小结与例题一、无向图与有向图。1、基本概念。有向图与无向图的定义；关联与邻接(相邻)；顶点的度数；零图与平凡图；简单图与多重图；完全图；子图，补图；图的同构。一、无向图与有向图。2、运用。(1) 灵活运用握手定理及其推论，(2) 判断两个图是否同构，(3) 画出满足某些条件的子图，补图等。二、通路，回路，图的连通性。1、基本概念。通路和回路；无向图和有向图中顶点之间的可达关系；短程线，距离；有向图连通的分类。二、通路，回路，图的连通性。2、运用

21、。(1) 判断有向图或无向图中通路(回路)的类型。(2) 求短程线和距离。(3) 判断有向图连通的类型。三、欧拉图。1、基本概念。欧拉通路，欧拉回路，欧拉图。2、运用。判定无向图是否具有欧拉通路或回路。四、哈密尔顿图。1、基本概念。哈密尔顿通路，哈密尔顿回路，哈密尔顿图。2、运用。判断无向图是否具有哈密尔顿通路或回路。五、图的矩阵表示。1、基本概念。无向图的关联矩阵，有向图的关联矩阵和邻接矩阵。2、运用。(1) 关联矩阵的行和、顶点度数间的关系。(2) 由有向图的邻接矩阵的次幂求从一顶点到另一顶点的长度为的通路数。六、无向树及生成树。1、基本概念。无向树；树叶，分支点；森林；平凡树；生成树，最

22、小生成树。2、运用。(3) 根据握手定理及树的某些性质，求顶点数或某些顶点的度数。(4) 求生成树，最小生成树。七、应用1、赋权图的最短路径迪克斯特拉算法2、最小生成树克鲁斯克尔算法例1、设图，其中，分别由下面给出。判断哪些是简单图，哪些是多重图？(1)(2)(3)简单图多重图不是例1、设图，其中，分别由下面给出。判断哪些是简单图，哪些是多重图？(4)(5)(6)简单图多重图不是例2、下列各序列中，可以构成无向简单图的度数序列的有哪些？(1)可以(2)不可以(3)可以(4)不可以(5)不可以例3、右图所示的无向图中，分别求：不同的基本通路(路径)。(1)之间所有解：有7条，分别为，和，。(2)之间的短程线。(3)。解：。解：。例4、下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？强连通单向连通弱连通例4、下图所示的六个图中