《离散数学》第6章图的基本概念.ppt

《《离散数学》第6章图的基本概念.ppt》由会员分享，可在线阅读，更多相关《《离散数学》第6章图的基本概念.ppt（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、有向图 5、图的同构的定义。4、简单图，完全图，子图，补图的概念，3、各顶点度数与边数的关系及推论，一、图的概念。一、图的概念。1、定义定义。无序积无向图中元素为无向边，简称边。，有向图中元素为有向边，简称边。，2、图的表示法。有向图，无向图的顶点都用小圆圈表示。无向边无向边连接顶点的线段。有向边有向边以为始点，以为终点的有向线段。例例1、(1)无向图，图形表示如右：图形表示如右：例例1、(2)有向图，3、相关概念。(1)有限图有限图都是有限集的图。阶图阶图的图。零图零图的图。特别，若又有，称平凡图。(2)关联关联(边与点关系边与点关系)设边(或)，则称与(或)关联。孤立点孤立点无边关联的点。

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

4、顶点的度数，握手定理。1、顶点的度数(简称度)。无向图的度数记，指与，相关联的边的条数。有向图的度数，如例1的(2)中，设为图的顶点集，称 为的度数序列度数序列。2、握手定理。定理定理1：设图为无向图或有向图，为边数)，(则定理定理2：设为有向图，则，。推论：推论：任何图中，度为奇数的顶点个数为偶数。例2（1）（2，3，4，5，6，7），（1，2，2，3，4）能否构成无向图的度数序列？为什么？如能则画出图解（2）已知图 中有11条边，有1个4度顶点，4个3度顶点，其余顶点的度数均小于等于2，问中至少有几个顶点？三、子图，补图。三、子图，补图。1、子图定义：子图定义：设是两个图，若，且，则称是的

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

6、所有非同构的无向简单图。解：解：只有如下3个图：例例5、(2)画出3个顶点，2条边的所有非同构的有向简单图。解：解：只有如下4个图：内容：内容：图的通路，回路，连通性，点割集，边割集。重点：重点：1、通路，回路，简单通路，回路，初级通路，回路的定义，2、图的连通性的概念，3、短程线，距离的概念。第二节第二节 通路，回路，图的连通性通路，回路，图的连通性 一、通路，回路。一、通路，回路。1、通路通路(回路回路)中顶点和边的交替序列，其中(无向图)，或(有向图)，始点始点，终点终点，称为到的通路通路。当时，为回路回路。2、简单通路，简单回路。简单通路简单通路(迹迹)简单回路简单回路(闭迹闭迹)复杂

7、通路复杂通路(回路回路)3、初级通路，初级回路。初级通路初级通路(路径路径)初级回路初级回路(圈圈)初级通路(回路)简单通路(回路)，但反之不真。4、通路，回路 的长度中边的数目。例例1、(1)图(1)中，从的通路有：到长度3长度6长度6初级通路简单通路复杂通路(2)长度3长度4长度7图(2)中过)有：的回路(从到初级回路(圈)初级回路(圈)复杂回路5、图中最短的回路。如图：6、性质。定理定理3：阶图中，若从顶点 到存在通路，则从到存在长度小于等于在一个的通路。推论：推论：阶图中，若从顶点 到存在通路，则从到存在长度小于等于在一个的初级通路。定理定理4：阶图中，若 到自身存在回路，则从到自身存

8、在长度小于等于 的回路。在一个推论：推论：阶图中，若 到自身存在一个简单回路，则从 到自身存在长度小于等于的初级回路。在一个由以上定理可知，在阶图中，任何一条初级通路的长度任何一条初级回路的长度二、图的连通性。二、图的连通性。1、连通，可达。无向图中，从 到存在通路，称到是连通的连通的(双向双向)。有向图中，从 到存在通路，称可达可达(注意方向)。2、短程线，距离。短程线连通或可达的两点间长度最短的通路。距离短程线的长度，记无向图有向图若之间无通路(或不可达)，规定距离满足：(1)，时，等号成立。(2)若是无向图，还具有对称性，。3、无向图的连通。为连通图为连通图是平凡图，或都是连通的。中任两

9、点为非连通图为非连通图中至少有两点不连通。设是一个无向图，是中顶点之间的连通关系，则是等价关系等价关系。设将划分成个等价类：，由它们导出的子图称为的连通分支连通分支，其个数记为4、有向图的连通。中任一对顶点都互相可达(双向)中任一对顶点至少一向可达略去 中有向边的方向后得到的无向图连通连通强连通单向连通弱连通强连通单向连通弱连通例例2、强连通单向连通单向连通弱连通非连通图三、点割集，边割集。1、设无向图 是连通图，若有顶点集 ，使 删除（将 中顶点及其关联的边都删除）后，所得子图 是不连通的或是平凡图；而删除 中的任何真子集 后，所得子图是连通的，则称 是 的点点割割集集若点割集中只有一个顶点

10、，则称该点为割点割点2、设无向图 是连通图，若有边集 ，使 删除（将 中的边从 中全部删除）后，所得子图 是不连通的或是平凡图；而删除 中的任何真子集 后，所得子图 是连通的，则称 是 的边边割割集集若边割集中只有一条边，则称该边为割割边边或桥桥内容：内容：关联矩阵，邻接矩阵，可达矩阵。重点：重点：1、有向图，无向图的关联矩阵，2、有向图的邻接矩阵。了解：了解：有向图的可达矩阵。第三节第三节 图的矩阵表示图的矩阵表示一、无向图的关联矩阵。一、无向图的关联矩阵。1、设无向图，的关联矩阵，例例1、无向图(下图所示)，求。解：2、性质性质。(1)(2)(3)握手定理(4)，当且仅当为孤立点。(5)若

11、第 列与第列相同，则说明 与为平行边。二、有向图的关联矩阵。二、有向图的关联矩阵。1、设无环有向图，的关联矩阵，其中例例2、有向图(下图所示)，求。解：解：2、性质性质。(1)(2)(3)三、有向图的邻接矩阵。三、有向图的邻接矩阵。1、设有向图，的邻接矩阵，其中指邻接到的边的条数(非负整数)。例例3、有向图(下图所示)，求。解：解：2、性质性质。(1)(2)(3)(4)为中环的个数。3、求中长度为 的通路数和回路数。(1)令矩阵乘法其中表示从到长度为2的通路数或回路数。考虑，简记为。其中表示从到长度为或回路数。的通路数中长度为为的通路总数，其中为 中长度为 的回路总数。(2)设则中元素为中到长

12、度小于等于的通路总数，为中长度小于等于 的通路总数，其中为 中长度小于等于的回路总数。例例4、在例3的有向图中求，。解：解：，四、有向图的可达性矩阵。四、有向图的可达性矩阵。(了解了解)设为有向图，令，可达性矩阵其中元素可由求得：第四节第四节 最短路径及关键路径最短路径及关键路径 内容：带权图，最短路径，Dijkstra算法算法，PERTPERT图，关键路径图，关键路径 重点：Dijkstra算法算法 了解：关键路径问题1、对于无向图或有向图 的每条边附加一个实数 ，则称 为边 上的权权连同附加在各边上的实数称为带权图带权图常记带权图为 一、最短路径问题2、在一个带权图 中，任给两点 和 ，从

13、 到 可能有好几条通路在这些通路中，求出所带权的总和最小的那条通路称为最短路径最短路径）3、Dijkstra标号法标号法 开始 ，给出始点 的 标号：，的 标号第 步 求下一个 标号顶点设 ，将 标在相应顶点 处，表明 获得 标号 修改通过集 和未通过集 查 ：若 ，则算法结束，否则转第2步 第 步 修改 中各顶点的 标号：是刚刚获得 标号顶点的 标号 令 ，转第 步 二、关键路径问题1、PERT图 2 2、最早完成时间、最早完成时间3 3、最晚完成时间、最晚完成时间4 4、缓冲时间、缓冲时间 一、无向图与有向图。一、无向图与有向图。1、基本概念。有向图与无向图的定义；关联与邻接(相邻)；顶点

14、的度数；零图与平凡图；简单图与多重图；完全图；子图，补图；图的同构。第六章第六章 小结与例题小结与例题2、运用。(1)灵活运用握手定理及其推论，(2)判断两个图是否同构，(3)画出满足某些条件的子图，补图等。二、通路，回路，图的连通性。二、通路，回路，图的连通性。1、基本概念。通路和回路；无向图和有向图中顶点之间的可达关系；短程线，距离；有向图连通的分类。2、运用。(1)判断有向图或无向图中通路(回路)的类型。(2)求短程线和距离。(3)判断有向图连通的类型。三、图的矩阵表示。三、图的矩阵表示。1、基本概念。无向图的关联矩阵，有向图的关联矩阵和邻接矩阵。2、运用。(1)关联矩阵的行和、顶点度数

15、间的关系。(2)由有向图的邻接矩阵的次幂求从一顶点到另一顶点的长度为 的通路数。四、最短路径和关键路径1、基本概念。权，带权图，最短路径，标号法PERT图，最早完成时间，后继元集，先驱元集最晚完成时间，缓冲时间2、运用。（1）标号法求解最短路径问题（2）求解关键路径问题例例1、设图，其中，分别由下面给出。判断哪些是简单图，哪些是多重图？(1)(2)(3)简单图多重图不是(4)(5)(6)简单图多重图不是例例2、下列各序列中，可以构成无向简单图的度数序列的有哪些？(1)可以(2)不可以(3)可以(4)不可以例例3、(1)画出完全图的所有非同构的生成子图。解：解：(2)的生成子图有几个是连通图？解

16、：解：有6个：例例4、下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？强连通单向连通弱连通单向连通强连通强连通例例5、已知图的邻接矩阵，(1)(2)从 到长度为2的通路数。解：解：因，所以从 到 长度为2的通路数为2。(3)从 到长度为3的通路数。解：解：因，所以从 到 长度为3的通路数为5。(4)过长度为3的回路数。解：解：因，所以过 长度为3的回路数为3。例例6、设为9个顶点的无向图，每个顶点的度数不是5就是6。证明 中至少有5个6度顶点或者至少有6个5度顶点。证明：证明：由握手定理的推论知，中5度顶点的个数只能是0，2，4，6，8这五种情形。此时6度顶点的个数分别为9，7，5，3，1这五种情形，不论何种情形，均满足结论要求。