资源描述
电子科技大学应用数学学院 张先迪,图论及其应用,1.1 图论简介,现实生活中许多问题都可归结为由点和线组成的图形的问题，例如，铁路交通图，公路交通图，市区交通图，自来水管网系统，甚至电路图在研究某些问题时也可简化为由点和线组成的图形，如：,图论就是研究这些由点和线组成的图形的问题,图论起源于18世纪，是一门较为年青的数学分支。但在历史上遗留了许多著名的图论问题，例如： 1.七桥问题 18世纪东普鲁士有一个城市称为个普尼斯堡，它位于普雷格尔河畔，河中有两个小岛，通过七座桥彼此相联（如图）。当时有人提出： 能否从某个地点出发经过每个桥一次且仅一次然后返回出发点？,A,B,C,D,Euler的解：,2. Hamilton 周游世界问题,1859年 Hamilton 提出这样一个问题：一个正十二面体有20个顶点，它们代表世界上20个重要城市。正十二面体的每个面均为五边形，若两个顶点之间有边相连，则表示相应的城市之间有航线相通。 Hamilton 提出 “能否从某城市出发经过每个城市一次且仅一次然后返回出发点？”,1840年数学家茂比乌斯（Mbius）提出一个猜想：任何平面地图，总可以把它的一个国家用四种颜色的一种着染，使相邻国家着不同色。这就是著名的四色猜想。如：,1890年希五德（Heawood）指出“4换为5”猜想成立。,1976年两位数学家在三台百万次的电子计算机上花了1200小时证明了猜想成立。猜想成为定理。,3. 四色问题,4. 中国邮路问题,1962年中国数学家管梅谷提出：一个邮递员从邮局出发递送邮件，要求对他所负责的辖区的每条街至少走一次，问如何选取路程最短 的路线？这个问题称为中国邮路问题。 该问题可用专门的算法来求解。,图论的应用范围很广，它不但能应用于自然科学，也能应用于社会科学。它非但广泛应用于电信网络、电力网络、运输能力开关理论、编码理论、控制论、反馈理论、随机过程、可靠性理论、化学化合物的辨认、计算机的程序设计、故障诊断、人工智能、印刷电路板的设计、图案识别、地图着色、情报检索，也应用于语言学、社会结构、经济学、运筹学、遗传学等。,图论作为一个数学分支，有一套完整的体系和广泛的内容，在这里我们只准备介绍图论的初步知识，其目的是今后在其它有关学科的学习和研究时，可以用图论的基本知识作为工具。,1.1 图和简单图,一图的定义,定义1 一个图 G 定义为一个有序对(V, E)，记为G = (V, E)，其中 （1）V是一个非空集合，称为顶点集或点集，其元素称为顶点或点； （2）E是由V中的点组成的无序点对构成的集合，称为边集，其元素称为边，且同一点对在 E 中可出现多次。,第一章 图的基本概念,符号说明: 图G 的顶点集也记为V(G), 边集也记为E(G)。图G 的顶点数（或阶数）和边数可分别用符号 n(G) (或 |V(G)| ) 和 m(G)表示。,例1 设 V =v1, v2, v3, v4，E =v1v2 , v1v2, v2v3 ，则 G = (V, E) 是一个4阶图。,若用小圆点代表点，连线代表边，则可将一个图用“图形”来表示, 如例1 中的图可表为,注: 也可记边 uv 为e ，即 e = uv。,e1,e4,e5,例2 设V = v1,v2,v3,v4，E = e1,e2,e3,e4,e5，其中 e1= v1v2， e2 = v2v3， e3 = v2v3， e4 = v3v4， e5 = v4v4 则 G = (V, E) 是一个图。,相关概念: (1) 若边e = uv , 此时称 u 和v 是 e 的端点; 并称 u 和 v 相邻，u (或v)与 e 相关联。若两条边有一个共同的端点，则称这两条边相邻。,（2）特殊点、边 孤立点：不与任何边相关联的点； 环：两端点重合的边； 重边：连接两个相同顶点的边的条数，叫做边的重数。重数大于1的边称为重边。,(4) 既没有环也没有重边的图称为简单图。其他所有的图都称为复合图。,例3,(3) 点集与边集均为有限集合的图称为有限图，本书只讨论有限图。只有一个顶点而无边的图称为平凡图。边集为空的图称为空图。,二图的同构,定义2 设有两个图G1 = (V1, E1)和G2 = (V2, E2)，若在其顶点集合之间存在双射，即存在一一对应的关系，使得边之间有如下的关系：设,，对应为：,例如,说明：(1) 两个同构的图均有相同的结构，没有本质上的差异, 差异只是顶点和边的名称不同。,（2）图同构的几个必要条件： 顶点数相同； 边数相同； 度数相等的顶点个数相同。,定义 设 v为 G 的顶点，G 中与 v 为端点的边的条数（环计算两次）称为点 v 的度数，简称为点v的度，记为 dG (v)，简记为 d(v)。,图中 d (v1) = 5 d (v2) = 4 d (v3) = 3 d (v4) = 0 d (v5) = 2,例,注：该图中各点的度数 之和等于14，恰好 是边数7的两倍,(3) 易证，图的同构关系是一个等价关系。该关系将所有的图的集合，划分为一些等价类，即相互同构的图作成同一个等价类。,（3）在图的图形表示中我们可以不给图的点和边标上符号，称这样的图为非标定（号）图，否则称为标定（号）图。非标定图实际上是代表一类相互同构的图。 不误解时我们也不严格区分标定图与非标定图。,（4）判定图的同构是很困难的，属于NP完全问题。对于规模不大的两个图，判定其是否同构，可以采用观察加推证的方法。,例 证明下面两图同构。,证明 作映射 f : vi ui (i=1,2.10)，易知该映射为双射。,容易验证 ，对vi v j E (a), 有 f (v i vj,) ui,uj, E(b) ，(1 i 10, 1 j 10 ),由图的同构定义知，图(a)与(b)是同构的。,例 判断下面两图是否同构。,解 两图不同构。,这是因若同构，则两图中唯一的与环关联的两个点u1 与v1 一定相对应，而u1的两个邻接点与v1的两个邻接点状况不同（ u1邻接有4度点，而v1 没有）。 所以，两图不同构。,三完全图 ，偶图 ，补图,完全图：任意两点均相邻的简单图称为完全图，在同构意义下，n 阶完全图只有一个，记为Kn。例如K2, K3, K4分别为如下图所示。,具有二分类（X, Y）的偶图（或二部图）：是指该图的点集可以分解为两个（非空）子集 X 和 Y ，使得每条边的一个端点在 X 中，另一个端点在Y 中。,。,完全偶图：是指具有二分类（X, Y）的简单偶图，其中 X的每个顶点与 Y 的每个顶点相连，若 |X|=m，|Y|=n，则这样的偶图记为 Km,n,例,K 3,3,K1,3,四个图均为偶图;,K1,3 , K3,3为完全偶图,例,偶图,不是偶图,简单图G 的补图: 设 G =（V, E），则图 H =（V，E1E）称为G 的补图，记为 , 其中集合,例如, 下图中的(a)，(b)两图是互补的。,定理1 若n 阶图G是自补的（即 ），则 n = 0, 1（mod 4）,证明 因为G是自补的，则G和其补图有同样多的边数，且边数,从而,又因G 的边数 m(G)是整数，故 n(n-1)/4 为整数，即只能有n0（mod 4）, 或 (n-1) 0 （mod 4）。,对任意的有m条边的图 G = (V, E)。有,证明 因图 G 的任一条边均有两个端点 (可以相同)，在计算度时恰被计算两次 (每个端点各被计算了一次)，所以各点的度数之和恰好为边数的两倍，即 (1.1) 式成立。,定理2 （握手定理）：,注：该定理也称为图论第一定理，是由欧拉提出的。欧拉一身发表论文886篇，著作90部。,奇(偶)点: 奇(偶)数度的顶点,相关术语和记号,图G的顶点的最小度,图G的顶点的最大度,k-正则图: 每个点的度均为 k 的简单图,例如,完全图和完全偶图Kn,n均是正则图。,推论1 任意图中，奇点的个数为偶数。,证明 任给图G = (V, E)，设G 有m 条边，令,V1= v | v V ,d(v) 为奇数 , V2= v | v V ,d(v) 为偶数 ,显然，V1 V2= V,V1V2= 。由握手定理,例7 证明在任意一次集会中和奇数个人握手的人的个数为偶数个。,证明: 将集会中的人作为点，若两个人握手则对应的点联线，则得简单图G。这样G 中点v的度对应于集会中与v握手的人的个数。于是，问题转化为证明“图G 中度数为奇的点的个数为偶数”，这正是推论1的结论。,推论2 正则图的阶数和度数不同时为奇数。,证明 设G是k-正则图，若k为奇数，则由推论1知正则图G的点数必为偶数。,度序列: 一个图G的各个点的度d1, d2, dn构成的非负整数 组 (d1, d2, dn)称为G的度序列 。它是刻画图的特 征的重要“拓扑不变量”。,正整数k的划分: 是指将k表示为若干正整数的和,或指一 个无序正整数组，组中正整数的和是k。,图划分: 正整数k的一个划分(d1, d2, dn)能成为某简 单图的度序列的k的划分.,显然，若正整数 k 有图划分，则k 必须是偶数,例 偶数4有五种划分： 4，3+1，2+2，1+1+2，1+1+1+1 但属于图划分的却只有两种:,例 试判断下列非负整数组 是否可图?,解 利用定理5可得下列非负整数组,所以 也是可图的:,关于图序列，主要研究的3个问题：（1）存在问题（什么样的整数组是图序列？）已解决；(2) 计数问题（一个图序列对应多少不同构的图？）解决得不好；(3) 构造问题（如何画出图序列对应的所有不同构图？）没有解决。,1.2 子图与图的运算,一. 子图,定义1 设G 和H为两个图，若V(H) V(G) , E(H) E(G) ,且H中边的重数不超过G中对应边的重数，则称H 是G 的子图. 记为H G 。有时又称G是H的母图。,当H G ，但H G时，则记为H G ，且称H为G的真子图。G的生成子图是指满足V(H) = V(G)的子图H。,例如,上图中，H1与H2均为G 的子图，其中H2 是G 的生成子图，而H1 则不是。,导出子图 设V是V的一个非空子集。以V为顶点集，以两端点均在V中的边的全体为边集所组成的子图，称为G的由V导出的子图，记为GV；简称为G的导出子图，,导出子图GVV记为 G -V ；它是G中删除V中的顶点以及与这些顶点相关联的边所得到的子图。若 V=v, 则把G-v简记为Gv。,边导出子图 假设E是E的非空子集。以E为边集，以E中边的端点全体为顶点集所组成的子图称为G的由E导出的子图，记为GE ；简称为G的边导出子图，边集为 E E 的G 的导出子图简记为 GE 。若E =e ，则用Ge来代替 G-e。,定理8 简单图G 中所有不同的生成子图（包括G和空图）的个数是2m个, 其中m为G 的边数。,证明 易知,其个数 = 含0条边的+含1条边的+含m条边的,二. 图的运算,设G1，G2是G 的子图, 有下列术语与概念,G1和G2不相交: 指它们无公共顶点.,G1和G2边不重 : 指它们无公共边.,并图G1G2 ：是指其顶点集为V(G1)V(G2)，边集为E(G1)E(G2) 的G 的一个子图 ；如果G1和G2是不相交的，有时就记其并图为G1+G2。,交图G1G2 ：类似地定义,例,例,定义2 在不相交的G1和G2的并图G1+G2中，把G1的每个顶点和G2的每个顶点连接起来所得到的图称为G1和G2的联图，记为G1G2。,例,有： K1K4=K5，K2K3=K5 K6= K1K5 = K2K4 = K3K3。,定义3 设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1V2中的任意两个点u = (u1,u2)和v = (v1,v2)，当(u1 = v1和 u2 adj v2) 或 (u2 = v2 和 u1 adj v1) 时就把 u 和 v 连接起来所得到的图G称为G1和G2积图，记为G = G1G2。其中 ui adj vi 表 ui 和vi邻接，如下图所示。,n-方体Qn ：递推地定义为，Q1= K2，Qn= K2Qn-1 。,注： Qn有2n个点，它的点可以用a1 a2an来标定，其中ai是0或者1。如果Qn的两个点的二进制表示式中只有一处不同，则它们邻接。,1.3 路和连通性,定义 给定图G = (V, E)，w = v0e1v1e2ekvk 是G 中点边交替组成的序列，其中 viV，eiE，若w满足 ei 的端点为 vi-1 与 vi，i = 0,1, k，则称w为一条从起点 v0 到终点 vk 的长为 k 的途径（或通道或通路), 简称（v0, vk）途径。,边不重复的途径称为迹 ；任意两点都不同的途径称为路。显然路必为迹。,闭途径:起点和终点相同的长为正的途径。 闭迹也称为回路。,1. 途径、迹、路、圈、距离和直径,圈: 起点和内部顶点（非起点和终点的点）两两不相同 的闭迹。,k（奇，偶）圈：长为k （奇，偶）的圈。 3圈常称为三角形。,易知，图中若两个不同点u与 v 间存在途径（通路），则 u 与 v 间必存在路；若过点u存在回路，则过点u 必存在圈 。,点u与v的距离：指图中最短 (u, v) 途径的长度，记为 d(u, v)。,图G的直径定义为 d(G) = max d(u, v) | u, vV,例1 在下图G 中，取 w1 = v1v2v3 ，w2 = v1v2v3v4v2 ，w3 = v1v2v3v2v3v4 ( 注：简单图可只用点序列表通路）,则 w1, w2, w3 依次为长 为2,4,5的途径 ；,由定义1可看出,G中 v1 v2v5v1为长为3的圈，v1v2 v3 v4v2 v5v1 为长为 6 的回路。,w1与w2为迹 ，w1为路。,d(G) =2,2. 图的连通性,点u与v连通 ：指图存在（u, v）路。规定u和u是连通的。,连通图: G中任意两个顶点均连通的图。,非连通图：不是连通图的图。,连通图,非 连 通 图,连通分支（分支，支）：若H是图G 的连通子图且H不能再扩充为G的任一连通子图，则称H为G的连通分支。用(G) 记图G 的连通分支数。,有：(D) =3， (G) =1,3. 有关定理,定理7 若图G是不连通的，则 是连通图。,证明 因G是不连通, 故G中至少两个分支.,设u，v是G的任意两个顶点。若u和v在G中不邻接，则在 中它们邻接。,若u和v在G中邻接，则它们属于G的同一分支。在另一个分支中取一点w，则在 中u和v均与w邻接，从而uwv是一条通道, 故在 中它们邻接。,定理8 一个图是偶图当且当它不包含奇圈。,证明 设G是具有二分类（X, Y）的偶图，并且C = v0 v1 vk v0是G的一个圈。不失一般性，可假定v0 X 。这样， v2i X ，且v2i +1Y 。又因为v0 X ，所以vk Y 。由此即得C是偶圈。,显然仅对连通图证明其逆命题就够了。设G是不包含奇圈的连通图。任选一个顶点u且定义V的一个分类（X, Y）如下：,X = x | d (u, x) 是偶数，xV(G) Y = y | d (u, y) 是奇数，yV(G),现在证明（X, Y）是G的一个二分类。,假设v和w是X的两个顶点，P是最短的（u, v）路，Q是最短的（u, w）路，以u1记P和Q的最后一个公共顶点。因P和Q是最短路，P和Q二者的（u1, u）节也是最短的路，故长相同。现因P和Q的长都是偶数，所以P的（u1, v）节P1和Q的（u1, w）节Q1必有相同的奇偶性。由此推出路（v, w）长为偶数。若v和w相连，则 就是一个奇圈，与假设矛盾，故X中任意两个顶点均不相邻。,类似地，Y中任意两个顶点也不相邻。所以（X, Y）是G的一个二分类。,1.4 最短路及其算法,一. 赋权图,定义 若图G的每一条边e 都附有一个实数w(e)，则G连同它边上的权称为赋权图。实数w(e) 称为e的权。子图H的各边权之和称为子图H 的权，记为W(H)。,例 右图G 为赋权图,其中w(v1v2) = 1，w(v1v3) = 5，W(G) = 20,设是权图G 中的一条路，称 的各边权之和为路的长。赋权图中点 u 到 v 的距离仍定义为点 u 到 v 的最短路的长，仍记为 d(u,v)。,例2 右图中， d(v2, v4) = 5 相应的最短路为 ：v2v1 v3v4,易知，各边的权均为1的权图中的路长与非权图中的路长是一致的。,二. 最短路问题,问题：给定简单权图G = (V, E)，并设G 有n个顶点，求G中点u0到其它各点的距离。,Dijkstra算法 (Edmonds, 1965),(2) 若i = n-1，则停；否则令 = V Si ,对每个v ，令 l(v) = min l(v)，l(ui) + w(uiv),(1) 置 l(u0) = 0；对所有vV u0，令 l(v) = ； S0 = u0，i = 0。,并用 ui+1记达到最小值的某点。置S i+1= Siu i+1，i = i+1（表示赋值语句，以后的算法中相同），转（2）。,终止后，u0 到 v 的距离由 l(v) 的终值给出。,说明：,（1） 算法中w(uiv) 表示边 uiv 的权；,（2） 若只想确定u0到某顶点v0的距离， 则当某 uj 等于 v0 时即停；,（3） 算法稍加改进可同时得出u0到其它点的最短路。,例3 求图 G 中 u0 到其它点的距离。,u0,7,4,2,1,5,5,8,1,3,G :,解,（b）用与u0关联的边的权2,4,7分别更新与u0相邻的三个点的标号;,（c）取小圆点中标号 最小者得 u1；,（d）对与u1相邻的小圆点， 用 l (u1) + w (u1v) = 2+1 = 3 更新标号4； 2+5=7 更新两个；,（e）取小圆点中标号 最小者得 u2。,三. 算法分析,好算法 一个图论算法如果在任何一个具有m条边的n阶图G上施行这个算法所需要的计算步数都可由n和m的一个多项式（例如3n2m）为其上界, 则称该算法是好的.,例 某两人有一只8升的酒壶装满了酒，还有两只空壶，分别为5升和3升。现要将酒平分，求最少的操作次数。,解 设x1,x2,x3分别表示8,5,3升酒壶中的酒量。则,容易算出(x1,x2,x3) 的组合形式共24种。,每种组合用一个点表示，若点u能通过倒酒的方式变换为v,则 u向v 连有向边，并将各边赋权1，得一个有向权图。,于是问题转化为在该图中求 (8,0,0)到(4,4,0)的一条最短路(求最短路的算法在有向图中仍适用)。结果如下：,1.5 图的代数表示及特征,一. 邻接矩阵,定义：设 n 阶标定图G = (V,E)，V = v1,v2, vn，则 G 的邻接矩阵是一个nn 矩阵A(G) = aij (简记为A)，其中若 vi邻接vj，则aij =1;否则aij =0。,注: 若aij 取为连接vi与vj 的边的数目, 则称A为推广的邻接矩阵,说明: (1) 邻接矩阵是一个对称方阵。,(2) 简单标定图的邻接矩阵的各行 (列) 元素之和是该行 (列) 对应的点的度。,（3）若A1和A2是对应于同一个G的两种不同的标定的邻接矩阵，则 A1和A2 是相似的。即存在一个可逆矩阵P有,（4）G是连通的当且仅当没有G的点的一种标定法使 它的邻接矩阵有约化的形式,图中 v1到 v1 的长为2的的通道的数目为1 v1到 v2 的长为2的的通道的数目为0 v1到 v3 的长为2的的通道的数目为2 v1到 v4的长为2的的通道的数目为0,v2到 v2 的长为2的的通道的数目为5,定理10 令G是一个有推广邻接矩阵A的 p阶标定图，则 An的i 行j 列元素 等于由vi到vj的长度为n的通道的数目。,证明 n = 0时，A0 = In (n阶单位矩阵)，从任一点到自身有一条长度为零的通道，任何不同的两点间没有长度为零的通道，从而命题对n = 0时成立。,由于aik是联结vi和vk的长度为1的通道的数目，akj(n)是联结vk和vj的长度为n的通道的数目，所以 aikakj(n) 表示由vi经过vk到vj的长度为n+1的通道数目。,于是对所有的k求和即（*）式右边表示了由 vi 到 vj 的长度为n+1的通道数目。也即 aij(n+1) 为由 vi 到 vj 的长度为n+1的通道数目。 这表明命题对n+1成立。,推论 设A为简单图G的邻接矩阵，则 （1）A2 的元素 aii(2) 是 vi 的度数。A3 的元素 aii(3) 是含 vi 的三角形的数目的两倍。,（2） 若G是连通的，对于ij，vi 与vj 之间的距离是使An 的 aij(n) 0 的最小整数n。,二. 关联矩阵,定义1 无环图G的关联矩阵B(G) = bij (简记为B)是一个 nm 矩阵，当点vi 与边ej 关联时 bij =1，否则 bij =0。,说明：定义中“无环”的条件可去掉，此时bij =点vi 与边ej 关联的次数（0, 1, 2(环).,性质：关联矩阵的每列和为2；其行和为对应顶点的度数.,例如：,三、邻接代数,给定图G , 容易验证G 的邻接矩阵的全体复系数多项式在通常的矩阵运算下构成一个有限维的线性空间，它也是一个代数，称为图G的邻接代数，记为(G)。,用图G的点数和直径可以给出邻接代数(G)的维数的界。,定理11 n阶连通图G的邻接代数的维数有 d(G)dim(G)n,回忆线性代数的一些概念。设A = (aij) 是一个n 阶方阵，其中 aijC（复数集合）。A的行（列）组成的n维向量称为A的行（列）向量。称为方阵A的特征值，如果存在数域C 中一个非零列向量X，使得 AX=X （1） 则X 称为A的属于的一个特征向量。,实际上是方程 |In-A | = 0 （2）的根，其中In为n阶单位矩阵。,若方程（2）有s 个相异的根1,2,s,其重数依次记为m1, m2, ms（有 m1+m2+ms = n），称,例1 设A 为4圈C4 的邻接矩阵，求A的谱。,解 C4的邻接矩阵,定理13 设G为n 阶连通图，则邻接矩阵A(G)的不同特征值数目s 满足不等式 d(G)+1 s n,证明 右边的不等式显然成立。,所以A 的特征值为 - 2 , 0, 2 ; 其重数依次记为1,2,1。故,Spec A =,对于左边的不等式，因A(G) 是对称的，故不同的特征值的数目s 等于最小多项式的次数，即等于邻接代数的(G)的维数，于是所要的不等式由定理11得到。,证明 因A(G)的各特征值的平方组成矩阵A(G) 2的特征值组，即i2 是A(G) 2 的特征值且重数相同，故由代数理论知 等于A(G) 2的迹（A(G) 2的对角线元素的和）。,故,证明 设A(G)的n 个特征值为1, 2, n。不妨设=n。对向量 (1,1,1) 和 (1, 2, n-1) 应用许瓦兹（Schwarz）不等式，得,（5.1）,定理15 设是A(G)的任一特征值，则,如4圈 的谱: 有(-2)2+22=8,因邻接矩阵A(G)的对角元全为零, 故,于是,又由定理14知,故,这样（5.1）式变成 (-)2(n-1)(2m-2) 即 n22m(n-1),故,例 C4中, n=4, m=4, 故,（5.1）,1.6 极图,定义1 若简单图G的点集V有一个划分,V= ，ViVj = ij,且所有Vi非空， Vi内的点均不相邻，则称G是一个l 部图。,说明: (1) 如果l=2，则G就是偶图；,(2) 任何一个n阶图必是一个n部图；,(3) 若l1l2n，易知任意的 l1部图也是l2部图。,定义2 如果在一个l 部图G中，|Vi|=ni，任何两点 uVi ,v Vj , ij , i,j =1,2, l 均邻接，则称G为完全l 部图。记作,注: 它有 个点和 条边。,定义3 如果在一个n个点的完全l 部图G中， n = kl + r 0rl |V1| = |V2| = = |Vr| = k + 1; |Vr+1| = |Vr+2 | = = |Vl | = k 则称 G 为n 阶完全 l 几乎等部图，记为Tl ,n。 |V1| = |V2| = = |Vl | 的完全 l 几乎等部图称为完全l 等部图。,1. 这是一个连通的3部图, 点集 V 的划分为: V1= v4， V2 = v3 ,v5，V3 =v1 ,v2 ,v6 ,2. V 的划分也可为 V1= v1,v5，V2 = v2 ,v3，V3 = v4 ,v6 ,3. 这也是一个2部图, 点集 的划分为: V1= v4 ,v2 ,v6 ， V2 = v1,v3 ,v5,且划分唯一,定理16 连通偶图的2部划分是唯一的。,证明 设连通偶图G 的2部划分为V1V2 =V 。取vV1 ，由于G 连通，对任何 uV1V2 ，G 中有联结 u 和 v 的路，故d (v, u)有定义。因为任何一条以v为起点的路交替地经过V1和V2 的点，可知一个点uV2 当且仅当d (v, u)是奇数。这准则唯一地决定了G的2部划分。,定理17 n阶完全偶图 的边数 m = n1n2 ，且有,证明 m = n1n2 是显然的。,又 m = n1n2 = n1(n-n1) = n1n - n12,= n2 /4 - (n1-n/2)2 （配方）, n2 /4,考虑到 m 是正整数，故,定理18 n阶l 部图G有最多边数的充要条件是 GTl,n。,证明 由代数学知，l个正整数n1 ,n2 ,nl 的函数 ，在约束条件 下达到极大值的充要条件是对任何1i jl，有 |ni-nj| 1.,故若取nj = k (j = r+1,r+2,l)，而 ni = k +1 ( i= 1,2,r) 使得|V1| = |V2| = = |Vr| = ni= k + 1，|Vr+1| = |Vr+2 | = = |Vr| = nl = k，此时n阶l部图G的边数必极大，而这时的GTl,n。,下面的定理是Turan（1941）提出的一个著名的定理。它确定了有n个顶点而不包含Km+1为其子图的简单图所能具有的最大边数。,定理20 （Turn）若 G 是简单图，并且不包含 Kl+1，则边数 m(G)m(Tl,n)。此外，仅当 G Tl,n 时有 m(G) = m(Tl,n)。,问题：一个小组n个人在一个平原地区执行一项排雷任务。其中任意的两个人，若其距离不超过g米，则可用无线电保持联系；若发生触雷意外，地雷的杀伤半径为h米。问：在任意的两个人之间均能保持联系的条件下，若发生意外，平均伤亡人数最低的可能值为多少？,Turn定理的一个应用,对此问题，按问题的条件若某人A触雷，则与A的距离大于h米的人将是安全的，但究竟哪个人会发生触雷意外，事先是不知道的，所以此问题实际上是求在任意的两个人之间的距离不超过g米的条件下，距离大于等于h米的人数对最多能达到多少对。为建立此问题的数学模型，先引入平面点集的直径这一概念。,有限平面点集A的直径: 指A中点对的距离的最大值, 其中距离是指欧氏距离。,先前的问题可转化为计算在直径为 g 的点集 x1, x2, xn中最多有多少点对，其距离大于h。下面我们对 g =1，h = 展开讨论。,先观察n = 6时平面点集的分布的两种特殊情况。一种情况为六个点x1, x2, x3, x4, x5和x6位于一个正六边形的顶点上，并使点对（x1, x4），（x2, x5）和（x3, x6）的距离为1，如图1。,容易计算该点集的直径为1，线段x1 A的长 ，Ax5的长为3/4（x1A, Ax5如图所示），从而可计算出x1与x5的距离为 。同理，点对（x1, x3）,（x2, x4）,（x2, x6）,（x3, x5）,（x4, x6）均为 。因 。所以此种情况距离大于 的点对有9对。,下面的定理回答了12已是最大数目。该定理的证明用到Turn定理。,另一种情况如图2所示。其中x1, x2和x3处于一个边长为1的正三角形的顶点上；x4, x5和 x6也位于一个正三角形的顶点上。由于线段x2 A的长为1/2，可使线段x5 B的长大于 。这是可以实现的。这样, 除点对（x1, x4）,（x2, x5）,（x3, x6）外，其余十二个点对的距离均大于 。,定理21 设A=x1, x2, xn为任意一个直径为1的平面点集，则A中距离大于 的点对的最大数目为 。并且对每个n，存在直径为1的点集A* = x1, x2, xn，它恰有 个点对，其距离大于 。,由定理21，n=6 时， 。所以图2的12是最大数目。,第二章 树,定义1 (1) 无圈连通图称为树, 树常用字母T 表示； (2) 树中，度数为1的顶点称为树叶，度数大于1 的顶点称为分支点； (3) 无圈图称为森林，树也是森林；,2.1 树的概念与性质,由定义, 平凡图也是树, 称为平凡树。,树,树,不是树,不是树，是森林,例,定理1 设G是具有n个点m条边的图，则以下关于树的命题等价。,（1）G 是树。,（2）G 中任意两个不同点之间存在唯一的路。,（3）G 连通，删去任一边便不连通。,（4）G 连通，且 n = m+1。,（5）G 无圈，且 n= m+1。,（6）G 无圈，添加任一条边可得唯一的圈。,因G是树，树是连通的，故G中任意两个不同点之间存在路。下证唯一性。,若不然，设点 u 与 v 之间存在两条不同的路1与2。从 u 出发沿1搜索，设x是具有第一个如下性质的点：它在2上，但它的下一个点 w 不在2上；继续搜索，设y是w之后的第一个既在1上又在2上的点。这样1上从 x 到 y 段与2上从 y 到 x 段便构成一个圈，这与G是树无圈矛盾，所以任意两点间的路唯一。,只需证 n= m+1即可。对 n 用归纳法。,当n = 1时，G无边，满足n = m+1。,设对少于n个点的图（4）的结论成立。,对于有n个点的图G，由（3）的假设知删去G中某边可得 两个具有同样性质的子图G1与G2。设Gi 的点数与边数分别为 ni 与mi（i =1,2）。显然n1 n，n2 n。由归纳假设有,相加得 n1+n2= m1+ m2+2 （*）,n1= m1+1，n2= m2+1,同时有 n1+n2= n， m1+ m2= m-1,代入（*）式得：n = m+1。,推论1 由k棵树组成的森林满足：m = n-k。其中n为G的顶点数，m为G的边数。,证明 设森林中每棵树的顶点数与边数分别是 ni 和 mi (i =1,2,k)。则由定理1， mi = ni-1 , i =1, 2, k,因此,即 m = n-k,推论2 一棵阶数大于或等于2的树至少有两片树叶。,证明 设非平凡树T 有x 片树叶，n个点, m条边。因为T 连通非平凡，故T 的其余 n-x 个点的度至少为2。,由1.1定理2和2.1定理1有： x +2(n-x) 度数之和 = 2m = 2(n -1),定义2 设图G是一个非平凡的无向连通图，如果对G中每一条边e, G-e都不连通，则称G是一个最小连通图。,定理2 非平凡的无向图G是树的充要条件是G为最小连通图。,证明 这是定理1和定义2的直接结果。,例 设树T 有ni 个度为i 的点，2ik（k1),其余点均为 叶，求T 中叶点的数目。,解 设 T 有x 片树叶，则T的点数为：,又由握手定理得：,解得 x 为:,故T的边数为:,x+n2+n3+nk,x+n2+n3+nk-1,x+2n2+3n3+ knk = 2(x+n2+n3+nk-1),x,2.2树的中心和形心,定义1 设 G = (V, E) 是一连通图， vV，令 e(v) = max d(u,v) | uV 则称 e(v)为顶点 v 的离心率；又令 r(G) = min e(v) | vV 称 r(G) 为图 G 的半径。,比较图的直径与离心率的定义可知，图G 的直径是G 的最大离心率；e(v) = r(G) 的点 v ，称为 G 的一个中心点， G 中全体中心点的集合称为G 的中心。,例1 在下图所示的树中，图中每个顶点处标出的数字为该点的离心率，图中的顶点u为该树的中心，该树的半径 r(G) = 4，直径d(G) = 8。在该图中，树的中心是点u。,定理5 每棵树有一个由一个点或两个邻接的点组成的中心。,证明 结论对于树 K1 , K2 是成立的。我们证明任何一个其它的树T，与除去T的所有度为1的顶点(即T的叶点)得到的树T1有同样的中心。,显然，由T的一个给定的顶点u到T的任何一个其它点v的距离仅当v是一叶点时，才可能达到最大值。于是,故树T与树T1有相同的中心。,重复这种除去端点的过程，我们相继得到一系列与T具有相同中心的树，因为T有限，故经过有限步后，我们最终得到的树是K1或K2，且K1,K2的中心即为T的中心。从而T的中心正好由一个顶点或两个相邻顶点组成。,定义2 设T是树，u是树T的任意一个顶点，树T在点u处的一个分枝是指包含u作为一个叶点的极大子树，其分枝数为该顶点的度数；树T在点u的分枝中边的最大数目称为点u的权；树T中权值最小的点称为它的一个形心点，全体形心点的集合称为树T的形心。,例 在图2-3的树中，每个顶点处的数字表示该顶点的权值，权值为4的顶点为该树的形心。,定理6 每一棵树有一个由一个点或两个邻接的点组成的形心。(证明留作习题 ),定义1 若图 G 的生成子图T是树，则称T为G 的生成树；若T为森林，称它是G的生成森林。生成树的边称为树枝，G 中非生成树的边称为弦。,2.3生成树,定理5 连通图的生成树必存在。,证明 给定连通图G，若G 无圈，则G就是自己的生成树。若G有圈，则任取G中一个圈C，记删去C中一条边后所得之图为H1。显然在H1中，圈C 已不存在，但仍连通。,定理4的证明方法也是求生成树的一种方法，称为“破圈法”。,若H1中还有圈，重复以上过程，直至得到一个无圈的连通图H。H 便是 G 的生成树。,解 这是一个求图G 的生成树的问题。 因G 有5个点，由定理1的（4）知G 的生成树有4条边，即至少需4条光纤不出故障，通信才不会中断，且这些不出故障的光纤应按上图中的H 进行分布，其中H是由破圈法求得的G的一个生成树。（注：H 不唯一）,例1 设有五个城市 v1, v2, v3, v4, v5。它们之间有通信光纤连通，其布置如图中的G。问至少有几条光纤不出故障，城市间的通信才不会中断，且这些不出故障的光纤应如何分布？,推论 若G 是连通的 (n,m) 图，则 mn -1 。,证明 设 G 是连通图，由定理5，包含一棵生成树T ，所以，,G 的边 e 称为被收缩，是指删去边e并使它的两个端点重合, 如此得到的图记为 G e 。,有下列关系: 若 e 是 G 的一条边，则有,若 T 是树，则 T e 也是树。,凯莱(Cayley 18211895): 剑桥大学数学教授，著名代数学家，发表论文数仅次于 Erdos ,Euler, Cauchy. 著名成果是1854年定义了抽象群，并且得到著名定理：任意一个群都和一个变换群同构。同时，他也是一名出色的律师，作律师14年期间，发表200多篇数学论文，著名定理也是在该期间发表的。 凯莱生成树递推计数公式是他在1889年建立的。,证明 由于G的每一棵不包含e 的生成树也是 G-e 的生成树。由此推知 ，(G-e) 就是G 的不包含 e 的生成树的棵数。,类似, (Ge) 就是G 的包含 e 的生成树的棵数。从而知结论成立。,解 (G)的部分递推计算过程如下（其中 已被省略）：,所以 (G) = 4 +4 = 8,定理7 (Kn) = nn-2。,注 以上讨论的生成树的棵数均指标定图而言。标定图的生成树的数量远大于非标定图生成树的数量。如标定图K6有66-2 = 1296 棵生成树，而不同构的6阶树仅6棵。,按直径从2到5依次是：,定义2 设T 是图G = (V, E) 的一棵生成树，m 和 n 分别是 G 的边数与顶点数，e1, e2 , em-n+1 为 T 的弦，设 Cr 是T 加 er 产生的圈，r = 1, 2 , m-n+1, 称 Cr 为对应于弦 er 的基本回路，C1,C2 ,Cm-n+1称为对应于生成树T 的基本回路系统。,例1 在下图中，（a）为一无向图，(b)为(a)的一棵生成树，(c)与(d)分别是对应于弦e6与e3的基本回路。,定理8 连通图G的任一回路均可表示成若干个基本回路的对称差。,例 假定有四个城市，准备修筑铁路将这四个城市连接起来，已知各城市间修铁路的造价预算如下图所示，图中边上的数值表示预算的造价（以亿元为单位），问如何选择线路以使总造价最小。,2.4最小生成树,分析：设求出的线路为H，因要保证将四个城市连接起来，故H 应是图中的连通生成子图。同时，因要保证造价最小，故H中应无圈（因若有圈，则删去圈中某边还能保证连通性，但造价被减少）。所以H 应是图中的生成树，并且还应是该图中所有生成树中边权之和最小的一个。,定义3 在连通赋权图G中，边权之和最小的生成树称为G 的最小生成树 。,给定无环连通赋权图G，设G 有 n 个点，m 条边，下面给出求 G 的最小生成树的一个算法。,克鲁斯克尔算法,（1） 将G 的边按权从小到大排列，不妨设为 e1, e2，em,( 2 ) 取T = e1，再从e2开始依次将排好序的边加入到T 中，使加入后由T 导出的子图（即由T 作为边集，T 中的边相关联的点作为点集所确定的子图）不含圈，直至T 中含有n-1条边。,定理11 由克鲁斯克尔算法构作的任何生成树 都是 G 的最小生成树。这里n为赋权图G 的顶点数。,证明 用反证法。对 G 的任何异于 T* 的生成树 T ，对e1, e2，en-1，用 f(T) 记使 ei 不在 T 中的第1个 i 值。现在假设 T*不是最小树， T 是一棵使 f(T) 尽可能大的最小树。,假设 f(T) =k。这表明 e1, e2，ek-1 同时在 T 和T*中，但ek不在T 中。则 T +ek 包含唯一的圈C。设ek 是 C 的一条边，它在 T 中而不在中T* 。于是ek 不是T +ek的割边。因此T =(T +ek)-ek 是具有n-1条边的连通图，所以，它是G 的另一棵生成树。显然，,（4.1）,在克鲁斯克尔算法中选出的边ek，是使 为无圈图的权最小的边。由于 是 G 的子图，它也是无圈的。于是得到：,（4.2）,结合（4.1）与（4.2）式，有,解 边权排序为1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6。 对应的边为 v1v2，v4v6，v2v7，v1v7，v2v4，v1v6，v2v3，v6v7，v4v5，v4v7，v5v6，v3v4,依据算法，其中画有下横线的边为依次被选为生成 树T 的边,且 W(T) = 1+1+2+3+4+5 = 16,2,第2章 完,
展开阅读全文