《图论复习题.doc》由会员分享，可在线阅读，更多相关《图论复习题.doc（11页珍藏版）》请在金锄头文库上搜索。
1、（二）图论复习题一、选择题1设图G，vV，则下列结论成立的是 ( C ) Adeg(v)=2E B deg(v)=E C PPT 23 D定理1 图G=（V，E）中，所有点的次之和为边数的两倍2设无向图G的邻接矩阵为则G的边数为( B ) A6 B5 C4 D33、 设完全图K有n个结点(n2)，m条边，当（ C）时，K中存在欧拉回路Am为奇数 Bn为偶数 Cn为奇数 Dm为偶数解释：K每个结点的度都为n1，所以若存在欧拉回路则n1必为偶数。n必为奇数。4欧拉回路是（ B ）A. 路径 B. 简单回路PPT 40 C. 既是基本回路也是简单回路 D.既非基本回路也非简单回路5哈密尔顿回路是（
2、C ）A. 路径 B. 简单回路 C. 既是基本回路也是简单回路 D.既非基本回路也非简单回路PPT 40：哈密尔顿回路要求走遍所有的点，即是基本回路的点不重复，也可以是简单回路的边不重复。6设G是简单有向图，可达矩阵描述两点之间是否有路相连P(G)刻划下列关系中的是（ C ）A、点与边 B、边与点 C、点与点 D、边与边7下列哪一种图不一定是树（C）。A.无简单回路的连通图 B. 有n个顶点n-1条边的连通图 C. 每对顶点间都有通路的图 D. 连通但删去一条边便不连通的图8在有n个结点的连通图中，其边数（B）A.最多有n-1条 B.至少有n-1条 C.最多有n条 D.至少有n条9下列图为树
3、的是（C）。A、 B、 C、 D、 10、下面的图7-22是（C）。A.完全图；B.平面图；C.哈密顿图；D. 欧拉图。二、填空题1无向完全图K6有 15 条边。6（6-1）/2=152设连通无向图G有k个奇顶点，要使G变成欧拉图，在G中至少要加 k/2 条边。解：任何图中的奇点的个数为偶数在每对奇点处多加一条边形成了多重边，G图就成了欧拉图。连通无向图G有k个奇顶点有k/2对奇顶点有多少对奇点就加多少条边3、n阶无向完全图Kn 的边数是()，每个结点的度数是(n-1)。证明：1个顶点的图有0条边2个顶点的图有1条边满足当3个顶点以上时 假如n=k-1 k=3时k-1个顶点的图有条边k个顶点的
4、图有条边k-1个顶点的图与k个顶点的图产生的边数为 而又k-1个顶点的图的边数加上这条边k-1恰好为当n=k时满足条件一个具有N个顶点的无向完全图的边数为4、n个结点的有向完全图边数是( n(n-1) )，每个结点的度数是( 2n-2 )。解：仿用握手定理假设把每个顶点看成一个人A点到B点相当于A主动向B伸手。每个点要与n-1个点握手。因为是有向的，所以A向B伸手和B向A伸手有区别。总共握手次数是n(n-1)所以总共边数是n(n-1)5、设有向图G = ，的邻接矩阵，则的入度= 3 ，的出度= 1 ，6、一棵无向树的顶点数为n，则其边数为 n-1 ，其结点度数之和是 2(n-1) 。所有的次之
5、和为边数的两倍7、一个无向图有生成树的充分必要条件是(此图为连通图)。8、设T=V,E是一棵树，若|V|1，则T中至少存在( 2 )片树叶。9、任何连通无向图G至少有( 1 )棵生成树，当且仅当G 是( 树 )，G的生成树只有一棵。10、设T是一棵树，则T是一个连通且(无圈)的图。11、设无向图G有18条边且每个顶点的度数都是3，则图G有( 12 )个顶点。解：18条边的次之和为，且每个顶点的度数都是3 顶点数为36/3=12。如图：12、任一有向图中，度数为奇数的结点有( 偶数 )个。PPT 2313、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（ 9 ）。如图：14、
6、设G是由5个顶点组成的完全图，则从G中删去（ 6 ）条边可以得到树。解： 5个顶点组成的完全图边数为又树有5个顶点树的边数应为4完全图应删除10-4=6条边可以得到树。010101001000001110000010015、已知图G是相邻矩阵为则G的边数为（ B ）。A.5； B.4； C.6三、计算题1设G=，V= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，试(1) 给出G的图形表示； (2) 写出其邻接矩阵；(3) 求出每个结点的度数； 解：(1) (2)(3)、每个结点的度数分别为V11、V22、
7、V34、V43、V522图G=，其中V= a, b, c, d, e，E= (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) ，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G的图形； （2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值解：(1) (2) (3)G图最小生成树的权值为2+1+1+3=8。四、问答题1、设无向图G=，|E|=12。已知有6个3度顶点，其他顶点的度数均小于3。问G中至少有多少个顶点？ 解：有6个3度顶点它们的度数之和为63=18.又所有点的度数之和为，度数均小于3的其
8、余顶点的度数之和为24-18=6.其余顶点的度数均为2时，G的顶点最少其余顶点有6/2=3个G中至少有6+3=9个顶点2、判断下列图是否为欧拉图？说明理由，存在是否哈密尔顿回路。 解：（1）、是欧拉图。理由：欧拉图判断条件：图中所有节度点均为偶数（2）、不存在哈密尔顿回路。理由：哈密顿图是基本回路（点不能重复）。哈密顿图遍历顶点。3、下列各组数中，哪些能构成无向图的度数列？哪些能构成无向简单图的度数列？（1）1，1，1，2，3 （2）2，2，2，2，2 （3）3，3，3，3 （4）1，2，3，4，5 （5）1，3，3，3 解：1、构成图的度数列的条件：度数（次）之和为偶数，并且奇点有偶数个。(
9、1)、(2)、(3)、(4)、(5)的度数（次）之和分别为8、10、12、15、10又奇点的个数分别为4、0、4、3、4(4)不符合。也不满足无向简单图。(1)，(2)，(3)，(5)都能构成无向图的度数列2、(5)虽然能构成无向图的度数列，但不能构成无向简单图的度数列。若G是无向简单图，设G中顶点为a、b、c、d且d(a)=1、d(b)=d(c)=d(d)=3显然，a只能与b、c、d其中一个顶点相邻，若设a与b相邻，则除b可以是3度顶点，c、d都不能是3度顶点，这是矛盾的。所以(5)中的度数列不能构成不是无向简单图。4、1 哥尼斯堡的居民能否通过建一座新桥来找一条可接受的路线？如果可以，该怎
10、么作？ 2 哥尼斯堡的居民能否通过建两座新桥来找一条可接受的路线？如果可以，该怎么作？ 3 哥尼斯堡的居民能否通过拆一座桥来找一条可接受的路线？如果可以，该怎么作？4 哥尼斯堡的居民能否通过拆两座桥来找一条可接受的路线？如果可以，该怎么作？解：七桥示意图的每个节点度为奇数它不是欧拉图，不能遍历边连通无向图G有n个奇点成为欧拉图的充要条件：在G中至少要添加或删掉n/2条边假设桥为图中的边，解答如下：（1）、（2）图中有4个奇点要使其变为欧拉回路，即可以在G中添加4/2=2条边（1）不满足条件，路线不被接受，（2）的建议则被接受（3）、（4） 图中有4个奇点要使其变为欧拉回路，即可以在G中删掉4/
11、2=2条边（3）不满足条件，路线不被接受，（4）的建议则被接受五画图 画出一个无向欧拉图，使它具有：（1）偶数个顶点，偶数条边；（2）奇数个顶点，奇数条边；（3）偶数个顶点，奇数条边；（4）奇数个顶点，偶数条边 画出一个有向欧拉图，要求：按数字顺序走遍所有的边，点可以重复。蓝点是起点。（1）偶数个顶点，偶数条边；（2）奇数个顶点，奇数条边；（3）偶数个顶点，奇数条边；（4）奇数个顶点，偶数条边。3. 根据如下的相邻矩阵，画出它所对应的图G。=010111101111010111111010111101111010)(GA4、已知无向图G有12条边，6个3度顶点，其余顶点的度数均小于3，问图G至
12、少有几个顶点？并画出符合条件的图形？解：无向图G的|E|=12图G的度数之和为又6个3度顶点这6个3度顶点的度数之和为63=18度数均小于3的其余顶点的度数之和为24-18=6当其余顶点的度数均为2时，图G的顶点最少其余顶点数为6/2=3图G至少有6+3=9个顶点。5、在有7个结点的无向图G中，2度、3度、4度、5度顶点的个数分别是1、3、2、1，求G的边数，试画出满足条件的图形？解：由题可知，7个顶点的度数之和为12+33+24+15=24所有次之和为边数的两倍G图的边数为24/2=12村民建房委员会应建立村级农房建设质量安全监督制度和巡查制度，选聘有责任心和具有一定施工技术常识的村民作为义务巡查监督员，开展经常性的巡查和督查。
