离散数学-图论

篇图论

本篇包括章、章。主要内容有图的基本理论、欧拉图、哈密尔图、树等。2021/5/91图论是一个古老而又年轻的数学分支，它诞生于18世纪，它是用图的方法研究客观世界的一门科学，为任何一个包含二元关系的系统提供了一个直观而严谨的数学模型，因此物理系、化学、生物学、工程科学、管理科学、计算机科学等各个领域都有图论的足迹。2021/5/92图论的发展图论的产生和发展经历了二百多年的历史，从1736年到19世纪中叶是图论发展的第一阶段。第二阶段大体是从19世纪中叶到1936年，主要研究一些游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。2021/5/93一些图论中的著名问题如四色问题(1852年)和哈密尔顿环游世界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫(G.R.Kirchoff)将树的概念和理论应用于工程技术的电网络方程组的研究。1857年英国的凯莱(A.Cayley)也独立地提出了树的概念，并应用于有机化合物的分子结构的研究中。2021/5/941936年匈牙利的数学家哥尼格(D.Konig)发表了第一部集图论二百年研究成果于一书的图论专著《有限图与无限图理论》，这是现代图论发展的里程碑，标志着图论作为一门独立学科。现在图论的主要分支有图论、超图理论、极值图论、算法图论、网络图论和随机图论等。2021/5/95第三阶段是1936年以后。由于生产管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现，大大促进了图论的发展。现代电子计算机的出现与广泛应用极大地促进了图论的发展和应用。目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域都有应用。。2021/5/96在计算机科学中计算机科学的核心之一就是算法的设计与理论分析，而算法是以图论与组合数学为基础；图论与组合数学关系也非常密切，已正式成为计算机诸多分支中一种有力的基础工具。因而，作为计算机专业人员，了解和掌握图论的基本原理和方法是必要的。2021/5/97图论交叉地运用了拓扑学、群论和数论知识，其定理证明难度高低不等，有的简单易懂，有的难于理解，但其每一步证明都需要技巧，每一个定理都像艺术平一样值得品味与推敲。因此，尽管本教材介绍的是较为基础的图论内容，但阅读理解与完成习题是学习图论必不可少的步骤。2021/5/98图是人们日常生活中常见的一种信息载体，其突出的特点是直观、形象。图论，顾名思义是运用数学手段研究图的性质的理论，但这里的图不是平面坐标系中的函数，而是由一些点和连接这些点的线组成的结构。2021/5/99在图形中，只关心点与点之间是否有连线，而不关心点具体代表哪些对象，也不关心连线的长短曲直，这就是图的概念。当研究的对象能被抽象为离散的元素集合和集合上的二元关系时，用关系图表示和处理十分方便。2021/5/910§8.1图的基本概念图论的起源可以追溯到1736年由瑞士数学家欧拉(LeonhardEuler，1707-1783)撰写的一篇解决“哥尼斯堡七桥问题”的论文。2021/5/911哥尼斯堡七桥问题把四块陆地用点来表示，桥用点与点连线表示。2021/5/912欧拉将问题转化为：任何一点出发，是否存在通过每条边一次且仅一次又回到出发点的路？欧拉的结论是不存在这样的路。显然，问题的结果并不重要，最为重要的是欧拉解决这个问题的中间步骤，即抽象为图的形式来分析这个问题。这是一种全新的思考方式，由此欧拉在他的论文中提出了一个新的数学分支，即图论，因此，欧拉也常常被图论学家称为图论之父。2021/5/913欧拉欧拉是著作较多的著名数学家之一，曾发表了886篇论文，出版了近90本书。在数学界的许多分支如数论、几何、组合数学等领域的很多定理和公式都以欧拉命名的。

2021/5/914欧拉简介2021/5/915图的基本概念定义8.1图（Graph）G包括一个非空的对象的集合

V={v1,v2,…,vn}与有限的V中两个对象构成的无序对构成的集合

E={e1,e2,…,em}，前者称为结点集(Vertexset)，后者称为边集（Edgeset）。一般用G=<V，E>表示图。2021/5/916例子：教材116页例8.1，例8.22021/5/917根据图中边的方向，分为有向图、无向图。边关联：有向边lk=(vi,vj)，其中vi称为起点，vj称为终点。无论边是否有向，称lk与vi,vj相关联。邻接：边lk=(vi,vj)，称vi,vj是邻接的点，若干条边关联同一个结点，则称边是邻接的。环：边lk=(vi,vj)，vi与vj是同一个点。孤立点：不与任何点相邻接的点。2021/5/918定义图的子图子图：设G=<V,E>，G’=<V’,E’>，若V’是V的子集，E’是E的子集，则G’是G的子图。真子图：若V’是V的子集，E’是E的真子集。生成子图：V’=V，E’是E的子集。举例说明一个图的子图。2021/5/919定义（n,m）图(n,m)图：由n个结点，m条边组成的图。零图：m=0。即（n,0）图，有n个孤立点。平凡图：n=1,m=0。即只有一个孤立点。2021/5/920完全图：一个（n,m）图G，其n个结点中每个结点均与其它n-1个结点相邻接，记为Kn。无向完全图：m=n(n-1)/2有向完全图：m=n(n-1)

