离散数学——图论.ppt

《离散数学——图论.ppt》由会员分享，可在线阅读，更多相关《离散数学——图论.ppt（90页珍藏版）》请在优知文库上搜索。

1、第四篇图论 本篇包括第八章、第九章。主要内容有图的基本理论、欧拉图、哈密尔图、树等。v图论是一个古老而又年轻的数学分支，它诞生于18世纪，它是用图的方法研究客观世界的一门科学，为任何一个包含二元关系的系统提供了一个直观而严谨的数学模型，因此物理系、化学、生物学、工程科学、管理科学、计算机科学等各个领域都有图论的足迹。图论的发展 v图论的产生和发展经历了二百多年的历史，从1736年到19世纪中叶是图论发展的第一阶段。v第二阶段大体是从19世纪中叶到1936年，主要研究一些游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。v一些图论中的著名问题如四色问题(1852年)和哈密尔顿环游世界问题(1

2、856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。v1847年德国的克希霍夫(G.R.Kirchoff)将树的概念和理论应用于工程技术的电网络方程组的研究。v1857年英国的凯莱(A.Cayley)也独立地提出了树的概念，并应用于有机化合物的分子结构的研究中。v1936年匈牙利的数学家哥尼格(D.Konig) 发表了第一部集图论二百年研究成果于一书的图论专著有限图与无限图理论，这是现代图论发展的里程碑，标志着图论作为一门独立学科。v现在图论的主要分支有图论、超图理论、极值图论、算法图论、网络图论和随机图论等。v第三阶段是1936年以后。由于生产管理、军事、交通运输、计算

3、机和通讯网络等方面的大量问题的出现，大大促进了图论的发展。现代电子计算机的出现与广泛应用极大地促进了图论的发展和应用。v目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域都有应用。 v在计算机科学中计算机科学的核心之一就是算法的设计与理论分析，而算法是以图论与组合数学为基础；图论与组合数学关系也非常密切，已正式成为计算机诸多分支中一种有力的基础工具。v因而，作为计算机专业人员，了解和掌握图论的基本原理和方法是必要的。v图论交叉地运用了拓扑学、群论和数论知识，其定理证明难度高低不等，有的简单易懂，有的难于理解，但其每一步证明都需要技巧

4、，每一个定理都像艺术平一样值得品味与推敲。v因此，尽管本教材介绍的是较为基础的图论内容，但阅读理解与完成习题是学习图论必不可少的步骤。 v图是人们日常生活中常见的一种信息载体，其突出的特点是直观、形象。图论，顾名思义是运用数学手段研究图的性质的理论，但这里的图不是平面坐标系中的函数，而是由一些点和连接这些点的线组成的结构 。v在图形中，只关心点与点之间是否有连线，而不关心点具体代表哪些对象，也不关心连线的长短曲直，这就是图的概念。v当研究的对象能被抽象为离散的元素集合和集合上的二元关系时，用关系图表示和处理十分方便。8.1图的基本概念v图论的起源可以追溯到1736年由瑞士数学家欧拉(Leonh

5、ard Euler，1707-1783)撰写的一篇解决“哥尼斯堡七桥问题”的论文。 哥尼斯堡七桥问题v把四块陆地用点来表示，桥用点与点连线表示。v欧拉将问题转化为：任何一点出发，是否存在通过每条边一次且仅一次又回到出发点的路？欧拉的结论是不存在这样的路。显然，问题的结果并不重要，最为重要的是欧拉解决这个问题的中间步骤，即抽象为图的形式来分析这个问题 。v这是一种全新的思考方式，由此欧拉在他的论文中提出了一个新的数学分支，即图论，因此，欧拉也常常被图论学家称为图论之父。欧拉v欧拉是著作较多的著名数学家之一，曾发表了886篇论文，出版了近90本书。在数学界的许多分支如数论、几何、组合数学等领域的很

6、多定理和公式都以欧拉命名的。 欧拉简介图的基本概念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)，

7、 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=是

