离散数学――图论

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