南京信息工程大学-2011-2012-图论复习题(中文)

1、精选优质文档-倾情为你奉上1、设G是一个哈密尔顿图，则G一定是( )。(1) 欧拉图 (2) 树 (3) 平面图 (4)连通图 答：(4)（考察图的定义）2、一个图的哈密尔顿路是一条通过图中( )的路。答：所有结点一次且恰好一次3、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示( )。答：以v为起点的边的条数， 以v为终点的边的条数4、设G是一棵树，则G 的生成树有( )棵。(1) 0(2) 1(3) 2(4) 不能确定答：15、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。答：, n-16、一棵无向树的顶点数n与边数m关系是()。答：m=n-17、一个

2、图的欧拉回路是一条通过图中( )的回路。答：所有边一次且恰好一次8、有n个结点的树，其结点度数之和是()。答：2n-2（结点度数的定义）9、n个结点的有向完全图边数是( )，每个结点的度数是( )。答：n(n-1),2n-210、一个无向图有生成树的充分必要条件是( )。答：它是连通图11、设G是一棵树，n,m分别表示顶点数和边数，则(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。答：（3）12、设T=V,E是一棵树，若|V|>1，则T中至少存在( )片树叶。答：213、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。答：1， 树

3、14、设G是有n个结点m条边的连通平面图，且有k个面，则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。答：（1）15、设T是一棵树，则T是一个连通且( )图。答：无简单回路16、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16答：（4）17、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12答：(4)18、设图G=<V，E>，V=a，b，c，d，e，E=<a,b>,<a,c>,&

4、lt;b,c>,<c,d>,<d,e>,则G是有向图还是无向图？答：有向图19、任一有向图中，度数为奇数的结点有()个。答：偶数20、具有6 个顶点，12条边的连通简单平面图中，每个面都是由()条边围成？(1) 2(2) 4(3) 3(4) 5答：（3）21、在有n个顶点的连通图中，其边数（ ）。(1) 最多有n-1条(2) 至少有n-1 条(3) 最多有n条 (4) 至少有n 条答：（2）22、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（ ）。(1) 5(2) 7 (3) 8 (4) 9答：（4）23、若一棵完全二元（叉）树有2n-1个顶

5、点，则它（ ）片树叶。(1) n(2) 2n (3) n-1 (4) 2答：（1）24、下列哪一种图不一定是树（ ）。(1) 无简单回路的连通图(2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图答：（3）25、连通图G是一棵树当且仅当G中（ ）。(1) 有些边是割边(2) 每条边都是割边(3) 所有边都不是割边 (4) 图中存在一条欧拉路径答：（2）26、证明在有n个结点的树中，其结点度数之和是2n-2。证明：设T=<V,E>是任一棵树，则|V|=n，且|E|=n-1。由欧拉握手定理，树中所有结点的度数之和等于2|E|.从而结

6、点度数之和是2n-2。27、任一图中度数为奇数的结点是偶数个。证明：设G=V,E是任一图。设|V|=n。由欧拉握手定理可得 deg(v)=2|E|可得，图中所有结点度数之和是偶数。显然所有偶数度结点的度数之和仍为偶数，从而所有奇数度结点的度数之和也是偶数。因此，图中度数为奇数的结点一定为偶数个。28、连通无向图G的任何边一定是G的某棵生成树的弦。这个断言对吗？若是对的请证明之，否则请举例说明。证明：不对。反例如下：若G 本身是一棵树时，则G的每一条边都不可能是G的任一棵生成树（实际上只有惟一一棵）的弦。29、设T=<V,E>是一棵树，若|V|>1，则T中至少存在两片树叶。证明

7、：（用反证法证明）设|V|=n。因为T=V,E是一棵树，所以|E|=n-1。由欧拉握手定理可得 deg(v)=2|E|=2n-2。假设T中最多只有1片树叶，则deg(v)2(n-1)+1>2n-2。得出矛盾。30、设无向图G=<V,E>，|E|=12。已知有6个3度顶点，其他顶点的度数均小于3。问G中至少有多少个顶点？解：设G中度数小于3的顶点有k个，由欧拉握手定理 24=知，度数小于3 的顶点度数之和为6。故当其余的顶点度数都为2时，G的顶点最少。即G中至少有9个顶点。30、设图G=<V,E>，|V|=n，|E|=m。k度顶点有nk个，且每个顶点或是k度顶点或是

8、k+1度顶点。证明：nk=(k+1)-2m。证明：由已知可知，G中k+1度顶点为n-nk个。再由欧拉握手定理可知 2m=knk+(k+1)(n-nk)=(k+1)n+-nk故nk=(k+1)-2m。31、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。解： 用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：树权C(T)=23+1+4+9+3+17=57即为总造价。1、图的同构2、图的连通 3、Hamilton图一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路。4、Euler 图通过图（无

9、向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。5、树图如果一个无向简单图G 满足以下相互等价的条件之一，那么G 是一棵树：§ G 是没有的。§ G 没有回路，但是在G内添加任意一条，就会形成一个回路。§ G 是连通的，但是如果去掉任意一条边，就不再连通。§ G 是连通的，并且3顶点的  不是G的。&#

10、167; G内的任意两个顶点能被唯一所连通。6、割边7、割点G的顶点v成为割点，如果E可以分为两个非空子集E1和E2，使得G【E1】和G【E2】恰好有公共顶点v，若G无环且非平凡，则V是G的割点当且仅当w(G-v)>w(G)8、关联矩阵关联矩阵即用一个矩阵来表示各个点和每条边之间是关系9、邻接矩阵10、连通度11、完全图完全图是每对顶点之间都恰连有一条边的简单图。n个端点的完全图有n个端点及n(n  1) / 2条边，以Kn表示。它是(k  1)-。所有完全图都是它本身的团。12、二部图二分图又称作二部图、两偶图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。13、简单图如果一个无向图没有环,且每两个顶点之间最多只有一条边