8、完全图，且EE=空集，则称G是G的补图。v事实上，G与G互为补图。图的同构v看一下教材120页一个图的几个不同图形。v我们常将一个图和它的图形等同起来，但这是两个不同的概念，给出图形就确定了一个图，然而一个图的图形是不唯一的。v考虑图和图形的不同。v定义同构：图G=， G=，如果它们的结点间存在一一对应关系，且这种对应关系也反映在边的结点对中，对于有向边，对应的结点对还保持相同的顺序，则称两图是同构的。v例1：教材121页。结点次数v引出次数：有向图中以结点v为起点的边的条数称为v的引出次数，记 v引入次数：有向图中以结点v为终点的边的条数称为v的引出次数，记 v结点次数：有向图中引出次数和引

9、入次数之和称为结点次数；无向图中与结点v相关联的边的条数称为V的次数。统一为记deg(v)。deg( )vdeg( )v握手定理v定理：G=是(n,m)图,V=v1,v2,vn 即所有结点次数之和等于边数的2倍。v定理：有向图中引入次数之和等于引出次数之和，都等于边数。v推论：任一图中，次数为奇数的结点（即奇结点）的个数必为偶数。 i 1deg()2nvim正则图v所有结点均有相同次数d的图称为d次正则图。v如4阶的完全图是3次正则图，是对角线相连的四边形。v试画出两个2次正则图。两图同构需满足的条件v若两个图同构，必须满足下列条件： （1）结点个数相同 （2）边数相同 （3）次数相同的结点个

10、数相同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度结点，则i1236d eg ()29nnmnvimm()(1)2(1)2kxnxkmxn kmv3.设其余结点次数均为2，有 43+2x=102=20 得x=4，因此G中

11、至少有8个结点。8.2通路、回路与连通性v定义：通路与回路 设有向图G=，考虑G中一条边的序列（vi1,vi2, vik）,称这种边的序列为图的通路。 Vi1、vik分别为起点、终点。通路中边的条数称为通路的长度。 若通路的起点和终点相同，则称为回路。简单通路、基本通路v简单通路：通路中没有重复的边。v基本通路：通路中没有重复的点。v简单回路和基本回路。v基本通路一定是简单通路，但反之简单通路不一定是基本通路。基本回路必是简单回路。v定理：一个有向（n,m）图中任何基本通路长度n-1。任何基本回路的长度n。v任一通路中如果删去所有回路，必得基本通路。v任一回路中如删去其中间的所有回路，必得基本

12、回路。可达性的定义v定义可达性：从一个有向图的结点vi到另一个结点vj间，如果存在一条通路，则称vi到vj是可达的。v同样，可以将可达性的概念推广到无向图。v利用通路、回路的概念，可研究计算机科学中的许多问题。连通性v定义：无向图，若它的任何两结点间均是可达的，则称图G是连通图；否则为非连通图。v定义：有向图，如果忽略图的方向后得到的无向图是连通的，则称此有向图为连通图。否则为非连通图。有向连通图v定义：设G为有向连通图，v强连通：G中任何两点都是可达的。v单向连通：G中任何两结点间，至少存在一个方向是可达的。v弱连通：忽略边的方向后得到的无向图是连通的。连通分支v无向图中的连通性是等价关系。

13、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中的每条边一次，这样的回路称为欧拉回路

14、。具有欧拉回路的图称为欧拉图。v定义欧拉通路：通过图G中每条边一次的通路（非回路）称为欧拉通路。判断欧拉通路的定理v定理：无向连通图G是欧拉图的充要条件是G的每个结点均具有偶次数。v定理：无向连通图G中结点vi与vj存在欧拉通路的充要条件是vi与vj的次数均为奇数，而其他结点次数均为偶数。例子v邮递员信件问题v城市街道问题v一笔画问题v公交线路问题有向欧拉图的判定v一个有向图G有欧拉通路当且仅当G是连通的，且除了两个结点外，其余结点的引入次数等于引出次数，且这两结点中，一个结点的入度比出度大1，另一个结点的入度比出度多1.v一个有向图G是欧拉图当且仅当G是连通的，且所有结点的入度等于出度。8.

15、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定理：设

16、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的邻接矩阵。0( ,)EA1( ,)Eijijijijv vaav vn n（ ） ,其中v零图的邻接矩阵：A为零矩阵。v完全图的邻接矩阵：A除对角线元素为0外，其余元素全为1。v无向图的邻接矩阵：将无向边用两条方向相反的有向边代替，将无向图