PPT《图论习题》

2)证明: 一个图是自补图, 其对应的完全图的边数必是偶数;

3)是否有3个结点或者6个结点的自补图. 2)证明:如果一个图是自补图,设该图的边数为e,则该图的自补图的边数也为e,所以对应的完全图的边数是2e,为偶数. 3)解:3个结点或者6个结点的完全图的边数分别为3和15,是奇数;

所以不存在3个结点或者6个结点的自补图. 连通性 证明连通的两种方法: 直接证明/反证法.证明连通的直接证明方法:任取图中两点,寻找这两点间必定存在路.证明连通的反证法: 首先假设图不连通,则它具有多个连通分支,然后根据题目条件推出矛盾.推矛盾的过程,通常是将具有多个连通分支的图的边数放到最大的过程(放缩法),即使每个连通分支都是完全图,然后推出边仍然不满足条件. 1. n个结点的简单图G,n>

2且n奇数,G和G补图中度数为奇数的结点个数是否相等?请证明或给出反例.(西南交大2001考研) 解:一定相等.因为n>

2且n奇数,则对于奇数个结点的完全图,每个结点的度数必为偶数.若G中度数为奇数的结点个数是m,则G的补图中m个结点的度数为(偶数-奇数)=奇数. G中度数为偶数的结点,在G的补图中这些结点的度数仍为(偶数-偶数)=偶数.所以命题成立. 2. 设无向图G有n个结点,n?2.证明: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考研 证明方法:1)反证法(简捷)2)数学归纳法:对顶点数进行数学归纳 反证法:证明:假设G不是连通的,则G至少存在两个连通分支.设G有两个连通分支C1和C2,则G的最大可能的边数m=x(x-1)/2+(n-x)(n-x-1)/2,其中1?x?n-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-S中的有向边至少有k条,则称G是k边连通的.证明:非平凡有向图是强连通的充要条件为它是一边连通的./*中国科学院计算所1999考研 证明:/*必要性证明*/因为设G为强连通的,假设从S到V-S没有有向边,则S中的任一顶点u到V-S中的任一顶点v均没有有向道路,从而与G为强连通的相矛盾.所以从S到V-S至少有一条有向边,即G为一边连通的. /*充分性证明*/设G为一边连通的,对任意的u, v?V, 则{u}到V(G-u)至少有一条边,设为(u, u1),而{u, u1}到V-{u, u1}至少有一条有向边(u, u2)或(u1, u2).无论哪种情况都有从u到u2的有向道路,因为G中结点数有限,所以通过如上递归地求解,一定有从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,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),回路长度为奇数,所以不是二分图.