离散数学第7章.ppt

离散数学第离散数学第7章章图论是一个古老的数学分支，它起源于游戏难题的研究。图论的内容十分丰富，应用得相当广泛，许多学科，诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等，都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展，图论在以上各学科中的作用越来越大，同时图论本身也得到了充分的发展。本课程在第七，八，九各章中介绍与计算机科学关系密切的图论的内容。2021/5/222第七章第七章 图的基本概念图的基本概念 第一节第一节 无向图及有向图无向图及有向图 2021/5/223内容：内容：有向图，无向图的基本概念。重点：重点：1、有向图，无向图的定义，2、图中顶点，边，关联与相邻，顶点度数等基本概念，3、各顶点度数与边数的关系及推论，2021/5/224内容：内容：有向图，无向图的基本概念。5、图的同构的定义。重点：重点：4、简单图，完全图，子图，补图的概念，2021/5/225一、图的概念。一、图的概念。1、定义定义。无序积无向图中元素为无向边，简称边。，有向图中元素为有向边，简称边。，2021/5/226一、图的概念。一、图的概念。1、定义定义。无序积2021/5/2272、图的表示法。有向图，无向图的顶点都用小圆圈表示。无向边无向边连接顶点的线段。有向边有向边以为始点，以为终点的有向线段。2021/5/228例例1、(1)无向图，图形表示如右：2021/5/229图形表示如右：例例1、(2)有向图，2021/5/22103、相关概念。(1)有限图有限图都是有限集的图。阶图阶图的图。零图零图的图。特别，若又有，称平凡图。(2)关联关联(边与点关系边与点关系)设边(或)，则称与(或)关联。2021/5/22113、相关概念。(2)2021/5/22123、相关概念。(2)孤立点孤立点无边关联的点。环环一条边关联的两个顶点重合，称此边为环(即两顶点重合的边)。2021/5/22133、相关概念。(2)悬挂点悬挂点只有一条边与其关联的点，所对应的边叫悬挂边。(3)平行边平行边关联于同一对顶点的若干条边称为平行边。平行边的条数称为重数。多重图多重图含有平行边的图。简单图简单图不含平行边和环的图。2021/5/2214如例1的(1)中，与关联的次数均为1，与关联的次数为2，边都是相邻的，为孤立点，为悬挂点，为悬挂边，为环，为平行边，重数2，为多重图。2021/5/22154、完全图设为阶无向简单图，若中每个顶点都与其余个顶点相邻，则称 为 阶阶无向完全图无向完全图，记作。若有向图的任一对顶点，既有有向边又有有向边，则称为有向完全图有向完全图。2021/5/2216例如：2021/5/2217二、顶点的度数，握手定理。二、顶点的度数，握手定理。1、顶点的度数(简称度)。无向图的度数记，指与，相关联的边的条数。有向图的度数，2021/5/2218二、顶点的度数，握手定理。二、顶点的度数，握手定理。1、顶点的度数(简称度)。最大度最大度 最小度最小度对有向图相应地还有，。2021/5/2219如例1的(2)中，。2021/5/2220设为图的顶点集，称 为的度数序列度数序列。2、握手定理。定理定理1：设图为无向图或有向图，为边数)，(则2021/5/2221定理定理2：设为有向图，则，。2、握手定理推论：推论：任何图中，度为奇数的顶点个数为偶数。2021/5/2222例例2、(1)能成为图的度数，序列吗？为什么？(2)已知图中有10条边，4个3度顶点，其余顶点的度数均小于3，问中至少有多少个顶点？为什么？2021/5/2223三、子图，补图。三、子图，补图。1、子图定义：子图定义：设是两个图，若，且，则称是的子图子图，是的母图母图，记作。真子图真子图 且(即或)。生成子图生成子图且。2021/5/2224三、子图，补图。三、子图，补图。导出子图导出子图 非空，以为顶点集，以两端均在中的边的全体为边集的的子图，称的导出子图。非空，以为边集，以中边关联的顶点的全体为顶点集的的子图，称的导出子图。2021/5/2225例例3、上图中，(1)(6)都是(1)的子图，其中(2)(6)为真子图，(1)(5)为生成子图。2021/5/22262、补图定义补图定义。设为无向完全图，为无向简单图，其中，则称，相对于互为补图，记，。2021/5/2227如例3中，2021/5/2228四、图的同构。四、图的同构。定义定义：设两个无向图，若存在双射函数，使得对于任意的，当且仅当并且与重数相同，则称与同构同构，记作。2021/5/2229例例4、2021/5/2230例例5、(1)画出4个顶点，3条边的所有非同构的无向简单图。解：解：只有如下3个图：2021/5/2231例例5、(2)画出3个顶点，2条边的所有非同构的有向简单图。解：解：只有如下4个图：2021/5/2232第二节第二节 通路，回路，图的连通性通路，回路，图的连通性 2021/5/2233内容：内容：图的通路，回路，连通性。重点：重点：1、通路，回路，简单通路，回路，初级通路，回路的定义，2、图的连通性的概念，3、短程线，距离的概念。2021/5/2234一、通路，回路。一、通路，回路。1、通路通路(回路回路)中顶点和边的交替序列，其中(无向图)，或(有向图)，始点始点，终点终点，称为到的通路通路。当时，为回路回路。2021/5/2235一、通路，回路。一、通路，回路。2、简单通路，简单回路。简单通路简单通路(迹迹)简单回路简单回路(闭迹闭迹)复杂通路复杂通路(回路回路)2021/5/2236一、通路，回路。一、通路，回路。3、初级通路，初级回路。初级通路初级通路(路径路径)初级回路初级回路(圈圈)初级通路(回路)简单通路(回路)，但反之不真。4、通路，回路 的长度中边的数目。2021/5/2237例例1、(1)图(1)中，从的通路有：到长度3长度6长度62021/5/2238例例1、(1)图(1)中，从的通路有：到初级通路简单通路复杂通路2021/5/2239例例1、(2)长度3长度4长度7图(2)中过)有：的回路(从到2021/5/2240例例1、(2)初级回路(圈)初级回路(圈)复杂回路图(2)中过)有：的回路(从到2021/5/22415、图中最短的回路。如图：2021/5/22426、性质。定理：定理：阶图中，若从顶点 到存在通路，则从到存在长度小于等于在一个的通路。推论：推论：阶图中，若从顶点 到存在通路，则从到存在长度小于等于在一个的初级通路。2021/5/22436、性质。定理：定理：阶图中，若 到自身存在回路，则从到自身存在长度小于等于 的回路。在一个推论：推论：阶图中，若 到自身存在一个简单回路，则从 到自身存在长度小于等于的初级回路。在一个2021/5/22446、性质。由以上定理可知，在阶图中，任何一条初级通路的长度任何一条初级回路的长度2021/5/2245二、图的连通性。二、图的连通性。1、连通，可达。无向图中，从 到存在通路，称到是连通的连通的(双向双向)。有向图中，从 到存在通路，称可达可达(注意方向)。2021/5/22462、短程线，距离。短程线连通或可达的两点间长度最短的通路。距离短程线的长度，记无向图有向图2021/5/22472、短程线，距离。若之间无通路(或不可达)，规定距离满足：(1)，时，等号成立。(2)若是无向图，还具有对称性，。2021/5/22483、无向图的连通。为连通图为连通图是平凡图，或都是连通的。中任两点为非连通图为非连通图中至少有两点不连通。2021/5/22493、无向图的连通。设是一个无向图，是中顶点之间的连通关系，则是等价关系等价关系。设将划分成个等价类：，由它们导出的子图称为的连通分支连通分支，其个数记为2021/5/22504、有向图的连通。中任一对顶点都互相可达(双向)中任一对顶点至少一向可达略去 中有向边的方向后得到的无向图连通连通强连通单向连通弱连通强连通单向连通弱连通2021/5/2251例例2、强连通单向连通2021/5/2252例例2、单向连通弱连通非连通图2021/5/2253第三节第三节 图的矩阵表示图的矩阵表示2021/5/2254内容：内容：关联矩阵，邻接矩阵，可达矩阵。重点：重点：1、有向图，无向图的关联矩阵，2、有向图的邻接矩阵。了解：了解：有向图的可达矩阵。2021/5/2255一、无向图的关联矩阵。一、无向图的关联矩阵。1、设无向图，的关联矩阵，2021/5/2256例例1、无向图(下图所示)，求。解：2021/5/22572、性质性质。(1)(2)(3)握手定理2021/5/2258(4)，当且仅当为孤立点。2、性质性质。(5)若第 列与第列相同，则说明 与为平行边。2021/5/2259二、有向图的关联矩阵。二、有向图的关联矩阵。1、设无环有向图，的关联矩阵，其中2021/5/2260例例2、有向图(下图所示)，求。解：解：2021/5/22612、性质性质。(1)(2)(3)2021/5/2262三、有向图的邻接矩阵。三、有向图的邻接矩阵。1、设有向图，的邻接矩阵，其中指邻接到的边的条数(非负整数)。2021/5/2263例例3、有向图(下图所示)，求。解：解：2021/5/22642、性质性质。(1)(2)(3)(4)为中环的个数。2021/5/22653、求中长度为 的通路数和回路数。(1)令矩阵乘法其中表示从到长度为2的通路数或回路数。2021/5/22663、求中长度为 的通路数和回路数。考虑，简记为。其中表示从到长度为或回路数。的通路数中长度为为的通路总数，其中为 中长度为 的回路总数。2021/5/22673、求中长度为 的通路数和回路数。(2)设则中元素为中到长度小于等于的通路总数，为中长度小于等于 的通路总数，其中为 中长度小于等于的回路总数。2021/5/2268例例4、在例3的有向图中求，。解：解：，2021/5/2269四、有向图的可达性矩阵。四、有向图的可达性矩阵。(了解了解)设为有向图，令，2021/5/2270四、有向图的可达性矩阵。四、有向图的可达性矩阵。(了解了解)可达性矩阵其中元素可由求得：2021/5/2271第七章第七章 小结与例题小结与例题2021/5/2272一、无向图与有向图。一、无向图与有向图。1、基本概念。有向图与无向图的定义；关联与邻接(相邻)；顶点的度数；零图与平凡图；简单图与多重图；完全图；子图，补图；图的同构。2021/5/2273一、无向图与有向图。一、无向图与有向图。2、运用。(1)灵活运用握手定理及其推论，(2)判断两个图是否同构，(3)画出满足某些条件的子图，补图等。2021/5/2274二、通路，回路，图的连通性。二、通路，回路，图的连通性。1、基本概念。通路和回路；无向图和有向图中顶点之间的可达关系；短程线，距离；有向图连通的分类。2021/5/2275二、通路，回路，图的连通性。二、通路，回路，图的连通性。2、运用。(1)判断有向图或无向图中通路(回路)的类型。(2)求短程线和距离。(3)判断有向图连通的类型。2021/5/2276三、图的矩阵表示。三、图的矩阵表示。1、基本概念。无向图的关联矩阵，有向图的关联矩阵和邻接矩阵。2、运用。(1)关联矩阵的行和、顶点度数间的关系。(2)由有向图的邻接矩阵的次幂求从一顶点到另一顶点的长度为 的通路数。2021/5/2277例例1、设图，其中，分别由下面给出。判断哪些是简单图，哪些是多重图？(1)(2)(3)简单图多重图不是2021/5/2278例例1、设图，其中，分别由下面给出。判断哪些是简单图，哪些是多重图？(4)(5)(6)简单图多重图不是2021/5/2279例例2、下列各序列中，可以构成无向简单图的度数序列的有哪些？(1)可以(2)不可以(3)可以(4)不可以(5)不可以2021/5/2280例例3、右图所示的无向图中，分别求：不同的初级通路(路径)。(1)之间所有解：解：有7条，分别为，和，。(2)之间的短程线。(3)。解：解：。解：解：。2021/5/2281例例4、(1)画出完全图的所有非同构的生成子图。解：解：2021/5/2282例例4、(1)画出完全图的所有非同构的生成子图。解：解：2021/5/2283例例4、(1)画出完全图的所有非同构的生成子图。(2)的生成子图有几个是连通图？解：解：有6个：2021/5/2284例例5、下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？强连通单向连通弱连通2021/5/2285例例5、下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？单向连通强连通强连通2021/5/2286例例6、已知图的邻接矩阵，(1)2021/5/2287例例6、已知图的邻接矩阵，(2)从 到长度为2的通路数。解：解：因，所以从 到 长度为2的通路数为2。2021/5/2288例例6、已知图的邻接矩阵，(3)从 到长度为3的通路数。解：解：因，所以从 到 长度为3的通路数为5。2021/5/2289例例6、已知图的邻接矩阵，(4)过长度为3的回路数。解：解：因，所以过 长度为3的回路数为3。2021/5/2290例例7、下列各图中各有多少个顶点。(1)16条边，每个顶点的度数均为2。解：解：设顶点数为，由握手定理，有，解得。解：解：设顶点数为，解得。(2)21条边，3个度数为4的顶点，其余顶点的度数均为3。有，由握手定理，2021/5/2291例例7、下列各图中各有多少个顶点。(3)24条边，每个顶点的度数均相同。解：解：设顶点数为，由握手定理，设每个顶点的度数均为，其正整数解有：，。，则有2021/5/2292例例7、下列各图中各有多少个顶点。(3)24条边，每个顶点的度数均相同。解：解：所以答案有以下八种：2个24度顶点，24个2度顶点，3个16度顶点，16个3度顶点，4个12度顶点，12个4度顶点，6个8度顶点，8个6度顶点。2021/5/2293例例8、设为9个顶点的无向图，每个顶点的度数不是5就是6。证明 中至少有5个6度顶点或者至少有6个5度顶点。证明：证明：由握手定理的推论知，中5度顶点的个数只能是0，2，4，6，8这五种情形。此时6度顶点的个数分别为9，7，5，3，1这五种情形，不论何种情形，均满足结论要求。2021/5/2294谢谢！