一、 图的概念、连通性与矩阵表示。
选择/填空题。
1、任何n个节点m条边的图g = v,e) ,边数与顶点度数的关系是。
2、任一有向图中，度数为奇数的结点有()个。
3、n阶完全图kn的边数为。
4、n个结点的有向完全图边数是( )每个结点的度数是( )
5、已知图g中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则g的边数是．
6、下面四组数能构成无向图的度数列的有( )
a、 2,3,4,5,6,7； b、 1,2,2,3,4；
c、 2,1,1,1,2d、 3,3,5,6,0。
7、设无向图g有16条边且每个顶点的度数都是2，则图g有( )个顶点。
8、在有n个顶点的连通图中，其边数（ ）
1) 最多有n-1条(2) 至少有n-1 条。
3) 最多有n条 (4) 至少有n 条。
9、如右图相对于完全图k5的补图为（）。
10、给定无向图g如下图所示，下面给出的结点集子集中，不是点割集的为（）．a． c．
11、图g如右图所示，以下说法正确的是 (
a．是割边。
b．是边割集。
c．是边割集。
d．是边割集。
12、给定无向图g=如下图所示，下面哪个边集不是其边割集（）。
a、；b、;
c、；d、。
13、设有向图（a）、（b）、（c）与（d）如下图所示，则下列结论成立的是( )
a．（a）是强连通的 b．（b）是强连通的。
c．（c）是强连通的 d．（d）是强连通的。
14、下图的邻接矩阵a=
15、设无向图g的邻接矩阵为，则g的边数为( )
a．5b．6c．3d．4
16、图的邻接矩阵为。
a、；b、；c、；d、。
综合题。17、设g=，v=，e=，试。
1) 给出g的图形表示2) 写出其邻接矩阵；
3) 求出每个结点的度数4) 画出其补图的图形．
18、已知：d=，v=，e=，求d的邻接距阵a和可达距阵p。
19、无向图g有12条边，g中有6个3度结点，其余结点的度数均小于3，问g中至少有多少个结点？
20、 有向图如右图所示。
1）求的邻接矩阵；
2）中到长度为4的路径有几条？
3）中到自身长度为3的回路有几条？
4）是哪类连通图？
21、设图如图1所示，1) 求的邻接矩阵；
2) 求，说明从到的长为的路径各有几条；
3) 求的可达矩阵；
4) 求的强连通分图。
22、设有如下有向图g=，1）求g的邻接矩阵；
2）g中v1到v4的长度为4 的通路有多少条？
3）g中经过v1的长度为3 的回路有多少条？
4）g中长度不超过4 的通路有多少条？其中有多少条通路？
二、 二部图、欧拉图、哈密顿图。
选择/填空题。
23、无向图g存在欧拉通路，当且仅当( )
a．g中所有结点的度数全为偶数。
b．g中至多有两个奇数度结点。
c．g连通且所有结点的度数全为偶数。
d．g连通且至多有两个奇数度结点。
24、无向图g是欧拉图，当且仅当( )
a) g的所有结点的度数都是偶数 (b)g的所有结点的度数都是奇数。
c)g连通且所有结点的度数都是偶数 (d) g连通且g的所有结点度数都是奇数。
25、当n为时，非平凡无向完全图kn是欧拉图。
26、下列图中是欧拉图的有。
27、下图中既不是eular图，也不是hamilton图的图是（）
28、在如下各图中（）是欧拉图。
综合题。29、若一个有向图是欧拉图，它是否一定是强连通的？若一个有向图是强连通的，它是否一定是欧拉图？说明理由。
30、一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人？
根据是什么？
三、 树及应用。
选择/填空题。
31、设g是有n个结点，m条边的连通图，必须删去g的( )条边，才能确定g的一棵生成树．
a． b． c． d．
32、已知一棵无向树t中有8个结点，4度，3度，2度的分支点各一个，t的树叶数为（）．
a．8b．5c．4d．3
33、连通无向图g有6个顶点9条边，从g中删去条边才有可能得到g的一棵生成树t．
34、已知一棵无向树t有三个3顶点，一个2度顶点，其余的都是1度顶点，则t中有个1度顶点。
35、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（ ）
36、一棵无向树的顶点数n与边数m关系是。
37、有n个结点的树，其结点度数之和是。
38、设g是一棵树，n,m分别表示顶点数和边数，则（ ）
1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。
39、任何连通无向图g至少有棵生成树。
40、下面给出的集合中，哪一个不是前缀码( )
41、下面给出的集合中，哪一个是前缀码？()
综合题。42、图g=，其中v=，e=，对应边的权值依次为5，2，1，2，6，1，9，3及8．
1) 画出g的图形2) 写出g的邻接矩阵；
3) 求出g权最小的生成树及其权值．
43、已知带权图g如右图所示．
1) 求图g的最小生成树； (2)计算该生成树的权值．
44、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。
45、设带权无向图g如下，求g的最小生成树t及t的权总和，要求写出解的过程。
46、求叶的权分别为的最优二叉树及其权。
47、在通讯中，八进制数字出现的频率如下：
求传输它们最佳前缀码（写出求解过程）。
离散数学第二次作业
参考试题02 0001 试卷总分 100 测试时间 0 单项选择题。一 单项选择题 共10道试题，共100分。1.设a r是a上的整除关系，b 则集合b的最大元 最小元 上界 下界依次为 a b c d.无 2 无 2 设集合a 上的函数分别为 f g h 则h a.fgb.gf c.ffd.gg ...
考试离散数学第二次作业
2013年4月考试离散数学第二次作业。一 单项选择题 本大题共50分，共 25 小题，每小题 2 分 1.下列语句中为命题的是 a.暮春三月，江南草长。b.这是多么可爱的风景啊！c.大家想做什么，就做什么，行吗？d.请勿践踏草地！2.2.设g是n个顶点的无向简单图，则下列说法不正确的是 a.若g是树...
离散第二次作业
一 填空题。1.对于任意集合a,若 a n,则a的幂集合p a 有 2n.个元素。2.整数集合z上的小于关系 具有 反自反 反对称 传递。3.联结词集合 是 功能完备的。4.设q是有理数集合，q关于数的乘法运算 能构成 独异点 5.设 是非空集合l上的偏序，若l中的任意两个元素均存在 上确界和下确界...