《图论习题.ppt》由会员分享，可在线阅读，更多相关《图论习题.ppt（68页珍藏版）》请在三一文库上搜索。
1、图论习题,一、握手定理的应用 二、平面图、欧拉公式的应用 三、图的基本概念与应用 四、欧拉图和哈密顿图 五、图的着色,一、握手定理的应用,1. 已知具有n个度数都为3的结点的简单图G有e条边， （1）若e=3n-6，证明G在同构意义下唯一，并求e，n。 （2）若n=6，证明G在同构意义下不唯一。 提示：握手定理（北师大2000考研）,解： （1）由握手定理，3n=2e; 因为e=3n-6，所以n=4，e=6。这样的图是完全图K4，所以在同构的意义下唯一。 （2）由握手定理，3*6=2e；e=9。在同构的意义下不唯一。,2. 无向图G有21条边，12个结点度数为3，其余结点度数为2，求G的顶点数
2、。 提示：握手定理（北大2001考研）,解：,3. 已知n个结点的简单图G有e条边，各结点度数为3，2n=e+3。试画出满足条件的所有不同构的G。 提示：握手定理（西南交大2000考研/北京大学1990考研） 参考1(2),解：由握手定理，e=(3n/2)；由已知，e=2n-2；所以n=6，e=9。 在同构意义下G不是唯一的。,4. 设树T有17条边，12片树叶，4个4度内结点，1个3度内结点，求T的树根的度数。 （提示：握手定理。北大1997考研）,解：结点数为17+1=18 由握手定理，12*1+4*4+1*3+1*l=34, l=3.,5. 设无向树T有3个3度，2个2度结点，其余结点都
3、是树叶，问T有几片树叶？ 握手定理,6. 证明：在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。 /*等价于：至少有两个顶点的简单图有两个相同度数的顶点 /*中国科学院自动化所1998考研,二、平面图、欧拉公式的应用,1，关于平面图的不等式的证明 欧拉公式及其推论的运用 2，非平面图的判定 应用库拉托斯基定理,1. 设G是n个结点的连通简单平面图，若n3，则G中必有一个结点度数不超过5。 提示：涉及度数，握手定理；连通平面图，欧拉公式；简单平面图，若n3，欧拉公式的推论 （西南交大1999考研）,证明： 握手定理：dev(vi)=2e; 反证：设每个结点的度数超过5，即dev(
4、vi)6，则2e=dev(vi)6n, 所以e3n. 由欧拉公式的推论，e3n-6。 所以矛盾。,2. 证明彼得森图是非平面图。 提示：要证明一个图不是平面图，首先考虑应用库拉托斯基定理。即在要判别的图中，找出一个K5或K3,3的剖分。 （西安交通大学1997考研）,3. 证明小于30条边的简单平面图G中，至少有一个度数小于等于4的结点。,证明：不妨设G是连通图。 因为e3n-6，假设所有顶点度数大于等于5；由握手定理，dev(vi)=2e; 所以2e5n，则有n2e/5。 代入e3n-6，则e6e/5-6, 从而e30。所以矛盾。,4. 证明在简单平面图G中， f 和n分别表示该图的面数和结
5、点数， (1) 如果n3，则f 2n-4。 (2) G中结点最小的度(G)=4，则G中至少有6个结点的度数小于等于5。 （西安交通大学1996考研）,（1）证明：假设图中的边数为e。由于简单图的每个面至少由3条边围成，因此3f 2e。由欧拉公式n-e+f=2，得e=n+f-2；代入3f 2e得到3f 2(n+f-2)，得f 2n-4。,（2）证明：（反证法） 假设G中至多有5个结点的度数小于等于5。因为(G)=4，则d(v)54+6(n-5)。因为d(v)=2e，则e3n-5。由(1)，e3n-6。,5. 设G是由n个结点，e条边，(2)个连通分支的平面图，G的每个面至少由k（k3）条边围成，
6、则,证明：设G的面数为f，各面的度数之和为T，T=2e。因为G的每个面至少由k条边围成，所以k*fT=2e。由欧拉公式的推广，f=+1+e-n, k*( +1+e-n)2e. 所以命题成立。,三、图的基本概念与应用,1. 补图 2. 连通性,补图,1. 证明无向图G是不连通的，则它的补图是连通的。 提示：分而治之（西南交大1999考研） 证明连通的两种方法：直接证明，反证法,证明：设G=(V, E), 根据连通分支将V划分为V1, V2, , Vn，并设Vi=u1, u2, , ur，Vj=v1, v2, , vs，ij，1i,jn，Ek表示完全图的边集。 任取V中两个结点，分两种情况讨论：
7、（1）设uiVi, vjVj. (ui, vj)E, 则(ui, vj) Ek E. 所以ui, vj是连通的。即在不同连通分支中的两个结点在补图中是连通的。 （2）设ui, ujVi, vjVj. 由(1)，(ui, vj) Ek E, (uj, vj) Ek E. 所以ui, uj通过vj连通。即在相同连通分支中的两个结点在补图中是连通的。 所以，命题成立。,2. 一个图如果同构于它的补图, 则该图称为自补图. 1)试给出一个5个结点的自补图; 2)证明: 一个图是自补图, 其对应的完全图的边数必是偶数; 3)是否有3个结点或者6个结点的自补图.,2)证明：如果一个图是自补图，设该图的边数
8、为e，则该图的自补图的边数也为e，所以对应的完全图的边数是2e，为偶数。,3)解：3个结点或者6个结点的完全图的边数分别为3和15，是奇数；所以不存在3个结点或者6个结点的自补图。,连通性,证明连通的两种方法: 直接证明/反证法. 证明连通的直接证明方法：任取图中两点，寻找这两点间必定存在路。 证明连通的反证法: 首先假设图不连通，则它具有多个连通分支，然后根据题目条件推出矛盾。推矛盾的过程，通常是将具有多个连通分支的图的边数放到最大的过程（放缩法），即使每个连通分支都是完全图，然后推出边仍然不满足条件。,1. n个结点的简单图G，n2且n奇数，G和G补图中度数为奇数的结点个数是否相等？请证明
9、或给出反例。 （西南交大2001考研）,解：一定相等。 因为n2且n奇数，则对于奇数个结点的完全图，每个结点的度数必为偶数。若G中度数为奇数的结点个数是m，则G的补图中m个结点的度数为（偶数-奇数）=奇数。 G中度数为偶数的结点，在G的补图中这些结点的度数仍为（偶数-偶数）=偶数。 所以命题成立。,2. 设无向图G有n个结点，n2。证明： 1）当(G)n/2时，G是连通图； 2）当(G)(1/2)(n+k-1)时，G是k-连通图，其中1 k n-1。 (北京大学1994年考研),3. 若G为简单图，且 ，则G是连通的。其中m和n分别为该图的边数和顶点数。 /*中国科学院自动化所1998考研,证
10、明方法： 1）反证法（简捷） 2）数学归纳法：对顶点数进行数学归纳,反证法： 证明：假设G不是连通的，则G至少存在两个连通分支。设G有两个连通分支C1和C2，则G的最大可能的边数m=x(x-1)/2+(n-x)(n-x-1)/2，其中1xn-1；所以m的最大 所以导致矛盾，则G是连通的。,4. 设G=(V, E)是连通简单图，但不是完全图，则存在3个结点u、v和w, 使(u, v), (v, w)E，但(u, w)E。 /*中国科学院计算所1993考研,证明方法： 1）反证法 2）数学归纳法,5. 设G为非平凡有向图，V为G的结点集合，若对V的任一非空子集S，G中起始结点在S中，终止结点在V-
11、S中的有向边至少有k条，则称G是k边连通的。 证明：非平凡有向图是强连通的充要条件为它是一边连通的。 /*中国科学院计算所1999考研,证明： /*必要性证明*/ 因为设G为强连通的，假设从S到V-S没有有向边，则S中的任一顶点u到V-S中的任一顶点v均没有有向道路，从而与G为强连通的相矛盾。所以从S到V-S至少有一条有向边，即G为一边连通的。,/*充分性证明*/ 设G为一边连通的，对任意的u, vV, 则u到V(G-u)至少有一条边，设为(u, u1)，而u, u1到V-u, u1至少有一条有向边(u, u2)或(u1, u2)。无论哪种情况都有从u到u2的有向道路，因为G中结点数有限，所以
12、通过如上递归地求解，一定有从u到v的有向道路。所以G为强连通的。,6. 设简单平面图G中顶点数n=7，边数e=15，证明G是连通的。 提示：反证,7.简单图G由图H和两个孤立点组成，图H不含孤立点，为平面图，证明H为连通图。 （中国科学院软件所1994考研）,8. 若G为简单图, 且 , 则G是连通的. 其中m和n分别为该图的边数和顶点数. 给出一个有n个结点而不连通的简单图,其边数恰好为 . /*华中科技大学2000考研,9. 能否画一个简单无向连通图，使各结点的度数与下面给出的序列一致？如可能，则画出符合条件的图，所画图是二分图？如不能，则说明原因。 （1）1，2，3，2，1，1 （2）1
13、，1，2，3，2，2 （3）1，2，3，4，5，5 （4）2，2，2，3，3，4 （西南交大1995考研）,(1) V1=a, c, e, V2=b, d, f. (2) 不可能画出图。(顶点度数之和为偶数) (3) 不可能画出图和二分图。由于有两个结点的度数为5，则该两个结点的度数必与其余5个结点有边相连（因为是简单图），所以其余4个结点度数至少为2，但有一个结点的度数为1。 (4) (1, 6, 4, 5, 6, 1)，回路长度为奇数，所以不是二分图。,10 设图G有n个结点，r个连通分支，则图G的路径矩阵的秩为n-r。,证明：设图G的r个连通分支为G1, G2, , Gr。得分块路径矩阵
14、如下：,因为Gi是连通图，Gi的秩是连通分支Gi的结点个数-1，所以rank(G)=rank(Gi)=n-r。,本题背景： 1 线性相关/线性无关 如果对m个向量1, 2, ., mFm，有m个不全为零的数k1, k2, ., kmF，使k11+k22 +.+kmm=0n成立，则称1, 2, ., m线性相关；否则，称1, 2, ., m线性无关。,2 向量组的秩 如果向量组1, 2, ., s中存在r个线性无关的向量，且其中任一个向量可由这r个线性无关的向量线性表示，则数r称为向量组的秩，记作1, 2, ., s =r。,9. 若图G=(V, E)是连通图，且eE，证明： (1)e属于每一棵
15、生成树的充要条件是e为G的割集； (2)e不属于G的任何一棵生成树的充要条件是e为G中的环。 提示：反证,分析： (1) e属于每一棵生成树, 要证G删去e后必不连通，否则矛盾。 (2),证明：（1） ： e属于每一棵生成树, 若e不是G的割集，G-e连通，则G-e中必存在生成树T，因为T也是G的生成树，但T不包含e，导致矛盾。 ：设e不是G的割集，若有G的生成树T，则T+e包含回路。则删去e后连通，则与e是G的割集的假设矛盾。,15. 具有(2)棵树的森林，恰巧加多少新边能使森林变树？,n个结点， (2)棵树，n-条边 n个结点的树，n-1条边 （n-1）-（n-）=-1,16. 已知n个结
16、点（n2）的简单无向图G具有n-1条边，G是树吗？ 提示：定义7.1 定理7.1,四、欧拉图和哈密顿图,1 证明：在无有向回路的竞赛图G=(V, E)中，对任意的u,vV, d+(u)d+(v)。 /*中国科学院软件所*/ /*反证*/,证明：假设G中存在两个顶点u, v， d+(u) =d+(v)。因为G是竞赛图，所以设(u, v)E, 在G中存在顶点w，使得(v, w)E, (u, w)E。所以，根据竞赛图的性质， (w, u)E。则构成有向回路u, v, w, u。导致矛盾。所以命题成立。,证明欧拉图：按照充要条件,证明哈密顿图：抽象图，充分条件或必要条件；具体图，比较困难,五、图的着色
17、,四色猜想和五色定理相对平面图而言 上海交通大学4次考到五色定理的证明 顶点着色,1 图G(V, E)称为k色临界图是指，对任意vV，均有(G-v)(G)=k。 证明：在k色临界图中，(G)k-1，其中(G)=mind(v)|vV。 中国科学院软件所1995,证明：/*反证法*/ 若在图G中存在v0V，d(v0)k-2。因为G是k色临界图，所以对G-v0可作k-1正常着色。又因为在G中与v0邻接的结点个数k-2，所以在G-v0中对这些邻接点至多用k-2种颜色，即至少还有k-1种颜色中的一种未使用。在G中用这种颜色对v0着色，其他结点着色与G-v0相同，所以得到G的k-1正常着色，与(G)=k矛盾。,2 对于图G，(G)=k，则G中至少有k(k-1)/2条边。,