举例说明以上几种图。2021/5/921定义补图设图G=<V,E>，G’=<V,E’>，若G’’=<V,E∪E’>是完全图，且E∩E’=空集，则称G’是G的补图。事实上，G与G’互为补图。2021/5/922图的同构看一下教材120页一个图的几个不同图形。我们常将一个图和它的图形等同起来，但这是两个不同的概念，给出图形就确定了一个图，然而一个图的图形是不唯一的。考虑图和图形的不同。2021/5/923定义同构：图G=<V,E>，G’=<V’,E’>，如果它们的结点间存在一一对应关系，且这种对应关系也反映在边的结点对中，对于有向边，对应的结点对还保持相同的顺序，则称两图是同构的。2021/5/924例1：教材121页。2021/5/925结点次数引出次数：有向图中以结点v为起点的边的条数称为v的引出次数，记引入次数：有向图中以结点v为终点的边的条数称为v的引出次数，记结点次数：有向图中引出次数和引入次数之和称为结点次数；无向图中与结点v相关联的边的条数称为V的次数。统一为记deg(v)。2021/5/926握手定理定理：G=<V,E>是(n,m)图,V={v1,v2,…,vn}

即所有结点次数之和等于边数的2倍。定理：有向图中引入次数之和等于引出次数之和，都等于边数。推论：任一图中，次数为奇数的结点（即奇结点）的个数必为偶数。

2021/5/927正则图所有结点均有相同次数d的图称为d次正则图。如4阶的完全图是3次正则图，是对角线相连的四边形。试画出两个2次正则图。2021/5/928两图同构需满足的条件若两个图同构，必须满足下列条件：（1）结点个数相同（2）边数相同（3）次数相同的结点个数相同例子2021/5/929多重图与带权图定义多重图：包含多重边的图。定义简单图：不包含多重边的图。定义有权图：具有有权边的图。定义无权图：无有权边的图。2021/5/930练习题----关于图中点的次数问题

1.设图G是3次正则图，且2n-3=m，则n、m是多少？2.设G是（n,m）图，G中结点次数要么为k，要么为k+1，则次数为k的结点有几个？3.设G有10条边，4个3度结点，其余结点次数均小于等于2，则G中至少有几个结点？2021/5/931解答1.2.设有x个k度结点，则2021/5/9323.设其余结点次数均为2，有

4×3+2x=10×2=20

得x=4，因此G中至少有8个结点。2021/5/933§8.2通路、回路与连通性定义：通路与回路设有向图G=<V,E>，考虑G中一条边的序列（vi1,vi2,…,vik）,称这种边的序列为图的通路。

Vi1、vik分别为起点、终点。通路中边的条数称为通路的长度。若通路的起点和终点相同，则称为回路。2021/5/934简单通路、基本通路简单通路：通路中没有重复的边。基本通路：通路中没有重复的点。简单回路和基本回路。基本通路一定是简单通路，但反之简单通路不一定是基本通路。基本回路必是简单回路。2021/5/935定理：一个有向（n,m）图中任何基本通路长度≤n-1。任何基本回路的长度≤n。任一通路中如果删去所有回路，必得基本通路。任一回路中如删去其中间的所有回路，必得基本回路。2021/5/936可达性的定义定义可达性：从一个有向图的结点vi到另一个结点vj间，如果存在一条通路，则称vi到vj是可达的。同样，可以将可达性的概念推广到无向图。利用通路、回路的概念，可研究计算机科学中的许多问题。2021/5/937连通性定义：无向图，若它的任何两结点间均是可达的，则称图G是连通图；否则为非连通图。定义：有向图，如果忽略图的方向后得到的无向图是连通的，则称此有向图为连通图。否则为非连通图。2021/5/938有向连通图定义：设G为有向连通图，强连通：G中任何两点都是可达的。单向连通：G中任何两结点间，至少存在一个方向是可达的。弱连通：忽略边的方向后得到的无向图是连通的。2021/5/939连通分支无向图中的连通性是等价关系。按照等价关系，可将图G中的结点进行分类，一个连通的子图即是一个等价类，称为G的一个连通分支。P（G）表示连通分支的个数。连通图的连通分支只有一个。2021/5/940练习题---图的连通性问题1.若图G是不连通的，则补图是连通的。提示：直接证法。根据图的不连通，假设至少有两个连通分支；任取G中两点，证明这两点是可达的。2021/5/9412.设G是有n个结点的简单图，且

