离散数学图论单元测验题
一、单项选择题(本大题共10小题,每小题2分,共20分) 1、在图G=<V,E>中,结点总度数与边数的关系是( ) (A) deg(vi)=2∣E∣ (B) deg(vi)=∣E∣ (C) (D)
2、设D是n个结点的无向简单完全图,则图D的边数为( )
(A) n(n-1) (B) n(n+1) (C) n(n-1)/2 (D) n(n+1)/2
3、 设G=<V,E>为无向简单图,∣V∣=n,∆(G)为G的最大度数,则有
(A) ∆(G)<n (B)∆(G)≤n (C) ∆(G)>n (D) ∆(G)≥n
4、图G与G'的结点和边分别存在一一对应关系,是G≌G'(同构)的( ) (A) 充分条件 (B) 必要条件 (C)充分必要条件 (D)既非充分也非必要条件
5、设,则与V能构成强连通图的边集合是( )
(A)
(B)
(C)
6、有向图的邻接矩阵中,行元素之和是对应结点的( ),列元素之和是对应结点的( )
(A)度数 (B) 出度 (C)最大度数 (D) 入度
7、设图G的邻接矩阵为
则G的边数为( ).
A.5 B.6 C.3 D.4
8、设为连通平面图且有r个面,则r=( )
(A) m-n+2 (B) n-m-2 (C) n+m-2 (D) m+n+2
9、在5个结点的二元完全树中,若有4条边,则有 ( )片树叶。
(A) 2 (B) 3 (C) 5 (D) 4 世界人体艺术鉴赏大典
10、图2是( )
(A) 完全图 (B)欧拉图 (C) 平面图 (D) 哈密顿图
二、填空题(本大题共10小题,每题2分,共20分)
1、设图G=<V,E脉冲变压器>和G'=<V',E'>,若 ,则G'是G的真子图,若 ,则G'是G的生成子图.
2、设G是完全二叉树,G有15个结点,其中有8个是树叶,则G有 条边,G的总度数是 ,G的分支点数是 ,G中度数为3的结点数是 .
3、一棵树有两个结点度数为2,一个结点度数为3,三个结点度数为4,问它有几个度数为1的结点。
4、画出满足下列条件的图:
(1) 画一个有一条欧拉回路和一条哈密顿回路的图;
(2) 画一个有一条欧拉回路,但没有哈密顿回路的图;
(3) 画一条没有欧拉路,但有一条哈密顿回路的图.
5、设G是n个结点的简单图,若G中每对结点的度数之和 ,则G一定是哈密顿图.
称为树叶.
7、设G是平面图,G有8个面,每个面的度数都是3,则G有__________条边,G有__________个顶点。
8、设G是有n个结点,m条边的连通图,要确定G的一棵生成树,必须删去G的 条边.
9、在下图中,哪些是欧拉图?哪些是哈密顿图?哪些是平面图?
(1)
(2)
10、设G是n阶无向带权边连通图,各边的权均为a(a>0),设T是G的一棵最小生成树,则T的权W(T)=________(n-1)*a_______________。
三、计算题(本大题共4小题,每小题10分,共40分)
1、设G=<V,E>是一个无向图,
(1) G=<V,E>的∣V∣,∣E∣各是多少? (2) 画出G的图示;
(3) 指出与v3邻接的结点,以及与v3关联的边; (4) 指出与e1关联的结点;
(5) 该图是否有孤立结点和孤立边? (6) 求出各结点的度数;
2、设图G是具有3个顶点的无向完全图,试问
(1) G有多少个子图? (2) G有多少个生成子图?
(3) 如果没有任何两个子图是同构的,则G的子图个数是多少?将它们构造出来.
3.图G=<V, E>,其中V={a, b, c, d, e, f任继愈 },E={(a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e), (d, f), (e, f)},对应边的权值依次为5,2,1,2,6,1,9,3及8.
(1)画出G的图形;
(2)写出G的邻接矩阵;
(3)求出G权最小的生成树及其权值.
4.设有一组权为2,3,5,7,11,13,17,19,23,29,31,试
(1)画出相应的最优二叉树;
(2)计算它们的权值.
四、证明题(本大题共3小题,任选2题,每小题于超颖10分,共20分)
1.若无向图G中只有两个奇数度结点,则这两个结点一定是连通的.
2.设G是一个n阶无向简单图,n是大于等于2的奇数.证明图G与它的补图中的奇数度顶点个数相等.
3.设连通图G有k个奇数度的结点,证明在图G中至少要添加条边才能使其成为欧拉图.
补充
1、若图G是不连通的,则G的补图G是连通的。
2、当且仅当G的一条边e不包含在G的回路中时,e才是G的割边。
3、设G是简单平面图,则它—定有一个度数≤5的结点。
解答:
密令截击一、单项选择题(本大题共10小题,每小题2分,共20分)
1、在图G=<V,E>中,结点总度数与边数的关系是( )
(A) deg(vi)=2∣E∣ (B) deg(vi)=∣E∣ (C) (D)
答案:(C)
2、设D是n个结点的无向简单完全图,则图D的边数为( )
(A) n(n-1) (B) n(n+1) (C) n(n-1)/2 (D) n(n+1)/2
答案: (C)
3、 设G=<V,E>为无向简单图,∣V∣=n,∆(G)为G的最大度数,则有
(A) ∆(G)<n (B)∆(G)≤n (C) ∆(G)>n (D) ∆(G)≥n
答案:(A)
解答:因为G中无平行边和环,任何结点最多有n-1条边与其相关联,最大度数小于或等于n-1. 故选择(A)
4、图G与G'的结点和边分别存在一一对应关系,是G≌G'(同构)的( )
(A) 充分条件 (B) 必要条件 (C)充分必要条件 (D)既非充分也非必要条件
答案:(B)
解答:见图的同构定义.
5、设,则与V能构成强连通图的边集合是( )
(D)
(E)
(F)
(G)
答案:(A)
解答:有向图G任何一对结点间都互相可达,称该图是强连通的. (A)所给的边的集合存在一个通过所有结点的通路. 故选择(A).
6、有向图的邻接矩阵中,行元素之和是对应结点的( ),列元素之和是对应结点的( )
(A)度数 (B) 出度 (C)最大度数 (D) 入度
答案:(B),(D)
解答:见邻接矩阵的定义.
7、设图G的邻接矩阵为
则G的边数为( ).
A.5 B.6 C.3 D.4
答案:(D)
8、设为连通平面图且有r个面,则r=( )