图论自学指导书范文.doc

图论自学指导书范文 图论自学指导书前言图论是一门应用十分广泛其内容非常丰富的数学分支，在物理、化学、生物、计算机科学、工程技术和经济管理等各个领域都可以找到图论的足迹。 它起源很早，瑞土数学家欧拉在1736年解决了当时颇为有名的一个实际问题，哥尼斯堡七桥问题，从而使他成为图论的创始人。 由于基础的图论不需要高深的数学知识，具有一定的初等性，而且图论的思想对于提高分析、解决问题的能力是十分有益的，所以深受数学竟赛命题者的青睐。 在数学竟赛中，经常出现一些以图论为背景的试题，这些试题题型新颖，内容生动诱人。 且在新课标中也已将图论列入中学数学选修课之内。 图论研究的对象是图，但这里所讨论的图并不是几何学中的图，而是客观世界中某些具体事物间某种二元关系的一个数学抽象，用顶点代表事物，用边表示各事物间的二元关系，如果所讨论的某两个事物之间有相应的二元关系，我们就在相应的两个顶点之间连一条边，这种由顶点及连接这些顶点的边所组成的图就是我们图论中所研究的图。 根据图的构造，图论方法来解决数学竞赛题的范围和基本思路是若问题中所给的条件和结论是讨论关于某些对象之间的二元关系，那我们基本上可以用图的方法来解决该问题。 其方法是用图的顶点表示问题中的对象，某两个事物之间有问题中所关注的二元关系，我们就在相应的两个顶点之间连一条边。 这样，就把一个具体问题抽象成为图论问题，我们就可以用图论的理论和方法进行探讨。 但是对于中学数学竞赛，一般并不要求学生直接用图论的定理去解题，而是运用图论中常见的处理方法（如反证法、数学归纳法、极端原理、抽屉原理、分类讨论、优化假设等）去分析图中的逻辑关系与数量关系，最终找出问题的答案。 用图论思想求解问题有两个较为明显的优点其一可将实际问题转化为一个数学问题；其二可将抽象的内在关系转化为图的外显关系。 第一章图论的基本概念通常用G=(V,E)表示图，E(G)=e1,e2,eq表示边的集合。 若边e连接顶点u与v，则记e=uv=vu，且称u与v相邻和e与u(v)关联，与同一个顶点关联的若干条边称为是相邻的，两个端点重合为一个顶点的边称为是环，若两个顶点之间有k(k2)条边连接，就称这些边为重边。 没有环也没其中V(G)=v1,v2,vp?表示顶点集合,有重边的图称为简单图。 )(GV称为图G的顶点数或阶，记为p(G),)(GE称为图G的边数，记为q(G)。 p(G)和q(G)都是有限的图称为有限图，这里仅讨论有限图。 为了方便，记NG(v)=u:u?V(G),u与v相邻称为顶点v的邻域。 在图G中，与顶点v关联的边的条数（环算2次）称为v的度数，记为dG(v)或d(v)分别用)(G?和)(G?表示图G的最大度和最小度。 当)(G?)(G?时，称G为正则图。 上述所讨论的图实质上给出了顶点之间的一种二元关系。 因而在客观世界中，一些事物间若带有某种二元关系，就可以用上面所讨论的一个图来描述这些事物间的相互关系。 像人与人之朋友关系、同学关系、相互认识关系等。 但上面所讨论的这种关系只能是具有对称性的二元关系。 而在现实生活中，有许多关系是非对称的，如认识关系，甲认识乙并不意味着乙认识甲。 在处理交通流问题时，会碰到单行道路。 像这些就不能简单地用前面所讨论的图来表示，为此需引进有向图的概念。 每条边带有方向的图称为有向图。 有向图用D=(V,A)表示，若有向边（也称为弧）a连接u到v，则记为a=(u,v),u称为a的起点，v称为a的终点。 在有向图D中，以u为起点的弧的数目称为u的出度，记为d以u为终点的弧的数目称为u的入度，记为d我们不难得到关于度数与弧数的一个关系式本章主要的定理是+(u)；(u)。 称d+(u)+d(u)=d(u)为顶点u的度数。 定理1.3.1任何一个n阶图G,均有?inivd1)(2q(G)推论1.3.2任何一个图G的奇点个数均为偶数。 重点是度与边数间的关系。 定理1.3.5对每个有向图D=(V,A)，有d这里对D中所有的顶点求和。 +(u)=d-(u)=m(D)若对于图G=(V,E)和H=(V1,E1),有V1?V,E1?E,就称H是G的子图,记为H?G。 若H?G且V(H)=V(G)，就称H为G的生成子图。 每一对顶点都有边连接的简单图称为完全图，记为Kn。 重点是度与边数间的关系和子图、生成子图概念。 一般来说，只要相应的问题讨论的是度数与边数间的关系，就可以用定理1.3.1来考虑。 若是有向图，则用定理1.3.5来考虑。 由于图论中关心的是集合中元素间的二元关系，因此对于一个图G，G的顶点的位置和边的形状都是无关紧要的。 如下面两个外形完全不同的图，在图论中看成是相同的两个图。 利用上述这些非常简单的基本概念，可以帮助我们思考和解决一些问题。 下面就是其中的几个例题。 例1（1996年全国数学联赛）有n（n?6）个人聚会，已知每个人至少认识其中的n/2个人，而对任意的n/2个人，或者其中有两个人相互认识，或者余下的n-n/2个人中有两个人相互认识。 证明这n个人中必有3个人互相认识。 注n/2表示不超过n/2的最大整数。 证明将n个人用n个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G。 由条件可知，G是具有n个顶点的简单图，并且有 （1）对每个顶点x，)(xNG?n/2； （2）对V的任一个子集S，只要Sn/2，S中有两个顶点相邻或V-S中有两个顶点相邻。 需要证明G中有三个顶点两两相邻。 反证，若G中不存在三个两两相邻的顶点。 在G中取两个相邻的顶点x1和y1,记NG(x1)y1,y2,yt和NG(y1)=x1,x2,xk,则NG(x1)和NG(y1)不相交，并且NG(x1)（NG(y1)）中没有相邻的顶点对。 情况一；n=2r此时n/2r，由 （1）和上述假设，t=k=r且NG(y1)V-NG(x1)，但NG(x1)中没有相邻的顶点对，由 （2），NG(y1)中有相邻的顶点对，矛盾。 情况二；n=2r+1:此时n/2r，由于NG(x1)和NG(y1)不相交，t?r,k?r,所以r+1?t,r+1?k。 若t=r+1,则k=r，即NG(y1)=r，NG(x1)V-NG(y1)，由 （2），NG(x1)或NG(y1)中有相邻的顶点对，矛盾。 故kr+1，同理tr+1。 所以t=r,k=r。 记w?V-NG(x1)NG(y1),由 （2），w分别与NG(x1)和NG(y1)中一个顶点相邻，设wxi0?E,wyj0?E。 若xi0yj0?E，则w，xi0,yj0两两相邻，矛盾。 若xi0yj0?E，则与xi0相邻的顶点只能是(NG(x1)-yj0)w,与yj0相邻的顶点只能是(NG(y1)-xj0)w。 但与w相邻的点至少是3，故NG(x1)NG(y1)中存在一个不同于xi0和yj0顶点z与w相邻，不妨设z?NG(x1)，则z，w，xi0两两相邻，矛盾。 例2在平面上有n个点Sx1,x2,xn，其中任两个点之间的距离至少是1，证明在这n个点中距离为1的点对数不超过3n。 证明首先建立一个图G（V，E），其中V就取S中的n个顶点，V中两个点有边相连当且仅当两点之间的距离恰好是1。 则所得图G是一个简单图，S中距离为1的点对数就是G的边数。 因此我们只需证明m(G)?3n。 我们考虑G中每个顶点的度，可以证明dG(xi)?6,i=1,2,n。 让xi是G中的任一个顶点，且与xi相邻的顶点为y1,y2,yk，则y1,y2,yk分布在以xi为圆心的单位圆周上。 所以k=dG(xi)?6,i=1,2,n。 现由定理1得2m(G)=?niivd1)(?6n故m(G)?3n。 注这个问题若用平面图来考虑，可以证明m(G)?3n-6。 若对S中两个点之间的距离不加限制，则有以下结论例3在平面上有n个点Sx1,x2,xn。 证明在这n个点中距离为1的点对数不超过4n+22n23。 证明首先建立一个图G（V，E），其中V就取S中的n个顶点，V中两个点有边相连当且仅当两点之间的距离恰好是1。 则所得图G是一个简单图，S中距离为1的点对数就是G的边数。 因此我们只需证明m(G)?4n+22n23。 用Di表示以点vi为圆心，半径为1的圆，这n个圆中两两交点总数不超过2C2n=n(n-1)个（包括重复）。 另一方面，若vk,vj与vi相邻，则vi?DkDj，因此，vi作为D1，D2，Dn中两圆的交点恰好被计数C2)(ivd次，故得C2)(ivd+C2)(2vd+C2)(n vd?2C2n=n(n-1) (1)由柯西不等式及2m(G)=?niivd1)(C2)(ivd+C2)(2vd+C2)(n vdn2(m(G)2-m(G) (2)由 （1）、 （2）得n2(m(G)2-m(G)?n(n-1)即2(m(G)2-nm(G)-n2(n-1)?0。 故可得m(G)?4n+22n23。 习题选解习题1.4证明先建立一个图G，顶点代表选手，两顶点相邻当且仅当所对应的两个代表之间进行过一场比赛。 所得图是一个简单图。 现在我们只要证明G中有两个顶点的度相等即可。 设有n个顶点，则)(G?0和)(G?n-1。 但G中)(G?=0和)(G?=n-1不能同时成立。 故当)(G?=0时)(G?n-2或当)(G?=n-1时)(G?1，故图G中的n个顶点的度数的取值只能在0,1,2,n-2或1,2,n-1中。 因此必定有两个顶点的度数是相等的。 习题1.8证明构造红蓝完全图如下用6个顶点代表6个人，如果两个人互相认识就在相应的两个顶点之间连一条红边，否则这两个顶点之间为蓝边。 得到一个红一蓝完全图K6。 现在问题转化为在K6中找同色的三角形。 考虑与顶点v关联的5条边，因这些边不是红色就是蓝色，所以这5条边中至少有三条边是同色的，不妨设vv1,vv2,vv3均为红色；再考虑边v1v2,v2v3,v3v1，若这三条边中有一条是红色，比如v1v2，则v,v1,v2构成一个红色的三角形（对应的三个人互相认识），否则v1,v2,v3构成一个蓝色三角形（对应的三个人互不认识）。 事实上红一蓝完全图K6的同色三角形至少有两个。 第二章图的连通性图G的一个点、边序列P=v0e1v1e2v2vk-1ekvk，如果ei=vi-1vi，i=1,2,k,且e1,e2,ek互不相同，则称P为一条从v0到vk的迹，当v0vk时，称C=v0e1v1e2v2vk-1ekv0为闭迹。 而当v0,v1,vk互不相同时，称P为一条v0-vk路；k称为P的长度。 当v0,v1,vk-1互不相同且v0vk时，称C=v0e1v1e2v2vk-1ekv0为回路。 在一个图G中，从u到v的所有路中，称长度最短的这条路为u-v最短路，其长度称为u与v的距离，记为dG(u,v)。 称d(G)=maxdG(u,v):u,v?V(G)为G的直径。 若图G中的每一对顶点之间都有路连接，称G为连通图，否则称为非连通图。 仅有一个顶点的图看作是连通图。 对于非连通图G，可把G分解成若干个极大的连通子图，这些连通子图称为连通分支。 对于一个连通图G的点子集V1，若G-V1非连通，就称V1是图G的一个点割集。 注意到完全图是没有点割集的。 当然完全图的连通程度也是最高的。 为了描述连通图的连通程度，我们引进连通度概念。 将连通图G的最小点割集的顶点数称为图G的连通度，记为(G)。 p阶完全图Kp的连通度定义为p-1。 规定非连通图的连通度为0。 不难看出对任何一个连通图G，0(G)p-1，当且仅当图G是完全图时右边等号成立。 在这里我们规定只要0k(G)，我们都称图G是一个k-连通图。 这个规定要避免与(G)=k混淆起来。 图G是一个k-连通图意指在图G中去掉任何一个点数少于k的顶点子集V1，所得图是仍一个连通图。 对于一个连通图G的边子集E1，若G-E1非连通，就称E1是图G的一个边割集。 注意到平凡图是没有边割集的。 完全图的连通程度也是最高的。 为了描述连通图的连通程度，我们同样引进边连通度概念。 将连通图G的最小边割集的边数称为图G的边连通度，记为(G)。 边连通度与上述点连通度有类似的概念和性质。 规定只要0k(G)，我们都称图G是一个k-边连通图。 本章主要定理是定理2.1.1若简单图G中每个顶点的度至少为k(k2)。 则G中必然含有一个长度至少是k+1的回路。 定理2.2.2设G是p阶连通图，则q(G)p(G-1)。 定理2.3.3对简单图G=(V,E)，以下几条结论成立 （1）(G)(G)，(G)(G)； （2）(G)p-1，当且仅当图G是完全图时右边等号成立； （3）(G)p-1，当且仅当图G是完全图时右边等号成立； （4）对G的任何一个顶点v，(G)-1(G-v)； （5）对G的任何一条边e,(G)-1(G-e)(G)。 定理2.3.4对任何简单图G，都有(G)(G)(G)本章的定理2.1.1说明了对于任何一个简单图G，只要每个顶点的度至少是2，这个图必存在回路，我们要用的就是这个结论。 定理2.2.2说明了连通图的边数不能太少，若一个图的边数少于p-1，那这个图必定不连通。 而边数恰好是p(G)-1的连通图也存在。 在下一章专门讨论，就是树。 定理2.3.3给出了点、边连通度的几个简单性质，对于我们理解图的连通度有帮助。 定理2.3.4给出了点、边连通度和最小度之间的关系。 一般情况下，给出这三者中的一个条件，就可以用这一定理来考虑另外的几个度量问题。 本章重点是连通的概念，点、边连通度间的关系；难点为k-连通图的特征。 例1在n*n的棋盘方格上，分别填上1,2,n2,n2，每格一个自然数。 证明必存在两个相邻（有公共边）的方格，这两个方格中所填的两数之差绝对值至少为?证明把每个方格作为顶点（n顶点，所得图记为G。 则只要证明该图G中存在一条边e，而e的两个端点的标号数之差绝?21?n。 2个）并标上该方格中所填的数，相邻的方格对应相邻的对值不小于?容易计算此图G的直径为d(G)=(n-1)+(n-1)。 即G中任意两个顶点之间有一条长度不超过2n-2的路连接它们。 ?21?n。 如果G中任意一条边的两个端点的标号数之差绝对值小于?点的标号数之差绝对值不超过?21?n。 则G的任意两个端2(n-1)?但G中必有一个顶点的标号数为n值是n?21?n-12(n-1)(22，一个顶点的标号数是1。 这两个顶点的标号数之差绝对1?n+1)-1=n2-12-1，与上矛盾。 所以G中至少有一条边e的两个端点的标号数之差绝对值不小于?21?n。 即这条边e的两个顶点所对应相邻的两个方格所填的两数之差绝对值不小于?若对上述问题进行更加细仔的分析，可以得到更强的结论例2（评委会，捷克1988）在n*n的棋盘方格上，分别填上1,2,n一个自然数。 证明必存在两个相邻（有公共边）的方格，这两个方格中所填的两数之差绝对值至少为n。 证明图G的构造与例1相同，为了方便，我们仍将图G的顶点按原来的次序排列成n*n的棋盘形式。 现在我们只要证明该图G中存在一条边e，使e的两个端点的标号数之差绝对值不小于n。 反证法若结论不成立，即对G中每一条边e，e的两个端点的标号数之差绝对值至多是n-1，对每个k1,2,nAk=1,2,k,Ck=k+1,k+2,k+(n-1),Bk=k+n,k+n+1,n顶点与Bk中的任何一个顶点标号之差绝对值至少为n，故Ak与Bk之间没有边连接。 又Ck=n-1。 因此该图中必存在由某一整行所构成的路Pk和某一整列所构成的路Qk均不含Ck中的顶点，因此路Pk和Qk中的顶点只能同时含在Ak或能同时含在Bk中。 当k=1时，A1=1，因此B1同时含有一整行和一整列，即含P1和Q1。 而当k=n有一整行和一整列即含有Pk和Qk。 于是存在k1,2,nBk均含有一整行和一整列，但Bk+1不具有此性质，则Ak+1含有Pk+1和Qk+1。 所以Bk含Pk和Ak+1含Qk+1,即Bk和Ak+1相交，因此存在mBkAk+1,则有k+nmk+1，由此可得n1，矛盾。 ?21?n。 2,n2，每格2，将图G的顶点集合V=1,2,n2分类令2。 由于Ak中的任何一个2-n时，Bk=1，故此时Ak含2-n-1，使得B1，B2，推论2.2.5若G是简单图，)(G?p(G)/2。 则是G连通图。 证明反证法若G非连通，让G1是G中一个阶数至多是p(G)/2的连通分支。 则G1中每个顶点的度至多是p(G1)-1?p(G)/2-1。 因此)(G?p(G1)-1?p(G)/2-1。 矛盾。 这个证明非常简单，但这是一个非常有代表性的证明，一般情况下，给定若干以度或边数作为条件，证明相应的图是连通图，基本上用这种方式来证明。 如习题2.17就是一例。 习题选解习题2.6证明在图G中取一条最长路P=x1x2xk,则与x1相邻的顶点均在P中，由于G中每个顶点的度至少为3，故与x1相邻的顶点至少有3个，取两个不同于x2的邻点xi与xj(不妨设ij-1)则我们可以构造出三个回路C1=x1x2xix1,C2=x1x2xjx1,C3=xixi+1xjxi,这三个回路的长度分别为i,j和j-i+1。 故不存在大于2的整数k能整除G中每个回路的长度。 习题2.8反证法若结论不成立，则存在两条没有公共顶点的最长路P=x1x2xk Q=y1y2yk因为G是连通图，G中存在从x1到y1的路P1，不妨设P1与P的最后一个公共顶点为xi，自xi后沿P1与Q的第一个公共顶点为yj，则P(x1,xi)或P(xi,xk)中的一段，Q(y1,yj,)或Q(yj,yk)中的一段和P1(xi,yj)一起组成G中一条比P更长的路，与P是一条最长路相矛盾。 习题2.12证明若图G是非连通图，则取G中的两个连通分支G 1、G2，并设p(G1)=p1,p(G2)=p2,则p1+p2p(G)。 在G1中取一个顶点u，在G2中取一个顶点v，因为G是简单图，所以d(u)p1-1，d(v)p2-1，因此我们有u与v在G中不相邻，且d(u)+d(v)p(G)-2,矛盾。 所以G是连通图。 习题2.13证明设e是C中的一条边，并记e=uv。 在G-e中任取两个顶点x和y，因为G是连通图，在G中存在一条u-v路P，若P不含边e，则P就是G-e中的一条u-v路；若P含边e，则P(x,u)(C-e)P(v,y)就是G-e中的一条u-v途径，因此在G-e中存在一条u-v路。 因此，无论怎样，G-e中存在一条u-v路，所以G-e是连通图。 习题2.22证明若G是2-连通图，则G+uv显然是2-连通图。 反之，假设G+uv是2-连通图，我们要证明G也是2-连通图。 否则，若G不是2-连通图，则存在一个顶点w，使G-w是非连通图。 则由于G+uv是2-连通图，所以u和v不会在G-w的同一个连通分支中。 不妨设u含在G-w的连通分支G1，v含在G-w的连通分支G2中，则d(u)p(G1)，d(v)p(G2),但p(G1)+p(G2)p(G)-1,d(u)+d(v)p(G)-1，这与给定的条件相矛盾。 第三章树根据定理2.2.2，连通图G的边数至少是P(G)-1。 这一章我们要考虑的是边数等于P(G)-1的连通图。 对于这一类图，我们可以断定G无回路，否则，我们可以利用习题2.13的结论，构造出一个边数少于P(G)-1的连通图。 这与定理2.2.2矛盾。 为此我们定义没有回路的连通图称为树。 树中度为1的顶点称为叶。 连通图G的一个生成子图T，若T也是树，就称T为G的生成树。 在实际应用中我们用的比较多的一类图是赋权图每一条边带有一个实数的图称为赋权图，赋权图G中，边e的权记为w(e)，称为边e的权，赋权图也记为G=(V,E,w)。 赋权图G的一个子图H，H中所有边的权的总和记为w(H)。 对于连通赋权图G的一个生成树T，若T是G中的所有生成树中权和最小的一个生成树，就称T是G的一个最优树。 本章中主要定理是定理3.1.1一个简单图T是树当且仅当T中任意两个不同顶点之间有且只有一条路连接。 定理3.1.2下述论断是等价的 （1）图T是树； （2）T连通且q(T)=p(T)-1； （3）T无回路且q(T)=p(T)-1； （4）T连通且T的每一条边都是割边； （5）T无回路，并且对T中任意两个不相邻的顶点u和v，T+uv有且只有一个回路。 定理3.1.3至少有二个顶点的树至少有两片叶。 树T恰好有两片叶当且仅当T本身是一条路。 定理3.2.1图G是连通图当且仅当G含有生成树。 Kruskal算法图G是连通的赋权图 （1）在G中选取边e1，使w(e1)尽可能小； （2）若已选取边e1,e2,ei，则从E(G)-e1,e2,ei中选取边ei+1，使满足以下两条（a）Ge1,e2,ei,ei+1不含回路；（b）在满足（a）的前提下，使w(ei+1)尽可能小； （3）当 （2）不能继续执行时，停止。 由Kruskal算法最后所得到的图T每一步都不允许出现回路，故TGe1,e2,ek不是G的生成子图，则可以在E(G)-e1,e2,ek中选出边ek+1，使得ek+1的端点至少有一个不在Ge1,e2,ek上，因此Ge1,e2,ek,ek+1无回路，从而存在满足算法 （2）的边ek+1，也即Kruskal算法在第k步后还可以继续执行，矛盾。 若Ge1,e2,ek不连通，由于G连通，在G中取一条连接Ge1,e2,ek的两个连通分支的一条边e，因此Ge1,e2,ek,e也无回路，此时Kruskal算法仍可继续执行，又是矛盾，故T就是G的生成树。 同时还可以证明是G的最优树。 对于该算法作一适当的改进，我们就可以去求连通的赋权图中权和最大的一个生成树。 我们注意到定理3.1.2，该定理的前三条说明了树的三个明显的特征是连通、无回路、q(G)=p(G)-1。 这三条中的任何二条都可以作为树的等价命题。 定理3.2.1的内容、结论虽然比较简单，但对于处理连通图中的一些问题是非常有效的，如习题3.12，3.13等都可以通过生成树来考虑。 对于一个连通图来说，生成树是不唯一的，当然最优树也是不唯一的。 本章的重点是树的等价命题，求最优生成树（Kruskal算法）。 难点为树的等价命题的证明。 例1（第24屇莫斯科奥赛试题）n个点由若干线段连接着。 已知每一点与另外任何一点都有道路相连通。 而任何两点都没有两种不同的道路。 证明线段总数为n-1。 证明构造图G将问题中给定的n个点作为顶点，线段作为边。 根据给定的条件，所得图G是含有n个顶点的简单图，每一对顶点之间有且只有一条路连接，因此G是连通图，并且没有回路（否则，该回路上两个不同的顶点之间有两条不同的路），所以图G是一棵树。 下面用归纳法证明G含有n-1条边。 若n=1，结论显然成立。 归纳假设当n=k时结论成立，下面证明当n=k+1时结论也成立。 因n2，由定理5，G含有叶，设u是其中一张叶，在G中将u及与u关联的这条边一起删除，所得图记为H，则H是含有n-1=k个顶点的树。 由归纳假设，m(H)=m(H)-1=(n-1)-1。 因此，我们有m(G)=m(H)+1=n-1=n(G)-1。 这样我们就证明了图G的边数是n-1，因此线段的总数是n-1。 其实我们也证明了下面两个定理3.1.1和定理3.1.2中的 （2）例2（1987，全国数学联赛）设n?3，且n名乒乓球选手单打比赛若干场后，任意两名选手已赛过的对手恰好都不完全相同。 证明总可以从中去掉一名选手，使得余下的选手中，任意两名选手已赛过的对手仍然都不完全相同。 证明这个问题要在证明过程中来构造图G。 用v1,v2,vn表示n名选手，同时也作为=Ge1,e2,ek就是G的生成树，这是因为算法的中无回路。 当Ge1,e2,ek不是G的生成时，即=Ge1,e2,ekH的边数图G的顶点。 假设结论不成立，即对每个k1,2,n，去掉选手vk之后，总有两名选手，设为vi、vj,他们在余下的选手中，已赛过的对手完全相同，就在vi与vj之间连上一条边，并将该边记为ek。 于是得到图G，G是含有n个顶点、n条边的简单图。 根据定理7，G不是树，可以断定G有回路。 否则，因为G不是树，G非连通，设G的所有连通分支为G1,G2,Gr,则每个Gi都是树，由定理7，m(Gi)=n(Gi)-1,i=1,2,r。 则m(G)=m(G1)+m(G2)+m(Gr)=(n(G1)-1)+(n(G2)-1)+(n(Gr)-1)=n-r矛盾！所以G中存在一个回路，记为C=vi1,vi2,vir,vi1,其中的边依次为ek1,ek2,ekr。 记选手vij的对手集为Aj,j=1,2,r。 现在来考虑这r个对手集A1,A2,Ar,由于ek1=vi1vi2,根据图G的构造，A1-vk1=A2-vk1,即选手v2的对手集A2是在A1中添加或删除顶点vk1所得到的；同样由ek2=vi2vi3,A3是在A2中添加或删除顶点vk2所得到的；最后由ekr=virvi1,选手v1的对手集A是在Ar中添加或删除顶点vk1所得到的；由于vk1,vk2,vkr两两不同，A和A1是不可能相同的，但A和A1同为选手vi1的对手集，故A=A1，矛盾。 根据例2的证明过程，我们不难得到下面的结论成立若简单图后G的边数q(G)p(G)，则G含有回路。 例3某镇有居民xx人，每天他们中的每一个人把昨天听到的消息告诉他所认识的人。 已知任何消息，只要镇上有人知道，都会经这种方式逐渐地为全镇人知道。 证明可以选出105个居民代表，使得只要同时向他们传达某一消息，经过18天后，就会为全镇人所知道。 提示构造图G，顶点代表居民，两顶点相邻当且仅当所对应的两个居民互相认识。 根据给定的条件，图G是具有xx个顶点的连通图，不妨假设G就是树。 在G中取一条最长路P=v1v2v3vr，则rxx。 现取v19作为一个居民代表。 在G中去掉边v19v20，将G分成两棵子树G1和G2（G1是含v19的一棵树）。 对G2作同样的处理，我们可得到不超过105个类似的居民代表。 习题选解习题3.2反证法若结论不成立，即G中没有回路，我们考虑G中的k个连通分支G1,G2,Gk。 则对每一个连通分支Gi来说，Gi是树，因此有q(Gi)=p(Gi)-1,i=1,2,k.这样我们就可以得到q(G)=(p(G1)-1)+(p(G2)-1)+(p(Gk)-1)=p(G1)+p(G1)+p(G1)-k=p(G1)-k这与给定的条件相矛盾。 习题3.4证明设T中有k个度为1的顶点，s个度为2的顶点，则T的顶点个数为p(T)=k+s+n3+n4+n(T)又T是树，故T的边数q(T)=p(T)-1。 应用定理1.3.1，我们有2(p(T)-1)=k+2s+3n3+4n4+(T)n(T)2(k+s+n3+n4+n(T)-1)=k+2s+3n3+4n4+(T)n(T)从上式可以解出k,有k=n3+2n4+(T)-2)n(T)+2习题3.7证明最简单的一个证明是直接应用习题3.4。 也可以直接去证明。 设T中有个度为1的顶点个数为s，并记T中一个度为(T)的顶点为u，则2(p(T)-1)s+d(u)+2(p(T)-s-1)=s+(T)+2(p(T)-s-1)由此可得sk。 习题3.12证明因为G是连通图，故G中存在一个生成树T，由于T的顶点个数至少是3，由定理3.1.3，T中含有二个悬挂点，不妨记其中的两个悬挂点为u、v，则T-u,v仍是一棵树，而且是G-u,v的生成树。 故G-u,v仍然连通。 习题3.13证明其实我们可以证明更强的结论对于任意的一个正整数k，只要kp(G)-2，G中存在k个顶点v1,v2,vk，使G-v1,v2,vk仍为连通图。 因为G是连通图，故G中存在一个生成树T，由于T的顶点个数至少是3，由定理3.1.3，T中含有二个悬挂点，不妨记其中的两个悬挂点为v1,v2,则T1=T-v1,v2仍是一棵树，而且是G-v1,v2的生成树。 若2k-1，对树T1同样有两个悬挂点或只需一个悬挂点，不妨记为v3,v4,则T2=T1-v3,v4仍是一棵树，故G-v1,v2,v3,v4仍为连通图。 若4k-1，我们可以继续这一过程，直到找出所需的k个顶点。 第四章欧拉环游和Hamiltom回路包含图G的所有边的迹称为G的欧拉迹。 起点与终点不同的欧拉迹称为欧拉环游，起点与终点相同的欧拉迹称为欧拉环游。 通常我们所碰到的判断一个图形是否能一笔画（即把一个图形不重复地一笔画成），就相当于去判别把这个图形中各线段的交叉点和端点作为顶点，线段本身作为边的图是否有欧拉环游或欧拉通路。 在一些竞赛问题中所表现出的一些图形是否能一笔画问题，基本可以转化为判断对应的图是否有欧拉环游或欧拉通路来考虑。 Hamilton问题是图论中一直悬而未解的一大问题，它源于一个周游世界的游戏。 其定义为图G的一个含所有顶点的回路称为G的一个Hamilton回路，同时称一条含所有顶点的路为G的一条Hamilton路。 而称含有Hamilton回路的图为Hamilton图。 从定义可知，一个图的Hamilton回路与Euler环游的概念是非常相似的，差别在于Hamilton回路是环游G的所有顶点的回路，而Euler环游是环游G的所有边的闭迹。 对于一个图是否存在Euler环游有一个非常简洁的判别法。 但是要判别一个图是否存在Hamilton回路却非常复杂，至今没有一个简洁的判别法。 本章的主要定理是定理4.1.1一个非平凡连通图G有欧拉环游的充要条件是G的每个点的度为偶数。 定理4.1.3一个连通图G有欧拉通路的充要条件是G恰好有两个奇点。 定理4.3.1若图G是Hamilton图，则对V(G)的每一个非空真子集S，均有w(G-S)S定理4.3.2设G中任意两个不相邻的顶点u与v，均有dG(u)+dG(v)p(G)则G是Hamilton图(p(G)3)。 推论4.3.3若G是具有p(G)(p(G)3)个顶点的简单图，每个顶点的度至少为p(G)/2。 则G是Hamilton图。 定理4.3.4设G是连通图，u与v是G中两个不相邻的顶点，满足dG(u)+dG(v)p(G)则G是Hamilton图当且仅当G+uv是Hamilton图。 这一定理其实给我们提供了一个讨论Hamilton性的工具若能在G中找到一对不相邻的顶点u与v使dG(u)+dG(v)p，则G与G+uv=G1有相同的Hamilton性质。 同样若在G1中找到一对不相邻的顶点x与y使dG1(x)+dG1(y)p，则G1与G1+xy=G2有相同的Hamilton性质。 继续这一过程，由于G是有限图，必终止于某一步，最后所得到的图记为C(G)，称为G的闭包。 要根据定理4.3.4的结论，我们马上可得定理4.3.5图G是Hamilton图当且仅当C(G)是Hamilton图。 本章重点是Euler图的判别和Hamilton图的充分性；难点为Hamilton图的充分性证明。 例1（1964，波兰奥赛试题）在圆上任取个n点，把每个点用线段与其余各点相连。 能否一笔画岀所有这些线段，使第一条线段的终点与第二条线段的起点相重，第二条线段的终点与第三条线段的起点相重，最后一条线段的终点与第一条线段的起点相重？解以这n个点作为顶点，这些线段作为边构成一个连通图G（实际上该图是具有n个顶点的完全图Kn），G的每个顶点的度为n-1。 则上述问题有解的充要条件是图G有欧拉环游。 当n为奇数时，G中每个顶点的度为偶数。 此时我们可以证明图G有欧拉环游。 由于G中每个顶点的度为偶数，从G的任何一个顶点出发，必能找出一条闭迹，由此在G中取一条最长的闭迹，记为C。 下面证明C包含G的所有边，即C就是G的欧拉环游。 若C并没有包含G的所有边，则图G-E(C)没有奇点，且有一个至少有一条边的连通子图G1。 因为G是连通图，G1与C有公共顶点，设为v0，在G1中从v0出发，可得到一条闭迹C1。 显然C与C1没有公共边但有一个公共顶点v0，我们可将C和C1通过公共顶点v0合为一个闭迹C0，显然C0的长度大于C的长度，矛盾。 这就证明了C就是图G的欧拉环游。 即上述问题可以一笔画。 当n为偶数时，则G中每个顶点的度为奇数，图G显然不存在欧拉环游。 因此上述问题不能一笔画。 该例的证明过程，实际上也是定理9的证明。 例2（1990，中国数学奥林匹克试题）凸n边形及其n-3条在形内不相交的对角线组成的图形称为一个剖分图，证明当且仅当3n时，存在一剖分图是可以一笔画成的。 证明将凸n边形的n条线段及n-3条对角线作为边，凸n边形的n个点作为顶点，所得图记为G（这些点和边保持原形状、位置不变）。 则凸n边形存在一剖分图可以一笔画成（封闭）的充要条件是图G有欧拉环游。 充分性给定的条件是3n。 下证凸n边形有一个可以一笔画（封闭）的剖分图。 对n进行归纳。 当n=3时结论显然成立。 归纳假设n=3k结论成立。 下面考虑n=3k+3。 取一个凸n边形，记为C=v1v2v3k+3v1，在C中加一条对角线v1v5，将C分成两个凸多边形C1=v1v5v6v3k+3v1,C2=v1v2v3v4v5v1。 其中C1是凸3k边形，由归纳假设在，C1中可加3k-3条对角线使之构成一个有欧拉环游的剖分图，记所对应的图为G1，则图G1有欧拉环游。 再在C2中加对角线v1v3和v3v5，对应的图记为G2，G2中除v1和v5的度为奇数3外其它顶点的度均为偶数。 G1与G2有且只有一条公共边v1v5，所以图G=G1G2中没有奇点，因此G有欧拉环游。 返回到凸n边形C=v1v2v3k+3v1，我们将C1和C2中的对角线加到C中，再加上v1v5，这样在C中加了3k-3+2+1=3k=n-3条对角线且这些对角线两两不相交，因此得到凸n边形C的一个剖分图，并且对应的图就是G，所以凸n边形存在一剖分图可以一笔画成。 故n=3k+3时充分性也成立。 根据归纳原理，对于一切3n的正整数n，充分性成立。 必要性设凸n边形存在一剖分图可以一笔画成（封闭），即对应的图G有欧拉环游。 则G的每个顶点的度为偶数，因此G中每个顶点所引出的对角线有偶数条。 故可将G中的每个基本三角形用红、蓝两色中的一种颜色进行染色，使有公共边的三角形（称为相邻）不同色。 因对每个顶点u，以u为一个端点的三角形有奇数个，这些三角形相邻的不同色，所以这些三角形中含有凸n边形中的边的两个三角形（若u的度至少是4）是同色的。 于是含有凸n边形中的边的这些三角形都同色，不妨设为红色。 则凸n边形中的每条边只能是一个红色三角形的边，而每条对角线既是一个红色三角形的边也是一个蓝色三角形的边。 若记红色三角形的个数为p，蓝色三角形的个数为q，则3p-3q=n，故3n。 习题选解习题4.2证明若图G是Euler图，则G的每个顶点的度至少为2，根据定理2.1.1的结论，G中存在一个回路，记为C1。 考虑G1=G-E(C1)，若G1没有边，则E(G)=E(C1)，若G1有边，则考虑G1的非平凡连通分支H，同样由定理2.1.1，H中存在一个回路，记为C2，显然C1与C2没有公共边。 再考虑G2=G1-E(C2)。 继续这一过程。 我们能找到一系列边不交的回路C1,C2,Ck，使E(G)=E(C1)E(C2)E(Ck)反之，因为回路中每个顶点的度为2，若一个顶点u含在k个回路上，又这些回路的边互不相交，故这个顶点的度就是2k，因此这个连通图是Euler图。 习题4.3证明对于G中的每一个顶点u，假设G-u的连通分支为G1,G2,Gk，因为图G有Euler环游，故u与每一个连通分支Gi至少有二条边连接，i=1,2,k。 因此kd(u)/2。 即w(G-S)d(u)/2。 习题4.12证明因为图G有Hamilton路，取G的一条Hamilton路P，对于V(G)的任意一个真子集S，则P-S至多被分割成S+1段，即w(P-S)S+1，故w(G-S)S+1习题4.14证明我们只要证明回路C包含图G中的所有顶点即可。 反证法若结论不成立，即G中存在一个顶点x不含在回路C中。 因为G是连通图，顶点x到回路C有路存在，不妨设P是一条从x到C的路，P的另一个端点为y，且P与C只有一个交点y。 在C中取一条与y关联的边e，则P(C-e)是G中的一条路，这条路的长度比路C-e更长，这与给定的条件矛盾。 所以回路C已经包含了G中的所有顶点，即C本身就是G的一条Hamilton回路。 习题4.17证明我们来构造图G的闭包对于V(G)-u1,u2中的任意两个不相邻的顶点x与y，因为x与y的度数至少是p/2，根据闭包构造原理，可以在x与y之间加一条边，因此我们可以将V(G)-u1,u2中的任意两个不相邻的顶点都可以加一条边。 这样我们可以得到图G1，对于图G1来说，V-u1,u2中的每一个顶点的度至少是p-3，而顶点u1的度至少是3，同样根据闭包构造原理，u1可以与V-u1,u2中的每一个顶点加一条边，我们可以得到图G2。 对于图G2来说，V-u2中的每一个顶点的度至少是p-2，而顶点u2的度至少是2，同样根据闭包构造原理，u2可以与V-u2中的每一个顶点加一条边。 最后所得到的图就是图G的闭包C(G)，并且C(G)是完全图。 根据定理4.3.5，图G是Hamilton图。 习题4.18证明为了方便，记p=p(G)。 在图G外取一个顶点w，让w与G中的每一个顶点之间加一条边，所得到的图记为H。 则H中顶点w的度数是p(H)-1=p，其它每一个顶点的度数增加1，故H中每一对不相邻的顶点的度数至少是(p-1)+2=p+1=p(H)。 根据定理4.3.2，图H有Hamilton回路，记为C，现在我们只要将C中的顶点w删除，得到的就是图G中的一条Hamilton路。 第五章图的对集与独立集若能将图G的顶点集V划分成二个子集X与Y，使G中的每一条边的两个端点分别在X和Y中，我们就称图G为二分图，记为G=(X,Y,E)。 根据定义，若图G是二分图，且相应的二分划为X和Y，则G中由X和Y所导出的子图GX、GY都是空图，反之也成立。 对于无环图G=(V,E)的一个边子集M，如果M中的边两两不相邻，就称M为图G的一个对集。 而M中的一条边e的两个端点