|E|>(n-1)(n-2)/2，则G是连通图。提示：反证法。设有两个连通分支，这两个分支至多是完全图。由此得到图中点与边之间的数量关系。2021/5/942§8.3欧拉图欧拉图产生的背景就是前面的七桥问题。定义：图G的回路，若它通过G中的每条边一次，这样的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。定义欧拉通路：通过图G中每条边一次的通路（非回路）称为欧拉通路。2021/5/943判断欧拉通路的定理定理：无向连通图G是欧拉图的充要条件是G的每个结点均具有偶次数。定理：无向连通图G中结点vi与vj存在欧拉通路的充要条件是vi与vj的次数均为奇数，而其他结点次数均为偶数。2021/5/944例子邮递员信件问题城市街道问题一笔画问题公交线路问题2021/5/945有向欧拉图的判定一个有向图G有欧拉通路当且仅当G是连通的，且除了两个结点外，其余结点的引入次数等于引出次数，且这两结点中，一个结点的入度比出度大1，另一个结点的入度比出度多1.一个有向图G是欧拉图当且仅当G是连通的，且所有结点的入度等于出度。2021/5/946§8.4哈密尔顿图与欧拉图类似的是哈密尔顿图，它起源于环游世界的问题。定义：若图G的一个回路通过G中每个点一次，这样的回路称为哈密尔顿回路，有这种回路的图称为哈密尔顿图。显然欧拉回路是简单回路，无重复边；哈密尔顿图是基本回路，无重复点。2021/5/947关于如何判断哈密尔顿通路与回路，至今尚未找到它的充要条件，只有一些充分条件和必要条件。2021/5/948H-图性质定理定理：设无向图G=<V,E>是哈密尔顿图，非空集V1是V的子集，则P（G-V1）≤|V1|。P（G-V1）是从G中删去V1（包括与V1中结点相关联的边）后所得的图的连通分支。利用这个定理有时可证明一个图不是哈密尔顿图。P（G-V1）>|V1|说明不是H-图。2021/5/949定理：设G=<V,E>是无向简单图，|V|≥3，如果G中每对结点次数之和大于等于|V|，则G必为哈密尔顿图。定理：设有向图，|V|≥2，若所有有向边均用无向边代替后，所得无向图中含生成子图Kn,则G存在哈密尔顿通路。推论：n阶有向完全图(n>2)为哈密尔顿图。2021/5/950判断H-图的一些充分或必要条件H-图一定是连通图，且每个结点次数≥2。若G是n阶图，则H-通路是长度为n-1的基本通路。若存在次数为1的结点，则G没有H-回路。欧拉图遍历边，哈密尔顿图遍历点。在H-图中，H-回路不一定是唯一的。2021/5/951§8.5图的矩阵表示用矩阵的理论和分析方法来研究图论，将图的一些问题转换为矩阵运算问题，更适合于计算机处理。图在计算机中就是以矩阵形式存贮和读取的。也可借助图的理论和方法研究矩阵中的问题。2021/5/952有向图的邻接矩阵定义邻接矩阵：设有向图G=<V,E>，设各点按一定次序排列，构造矩阵则称A为图G的邻接矩阵。2021/5/953零图的邻接矩阵：A为零矩阵。完全图的邻接矩阵：A除对角线元素为0外，其余元素全为1。无向图的邻接矩阵：将无向边用两条方向相反的有向边代替，将无向图转成有向图。无向图的邻接矩阵是对称阵。邻接矩阵的概念还可推广到多重图和带权图，考虑如何表示。2021/5/954一个图的邻接矩阵完整的刻画了图中结点间的邻接关系，但当结点次序发生变化时，对应的邻接矩阵也随之变化。一般将V强行排序，图与邻接矩阵就一一对应了。同构的两个图，对应结点间的邻接关系相同，则它们的邻接矩阵或者相同或者其中一个通过行、列交换可得到另一个。2021/5/955例子2021/5/956有向图的邻接矩阵和次数设A为有向图G=<V,E>的邻接矩阵，|V|=n，有2021/5/957无向图的邻接矩阵和次数设A为无向图G=<V,E>的邻接矩阵，则A=AT。有2021/5/958An=A·A···A的元素的意义n=1时，aij=1表示存在一条边（vi,vj）或者从vi到vj存在一条长度为1的通路。若vi与vj是同一个点，则表示回路。当n=2时，记B=A2=(bij)，bij表示从vi到vj存在的长度为2的通路的条数。当n=k时，记C=Ak=(cij)，cij表示从vi到vj存在的长度为k的通路的条数。2021/5/959例子2021/5/960可达性矩阵记Rn=A+A2+···+An=(rij)n×n，由上一部分Ak的意义知，rij表示给出了从vi到vj的所有长度从1到n的通路的数目之和。一般我们并不关心两点之间有几条通路，通路的长度是多少等等。若rij=0，则表示从vi到vj是不可达的；若rij≠0，则vi到vj是可达的。考虑：为什么计算到An即可判断vi到vj是否可达？2021/5/961记称P为G的可达性矩阵或通路矩阵。一个图的可达矩阵给出了图中各结点间是否可达及图中是否有回路。2021/5/962例：求G=<V,E>的可达矩阵，V、E如下：

