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