离散数学——图论.ppt

第四篇图论 本篇包括第八章、第九章。主要内容有图的基本理论、欧拉图、哈密尔图、树等。v图论是一个古老而又年轻的数学分支，它诞生于18世纪，它是用图的方法研究客观世界的一门科学，为任何一个包含二元关系的系统提供了一个直观而严谨的数学模型，因此物理系、化学、生物学、工程科学、管理科学、计算机科学等各个领域都有图论的足迹。图论的发展 v图论的产生和发展经历了二百多年的历史，从1736年到19世纪中叶是图论发展的第一阶段。v第二阶段大体是从19世纪中叶到1936年，主要研究一些游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。v一些图论中的著名问题如四色问题(1852年)和哈密尔顿环游世界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。v1847年德国的克希霍夫(G.R.Kirchoff)将树的概念和理论应用于工程技术的电网络方程组的研究。v1857年英国的凯莱(A.Cayley)也独立地提出了树的概念，并应用于有机化合物的分子结构的研究中。v1936年匈牙利的数学家哥尼格(D.Konig)发表了第一部集图论二百年研究成果于一书的图论专著有限图与无限图理论，这是现代图论发展的里程碑，标志着图论作为一门独立学科。v现在图论的主要分支有图论、超图理论、极值图论、算法图论、网络图论和随机图论等。v第三阶段是1936年以后。由于生产管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现，大大促进了图论的发展。现代电子计算机的出现与广泛应用极大地促进了图论的发展和应用。v目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域都有应用。v在计算机科学中计算机科学的核心之一就是算法的设计与理论分析，而算法是以图论与组合数学为基础；图论与组合数学关系也非常密切，已正式成为计算机诸多分支中一种有力的基础工具。v因而，作为计算机专业人员，了解和掌握图论的基本原理和方法是必要的。v图论交叉地运用了拓扑学、群论和数论知识，其定理证明难度高低不等，有的简单易懂，有的难于理解，但其每一步证明都需要技巧，每一个定理都像艺术平一样值得品味与推敲。v因此，尽管本教材介绍的是较为基础的图论内容，但阅读理解与完成习题是学习图论必不可少的步骤。v图是人们日常生活中常见的一种信息载体，其突出的特点是直观、形象。图论，顾名思义是运用数学手段研究图的性质的理论，但这里的图不是平面坐标系中的函数，而是由一些点和连接这些点的线组成的结构。v在图形中，只关心点与点之间是否有连线，而不关心点具体代表哪些对象，也不关心连线的长短曲直，这就是图的概念。v当研究的对象能被抽象为离散的元素集合和集合上的二元关系时，用关系图表示和处理十分方便。8.1图的基本概念v图论的起源可以追溯到1736年由瑞士数学家欧拉(Leonhard Euler，1707-1783)撰写的一篇解决“哥尼斯堡七桥问题”的论文。哥尼斯堡七桥问题v把四块陆地用点来表示，桥用点与点连线表示。v欧拉将问题转化为：任何一点出发，是否存在通过每条边一次且仅一次又回到出发点的路？欧拉的结论是不存在这样的路。显然，问题的结果并不重要，最为重要的是欧拉解决这个问题的中间步骤，即抽象为图的形式来分析这个问题。v这是一种全新的思考方式，由此欧拉在他的论文中提出了一个新的数学分支，即图论，因此，欧拉也常常被图论学家称为图论之父。欧拉v欧拉是著作较多的著名数学家之一，曾发表了886篇论文，出版了近90本书。在数学界的许多分支如数论、几何、组合数学等领域的很多定理和公式都以欧拉命名的。欧拉简介图的基本概念v定义8.1图（Graph）G包括一个非空的对象的集合 V=v1,v2,vn与有限的V中两个对象构成的无序对构成的集合 E=e1,e2,em，前者称为结点集(Vertex set)，后者称为边集（Edge set）。一般用G=表示图。v例子：教材116页例8.1，例8.2v根据图中边的方向，分为有向图、无向图。v边关联：有向边lk=(vi,vj)，其中vi称为起点，vj称为终点。无论边是否有向，称lk与vi,vj相关联。v邻接：边lk=(vi,vj)，称vi,vj是邻接的点，若干条边关联同一个结点，则称边是邻接的。v环：边lk=(vi,vj)，vi与vj是同一个点。v孤立点：不与任何点相邻接的点。定义图的子图v子图：设G=，G=，若V是V的子集，E是E的子集，则G是G的子图。v真子图：若V是V的子集，E是E的真子集。v生成子图：V=V，E是E的子集。v举例说明一个图的子图。定义（n,m）图v(n,m)图：由n个结点，m条边组成的图。v零图：m=0。即（n,0）图，有n个孤立点。v平凡图：n=1,m=0。即只有一个孤立点。v完全图：一个（n,m）图G，其n个结点中每个结点均与其它n-1个结点相邻接，记为Kn。v无向完全图：m=n(n-1)/2v有向完全图：m=n(n-1)v 举例说明以上几种图。定义补图v设图G=，G=，若G=是完全图，且EE=空集，则称G是G的补图。v事实上，G与G互为补图。图的同构v看一下教材120页一个图的几个不同图形。v我们常将一个图和它的图形等同起来，但这是两个不同的概念，给出图形就确定了一个图，然而一个图的图形是不唯一的。v考虑图和图形的不同。v定义同构：图G=，G=，如果它们的结点间存在一一对应关系，且这种对应关系也反映在边的结点对中，对于有向边，对应的结点对还保持相同的顺序，则称两图是同构的。v例1：教材121页。结点次数v引出次数：有向图中以结点v为起点的边的条数称为v的引出次数，记 v引入次数：有向图中以结点v为终点的边的条数称为v的引出次数，记 v结点次数：有向图中引出次数和引入次数之和称为结点次数；无向图中与结点v相关联的边的条数称为V的次数。统一为记deg(v)。握手定理v定理：G=是(n,m)图,V=v1,v2,vn 即所有结点次数之和等于边数的2倍。v定理：有向图中引入次数之和等于引出次数之和，都等于边数。v推论：任一图中，次数为奇数的结点（即奇结点）的个数必为偶数。正则图v所有结点均有相同次数d的图称为d次正则图。v如4阶的完全图是3次正则图，是对角线相连的四边形。v试画出两个2次正则图。两图同构需满足的条件v若两个图同构，必须满足下列条件：（1）结点个数相同 （2）边数相同 （3）次数相同的结点个数相同v例子多重图与带权图v定义多重图：包含多重边的图。v定义简单图：不包含多重边的图。v定义有权图：具有有权边的图。v定义无权图：无有权边的图。练习题-关于图中点的次数问题v1.设图G是3次正则图，且2n-3=m，则n、m是多少？v2.设G是（n,m）图，G中结点次数要么为k，要么为k+1，则次数为k的结点有几个？v3.设G有10条边，4个3度结点，其余结点次数均小于等于2，则G中至少有几个结点？解答v1.v2.设有x个k度结点，则v3.设其余结点次数均为2，有 43+2x=102=20 得x=4，因此G中至少有8个结点。8.2通路、回路与连通性v定义：通路与回路 设有向图G=，考虑G中一条边的序列（vi1,vi2,vik）,称这种边的序列为图的通路。Vi1、vik分别为起点、终点。通路中边的条数称为通路的长度。若通路的起点和终点相同，则称为回路。简单通路、基本通路v简单通路：通路中没有重复的边。v基本通路：通路中没有重复的点。v简单回路和基本回路。v基本通路一定是简单通路，但反之简单通路不一定是基本通路。基本回路必是简单回路。v定理：一个有向（n,m）图中任何基本通路长度n-1。任何基本回路的长度n。v任一通路中如果删去所有回路，必得基本通路。v任一回路中如删去其中间的所有回路，必得基本回路。可达性的定义v定义可达性：从一个有向图的结点vi到另一个结点vj间，如果存在一条通路，则称vi到vj是可达的。v同样，可以将可达性的概念推广到无向图。v利用通路、回路的概念，可研究计算机科学中的许多问题。连通性v定义：无向图，若它的任何两结点间均是可达的，则称图G是连通图；否则为非连通图。v定义：有向图，如果忽略图的方向后得到的无向图是连通的，则称此有向图为连通图。否则为非连通图。有向连通图v定义：设G为有向连通图，v强连通：G中任何两点都是可达的。v单向连通：G中任何两结点间，至少存在一个方向是可达的。v弱连通：忽略边的方向后得到的无向图是连通的。连通分支v无向图中的连通性是等价关系。v按照等价关系，可将图G中的结点进行分类，一个连通的子图即是一个等价类，称为G的一个连通分支。vP（G）表示连通分支的个数。连通图的连通分支只有一个。练习题-图的连通性问题v1.若图G是不连通的，则补图是连通的。v提示：直接证法。根据图的不连通，假设至少有两个连通分支；任取G中两点，证明这两点是可达的。v2.设G是有n个结点的简单图，且|E|(n-1)(n-2)/2，则G是连通图。v提示：反证法。设有两个连通分支，这两个分支至多是完全图。由此得到图中点与边之间的数量关系。8.3欧拉图v欧拉图产生的背景就是前面的七桥问题。v定义：图G的回路，若它通过G中的每条边一次，这样的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。v定义欧拉通路：通过图G中每条边一次的通路（非回路）称为欧拉通路。判断欧拉通路的定理v定理：无向连通图G是欧拉图的充要条件是G的每个结点均具有偶次数。v定理：无向连通图G中结点vi与vj存在欧拉通路的充要条件是vi与vj的次数均为奇数，而其他结点次数均为偶数。例子v邮递员信件问题v城市街道问题v一笔画问题v公交线路问题有向欧拉图的判定v一个有向图G有欧拉通路当且仅当G是连通的，且除了两个结点外，其余结点的引入次数等于引出次数，且这两结点中，一个结点的入度比出度大1，另一个结点的入度比出度多1.v一个有向图G是欧拉图当且仅当G是连通的，且所有结点的入度等于出度。8.4哈密尔顿图v与欧拉图类似的是哈密尔顿图，它起源于环游世界的问题。v定义：若图G的一个回路通过G中每个点一次，这样的回路称为哈密尔顿回路，有这种回路的图称为哈密尔顿图。v显然欧拉回路是简单回路，无重复边；哈密尔顿图是基本回路，无重复点。v关于如何判断哈密尔顿通路与回路，至今尚未找到它的充要条件，只有一些充分条件和必要条件。H-图性质定理v定理：设无向图G=是哈密尔顿图，非空集V1是V的子集，则P（G-V1）|V1|。vP（G-V1）是从G中删去V1（包括与V1中结点相关联的边）后所得的图的连通分支。v利用这个定理有时可证明一个图不是哈密尔顿图。P（G-V1）|V1|说明不是H-图。v定理：设G=是无向简单图，|V|3，如果G中每对结点次数之和大于等于|V|，则G必为哈密尔顿图。v定理：设有向图，|V|2，若所有有向边均用无向边代替后，所得无向图中含生成子图Kn,则G存在哈密尔顿通路。v推论：n阶有向完全图(n2)为哈密尔顿图。判断H-图的一些充分或必要条件vH-图一定是连通图，且每个结点次数2。v若G是n阶图，则H-通路是长度为n-1的基本通路。v若存在次数为1的结点，则G没有H-回路。v欧拉图遍历边，哈密尔顿图遍历点。在H-图中，H-回路不一定是唯一的。8.5图的矩阵表示v用矩阵的理论和分析方法来研究图论，将图的一些问题转换为矩阵运算问题，更适合于计算机处理。v图在计算机中就是以矩阵形式存贮和读取的。v也可借助图的理论和方法研究矩阵中的问题。有向图的邻接矩阵v定义邻接矩阵：设有向图G=，设各点按一定次序排列，构造矩阵 则称A为图G的邻接矩阵。v零图的邻接矩阵：A为零矩阵。v完全图的邻接矩阵：A除对角线元素为0外，其余元素全为1。v无向图的邻接矩阵：将无向边用两条方向相反的有向边代替，将无向图转成有向图。v无向图的邻接矩阵是对称阵。v邻接矩阵的概念还可推广到多重图和带权图，考虑如何表示。v一个图的邻接矩阵完整的刻画了图中结点间的邻接关系，但当结点次序发生变化时，对应的邻接矩阵也随之变化。一般将V强行排序，图与邻接矩阵就一一对应了。v同构的两个图，对应结点间的邻接关系相同，则它们的邻接矩阵或者相同或者其中一个通过行、列交换可得到另一个。v例子有向图的邻接矩阵和次数v设A为有向图G=的邻接矩阵，|V|=n，有无向图的邻接矩阵和次数v设A为无向图G=的邻接矩阵，则A=AT。有An=AAA的元素的意义vn=1时，aij=1表示存在一条边（vi,vj）或者从vi到vj存在一条长度为1的通路。若vi与vj是同一个点，则表示回路。v当n=2时，记B=A2=(bij)，bij表示从vi到vj存在的长度为2的通路的条数。v当n=k时，记C=Ak=(cij)，cij表示从vi到vj存在的长度为k的通路的条数。v例子可达性矩阵v记Rn=A+A2+An=(rij)nn，由上一部分Ak的意义知，rij表示给出了从vi到vj的所有长度从1到n的通路的数目之和。v一般我们并不关心两点之间有几条通路，通路的长度是多少等等。v若rij=0，则表示从vi到vj是不可达的；若rij0，则vi到vj是可达的。v考虑：为什么计算到An即可判断vi到vj是否可达？v记 称P为G的可达性矩阵或通路矩阵。一个图的可达矩阵给出了图中各结点间是否可达及图中是否有回路。v例：求G=的可达矩阵，V、E如下：V=v1,v2,v3,v4，E=(v1,v2),(v2,v3),(v2,v4),(v3,v2),(v3,v4),(v3,v1),(v4,v1)。v解：v由于根据Rn计算可达矩阵较复杂，在以后的计算中引入布尔运算。v例子：教材136页例8.11是否存在递归调用？多重图及有权图的矩阵表示v举例说明。矩阵与无向图的连通性v设G为无向图，由连通性定义知，任两个结点都是可达的。vG连通当且仅当G的可达矩阵P除对角线外，所有元素均为1。矩阵与有向图的连通性v设G为有向图，设P为G的可达矩阵。（1）G强连通当且仅当P除对角线外均为1。（2）G单向连通当且仅当P=P+PT，P除对角线外其余元素均为1。（3）G弱连通当且仅当A=A+AT，P 是A的可达矩阵，P除对角线外其余元素均为1。第九章常用图v本章介绍图论中几种常用图的基本原理和方法。v树是图论中重要概念之一，它在计算机科学中如算法分析、数据结构等有广泛应用。v平面图v两步图9.1树v定义：树是不包含回路的连通图。v在树中次数为1的结点称为叶，次数大于1的结点称为分支结点。v例树的定理v定理9.1：在（n,m）树中，必有m=n-1。证明：对n用归纳法。v定理9.2：具有两个结点以上的树必至少有两片叶。证明：用反证法、直接法两种方法。v定理9.3：图G是树的充要条件是G的每对结点间只有一条通路。树的等价定义v设图T=是（n,m）图，T是树。vT连通无回路。vT连通且m=n-1。vT无回路，且m=n-1。vT是最小连通图。vT是最大无回路图。vT的每对结点间恰有唯一一条通路。有向树v定义：在有向图中若不考虑边的方向而构成树，则称为有向树。v一般常用的有向树为外向树和内向树。外向树v定义外向树：满足下列条件的有向树T称为外向树。（1）T有且仅有一个根。（引入次数为0）（2）T的其它结点的引入次数均为1.（3）T有叶。（引出次数为0，当然引入次数仍为1）v定义：由外向树的根到结点vi的通路长度称为结点vi的级。外向树的相关概念v两个结点如从根到结点的通路长度相等，则它们同级。否则不同级。v可用外向树表示上面家属关系。例子：红楼梦人物简表。双亲，儿子，祖先，子孙，兄弟。v从家属树中引入有序树的概念。兄弟间有一定的次序。定义内向树v定义内向树：满足下列条件的有向树T称为内向树。（1）T有且仅有一个根。（引出次数为0）（2）T的其它结点的引出次数均为1.（3）T有叶。（引入次数为0，当然引出次数仍为1）v内向树的概念和性质与外向树类似，故以后只考虑外向树。m元树v定义：设有n个结点的外向树T=，若 vi的引出次数m，称T为m元树；若除了叶外，vi的引出次数=m，则称T为m元完全树。v例：用二元树表示算术表达式。v例：计算机中的程序流程图也可用有序二元树表示。v二元树的真正作用在于：任一外向树均可用二元树表示。v例子。生成树v定义：设G=是一连通图，T=是G的一个子图，T是树，且V=V，E是E的子集，称T是G的生成树。v由一连通图G寻找它的生成树过程如下：在G中寻找基本回路，找到后在此回路中删去一边，并继续寻找直至G中无基本回路为止。v一般而言，G的生成树不是唯一的。求生成树v若G=（n,m）图，得到的生成树为（n,m-1）图，故由G得到一个生成树，必须删去m-(n-1)=m-n+1条边，称之为G的基本回路的秩。v练习：求一图的生成树。v寻找一个图的生成树是很有实际价值的。v一个连通图可以有多个生成树，寻找生成树使它的总长度最短的问题即为最短树问题。即求最小生成树问题。v目前已有很多成熟的算法。9.2平面图v定义平面图：一个图不管它的图形的几何形状如何改变，它们的边之间总有交叉现象出现，则称此图为非平面图；否则称为平面图。v或定义：设G=是无向图，若存在G的一种图示，使得任意两条边不相交，则称为平面图。v无回路的图是平面图。v有回路，无相交交叉边，G是平面图。v有回路有交叉边，则将边分别置于某基本回路的内或外，然后判定是否是平面图。平面图的区域v定义：设G是连通平面图，由图中的边所包围的最小平面块称为平面图的区域。v包围该区域的边所构成的回路称为这个区域的边界。v区域面积有限称为有限区域；面积无限称为无限区域。v每个平面图只有唯一一个无限区域。v一个平面图将整个平面完全划分。v例子v定理：（Euler定理）设G是(n,m)连通平面图，区域数为r,则有 n-m+r=2v证明：对m 进行归纳法证明。m=1时，由G连通，n=2或n=1。设m=k-1时，有n-m+r=2，证m=k时，G有n个结点，r个区域。有两种情况：G有次数为1的结点；G没有次数为1的结点。v定理：设G是一个(n,m)平面连通图，且G中无环，m1，则必有 m3n-6。证明：已知图G的每个区域边界的边数至少为3。G中每条边至多同时作为两个不同区域边界的边。故有 3r 2m。v一个连通平面图一般应满足m3n-6，否则是非平面图。判断定理v定义：基本缩减。v定理：一个图是平面图的充要条件是它的任何子图都不可能缩减成下面的两个图：K5和K3,3 v例子9.3两步图v定义：设无向图G=有两个V的子集V1、V2，两个相互分离，且满足V1V2=V，图G的每一边e均有e=(vi,vj),其中viV1,vjV2，称G为两步图。v在G中，V被划分为V1、V2，且在V1、V2内各结点间无边相连，故称V1、V2为G的互补结点子集。v定理：图G是两步图的充要条件是G的所有回路长度均为偶数。v例子