V={v1,v2,v3,v4}，E={(v1,v2),(v2,v3),(v2,v4),(v3,v2),(v3,v4),(v3,v1),(v4,v1)}。2021/5/963解：2021/5/964由于根据Rn计算可达矩阵较复杂，在以后的计算中引入布尔运算。例子：教材136页例8.11是否存在递归调用？2021/5/965多重图及有权图的矩阵表示举例说明。2021/5/966矩阵与无向图的连通性设G为无向图，由连通性定义知，任两个结点都是可达的。G连通当且仅当G的可达矩阵P除对角线外，所有元素均为1。2021/5/967矩阵与有向图的连通性设G为有向图，设P为G的可达矩阵。（1）G强连通当且仅当P除对角线外均为1。（2）G单向连通当且仅当P’=P+PT，P’除对角线外其余元素均为1。（3）G弱连通当且仅当A’=A+AT，P’是A’的可达矩阵，P’除对角线外其余元素均为1。2021/5/968第九章常用图本章介绍图论中几种常用图的基本原理和方法。树是图论中重要概念之一，它在计算机科学中如算法分析、数据结构等有广泛应用。平面图两步图2021/5/969§9.1树定义：树是不包含回路的连通图。在树中次数为1的结点称为叶，次数大于1的结点称为分支结点。例2021/5/970树的定理定理9.1：在（n,m）树中，必有m=n-1。证明：对n用归纳法。定理9.2：具有两个结点以上的树必至少有两片叶。证明：用反证法、直接法两种方法。定理9.3：图G是树的充要条件是G的每对结点间只有一条通路。2021/5/971树的等价定义设图T=<V,E>是（n,m）图，T是树。T连通无回路。T连通且m=n-1。T无回路，且m=n-1。T是最小连通图。T是最大无回路图。T的每对结点间恰有唯一一条通路。2021/5/972有向树定义：在有向图中若不考虑边的方向而构成树，则称为有向树。一般常用的有向树为外向树和内向树。2021/5/973外向树定义外向树：满足下列条件的有向树T称为外向树。（1）T有且仅有一个根。（引入次数为0）（2）T的其它结点的引入次数均为1.（3）T有叶。（引出次数为0，当然引入次数仍为1）定义：由外向树的根到结点vi的通路长度称为结点vi的级。2021/5/974外向树的相关概念两个结点如从根到结点的通路长度相等，则它们同级。否则不同级。可用外向树表示上面家属关系。例子：红楼梦人物简表。双亲，儿子，祖先，子孙，兄弟。从家属树中引入有序树的概念。兄弟间有一定的次序。2021/5/975定义内向树定义内向树：满足下列条件的有向树T称为内向树。（1）T有且仅有一个根。（引出次数为0）（2）T的其它结点的引出次数均为1.（3）T有叶。（引入次数为0，当然引出次数仍为1）内向树的概念和性质与外向树类似，故以后只考虑外向树。

2021/5/976m元树定义：设有n个结点的外向树T=<V,E>，若

vi的引出次数≤m，称T为m元树；若除了叶外，vi的引出次数=m，则称T为m元完全树。例：用二元树表示算术表达式。例：计算机中的程序流程图也可用有序二元树表示。2021/5/977二元树的真正作用在于：任一外向树均可用二元树表示。例子。2021/5/978生成树定义：设G=<V,E>是一连通图，T=<V’,E’>是G的一个子图，T是树，且V’=V，E’是E的子集，称T是G的生成树。由一连通图G寻找它的生成树过程如下：在G中寻找基本回路，找到后在此回路中删去一边，并继续寻找直至G中无基本回路为止。一般而言，G的生成树不是唯一的。2021/5/979求生成树若G=（n,m）图，得到的生成树为（n,m-1）图，故由G得到一个生成树，必须删去m-(n-1)=m-n+1条边，称之为G的基本回路的秩。练习：求一图的生成树。2021/5/980寻找一个图的生成树是很有实际价值的。一个连通图可以有多个生成树，寻找生成树使它的总长度最短的问题即为最短树问题。即求最小生成树问题。目前已有很多成熟的算法。2021/5/981§9.2平面图定义平面图：一个图不管它的图形的几何形状如何改变，它们的边之间总有交叉现象出现，则称此图为非平面图；否则称为平面图。或定义：设G=<V,E>是无向图，若存