图论第一章课后习题解答

《图论及其应用》习题课教材杨春编电子科技大学应用数学学院内容提要本书主要对张先迪等编的研究生《图论及其应用》教材的习题进行解答。该书可作为研究生图论教学的参考教材。前言现实生活中，许多问题都可归结为一个由点和线组成的图形的问题。例如，由点代表车站，线代表铁路线的铁路网络图；点代表路口，线代表街道的城市交通图；点代表管道接头，线代表管道的自来水供水系统；点代表电路的结点，线代表结点间的电气元件的电网络图；点代表网络的结点，线代表通讯线的通讯网络、计算机网络等等。图论正是研究这些由点和线组成的“图形”问题的一门学科。图论起源于18世纪，其第一篇论文是由欧拉（Euler，1707—1782）于1736年所完成。这篇论文解决了一个当时还没有解决的著名问题—哥尼斯堡（Königsberg）七桥问题（见第四章）。这篇论文也使欧拉成为了图论和拓扑学的创始人。图论诞生后，特别是近三十年来发展十分迅速，应用也十分广泛。其应用已涉及物理学、化学、运筹学、计算机科学、信息论、控制论、网络理论、社会科学、以及管理科学等诸多领域。由于图论与计算机科学紧密相联系，近若干年来，在计算机科学、计算机网络的迅猛发展下，更拓展了图论的应用发展空间。在计算机的许多领域内，它都占有一席之地。图论在矩阵论、群论等其它一些数学分支中，也有其重要的应用。张先迪等编的《图论及其应用》一书精选了内容广泛、难度各易的习题，其中的大多数习题都是对图论的进一步学习是应当掌握的。本书依序将该书的重要内容摘要列出，并将全部习题给出了详细解答。本书所涉及到的术语、符号与该书一致。有些习题存在多种解法，在一般情况下，只给出一种解法供参考。由于编者水平有限及编写时间的匆忙，书中难免出现一些缺点和错误，恳请同行专家及读者提出宝贵意见和建议，以使本书得以不断改进和完善。编者2004．7目录第一章图的基本概念1.1图和简单图1.2子图与图的运算1.3路与图的连通性1.4昀短路及其算法1.5图的代数表示及其特征1.6极图1.7交图与团图习题1第二章树2.1树的概念与性质2.2树的中心与形心2.3生成树2.4昀小生成树习题2第三章图的连通度3.1割边、割点和块3.2连通度3.3应用3.4图的宽距离和宽直径习题3第四章欧拉图与哈密尔顿图4.1欧拉图4.2高效率计算机鼓轮的设计4.3中国邮路问题4.4哈密尔顿图4.5度极大非哈密尔顿图4.6旅行售货员问题4.7超哈密尔顿图4.8E图和H图的联系4.9无限图中的欧拉,哈密尔顿问题习题4第五章匹配与因子分解5.1匹配5.2偶图的匹配与覆盖5.3Tutte定理与完美匹配5.4因子分解5.5昀优匹配与匈牙利算法5.6匹配在矩阵理论中的应用习题5第六章平面图6.1平面图6.2一些特殊平面图及平面图的对偶图6.3平面图的判定及涉及平面性的不变量6.4平面性算法习题6第七章图的着色7.1图的边着色7.2顶点着色7.3与色数有关的几类图7.4完美图7.5着色的计数，色多项式习题27.6List着色7.7全着色7.8着色的应用习题7第八章Ramsey定理8.1独立集和覆盖8.2Ramsey定理8.3广义Ramsey数8.4应用习题8第一章图的基本概念§1.1图和简单图定义1一个图G定义为一个有序对(V,E)，记为G=(V,E)，其中（1）V是一个非空集合，称为顶点集或边集，其元素称为顶点或点；（2）E是由V中的点组成的无序点对构成的集合，称为边集，其元素称为边，且同一点对在E中可出现多次。图G的顶点集也记为V(G),边集也记为E(G)。顶点集和边集都有限的图称为有限图。只有一个顶点而无边的图称为平凡图。其他所有的图都称为非平凡图。边集为空的图称为空图。图G的顶点数（或阶数）和边数可分别用符号n(G)和m(G)表示。连接两个相同顶点的边的条数，叫做边的重数。重数大于1的边称为重边。端点重合为一点的边称为环。既没有环也没有重边的图称为简单图。其他所有的图都称为复合图。边记为uv，也可记uv为e，即e=uv。此时称u和v是e的端点，并称u和v相邻，u(或v)与e相关联。若两条边有一个共同的端点，则称这两条边相邻。若用小圆点代表点，连线代表边，则可将一个图用“图形”来表示。定义2设有两个图G1=(V1,E1)和G2=(V2,E2)，若在其顶点集合之间存在双射，即存在一一对应的关系，使得边之间有如下的关系：设12uu，12vv，111,uvV，222,uvV；111uvE，当且仅当222uvE，且11uv的重数与22uv的重数相同，则称两图同构，记为G1≌G2。定义3每两个不同的顶点之间都有一条边相连的简单图称为完全图。在同构意义下，n个顶点的完全图只有一个，记为nK。所谓具有二分类（X,Y）的偶图（或二部图）是指一个图，它的点集可以分解为两个（非空）子集X和Y，，使得每条边的一个端点在X中，另一个端点在Y中；完全偶图是指具有二分类（X,Y）的简单偶图，其中X的每个顶点与Y的每个顶点相连，若|X|=m，|Y|=n，则这样的偶图记为,mnK。对于一个简单图G=（V,E），令集合1,,EuvuvuvV，则图H=（V，E1\E）称为G的补图，记为HG。定理1若n阶图G是自补的（即GG），则n=0,1（mod4）。定义4G的顶点v的度d(v)是指G中与v关联的边的数目，每个环计算两次。用G和G分别表示G的顶点的最小度和最大度。为方便，奇数度的顶点称为奇点，偶数度的顶点称偶点。设G=(V,E)为简单图，如果对所有vV，有d(v)=k，称图G为k-正则图。完全图和完全偶图,nnK均是正则图。定理2图G=(V,E)中所有顶点的度的和等于边数m的2倍，即Vvvd)(=2m推论3在任何图中，奇点个数为偶数。推论4正则图的阶数和度数不同时为奇数。定义5一个图G的各个点的度d1,d2,…,dn构成的非负整数组(d1,d2,…,dn)称为G的度序列。若对一个非负整数组(d1,d2,…,dn)，niid1=2m，存在一个简单图G，以它为度序列，则称这个数组是可图的。定理5设有非负整数组Π=(d1,d2,…,dn)，且niid1=2m是一个偶数，n-1≥d1≥d2≥…≥dn，它是可图的充要条件为Π’=(d2-1,d3-1,…,2111,1dddd,…,dn)是可图的。定理6一个简单图G的n个点的度不能互不相同。定义6设n阶图G的各点的度取s个不同的非负整数d1,d2,…,ds。又设度为di的点有bi个(i=1,2,…,s)，则有siib1=n。故非整数组(b1,b2,…,bs)是n的一个划分，称为G的频序列。定理7一个n阶图G和它的补图G有相同的频序列。§1.2子图与图的运算定义1如果VHVG，EHEG，且H中边的重数不超过G中对应边的重数，则称H是G的子图，记为HG。有时又称G是H的母图。当HG，但HG时，则记为HG，且称H为G的真子图。G的生成子图是指满足V(H)=V(G)的子图H。假设V是V的一个非空子集。以V为顶点集，以两端点均在V中的边的全体为边集所组成的子图，称为G的由V导出的子图，记为G[V]；简称为G的导出子图，导出子图G[V\V]记为GV；它是G中删除V中的顶点以及与这些顶点相关联的边所得到的子图。若V={v},则把G-{v}简记为G–v。假设E是E的非空子集。以E为边集，以E中边的端点全体为顶点集所组成的子图称为G的由E导出的子图，记为GE；简称为G的边导出子图，边集为\EE的G的导出子图简记为GE。若Ee，则用G–e来代替G-{e}。定理8简单图G中所有不同的生成子图（包括G和空图）的个数是2m个。定义2设G1，G2是G的子图。若G1和G2无公共顶点，则称它们是不相交的；若G1和G2无公共边，则称它们是边不重的。G1和G2的并图G1∪G2是指G的一个子图，其顶点集为V(G1)∪V(G2)，其边集为E(G1)∪E(G2)；如果G1和G2是不相交的，有时就记其并图为G1+G2。类似地可定义G1和G2的交图G1∩G2，但此时G1和G2至少要有一个公共顶点。G1和G2的差G1-G2是由G1中去掉G2中的边组成的图。G1与G2的对称差G1△G2是G1和G2的并中去掉G1与G2的交所得到的图，即G1△G2=(G1∪G2)-(G1∩G2)=(G1-G2)∪(G2-G1)定义3在不相交的G1和G2的并图G1+G2中，把G1的每个顶点和G2的每个顶点连接起来所得到的图称为G1和G2的联图，记为G1∨G2。定义4设G1=(V1,E1)，G2=(V2,E2)，对点集V=V1×V2中的任意两个点u=(u1,u2)和v=(v1,v2)，当(u1=v1和u2adjv2)或(u2=v2和u1adjv1)时就把u和v连接起来所得到的图G称为G1和G2积图，记为G=G1×G2。其中uiadjvi表ui和vi邻接。§1.3路和连通性定义1G的一条途径（或通道或通路）是指一个有限非空序列w=v0e1v1e2v2…ekvk，它的项交替地为顶点和边，使得对1ik，ie的端点是1iv和iv。称w是从v0到vk的一条途径，或一条（v0,vk）途径。顶点v0和vk分别称为w的起点和终点，而v1,v2,…,vk-1称为它的内部顶点。整数k称为w的长。在简单图中，途径可简单地由其顶点序列来表示，即w=v0v1v2…vk。若途径w的边e1,e2,…,ek互不相同，则w称为迹；这时w的长恰好是m(w)。又若途径w的顶点v0,v1,…,vk也互不相同，则w称为路。G的两个顶点u和v称为连通的，如果在G中存在（u,v）路。规定u和u是连通的。如果对G中每一对顶点u，v都有一条（u,v）路，则称G为连通图，否则称为非连通图。连通是顶点集V上的一个等价关系，于是可将V划分为一些等价类。设V的所有不同的等价类为V1,V2,…,Vk,这样，两个顶点u和v是连通的当且仅当它们属于同一子集Vi，称子图G[V1],G[V2],…,G[Vk]为G的连通分支，简称分支或支。记G的分支个数为ω(G)。于是G是连通图当且仅当ω(G)=1。定理9若图G是不连通的，则G是连通图。定义2称一条途径是闭的，如果它有正的长且起点和终点相同。闭迹也称为回路。若一条闭迹的起点和内部顶点互不相同，则称它为圈。长为k的圈称为k圈；按k是奇数还是偶数，称k圈是奇圈和偶圈。3圈常称为三角形。联结u和v中长度昀短的途径之长度，称为u与v的距离，记为d(u,v)。称d(G)=max{d(u,v)|u,v∈V}为G的直径。定理10一个图是偶图当且当它不包含奇圈。§1.4昀短路及其算法定义1对G的每一条边e，可赋以一个实数w(e)，称为e的权。G连同它边上的权称为赋权图。若H是赋权图的一个子图，则H的权W(H)=)()(HEeew。赋权图中路P的长定义为W(P)，距离d(u,v)仍定义为昀短(u,v)路的长。在一个赋权图中找出某类具有昀小（或昀大）权的子图，其中之一就是最短路问题最短通路算法1.记a=a1，t(a1)=0，A1={a1}，T1=Φ。2.若已得到Ai={a1,a2,…,ai}，且对1ni，已知t(an)，对每一个an∈Ai，求一点iinninbNaAB使)(min)()()(valbalnBvinnin其中N(an)是与an邻接的所有的点的集合，又称为点an的邻域或邻集。3.设有,1iimmi，而iimb使iiiimmmtalab取昀小值，令1)(iimabi，t(ai+1)=)(imat+)(1iimaal，Ti+1=Ti∪{1imaai}4.若ai+1=b，停止。否则，记Ai+1=Ai∪{ai+1}回到第二步。§1.5图的代数表示及特征定义1有n个点的一个标定图G的邻接矩阵ijAa是一个n×n矩阵，其中，如果iv邻接jv则1ija，否则0ija。定理12令G是一个有邻接矩阵A的p阶简单标定图，则nA的i行j列元素nija等于由iv到jv的长度为n的通