图论部分。本课程形成性考核作业共4次。内容由**电大确定、统一布置。
本次形考作业是第二次作业。大家要认真及时地完成图论部分的形考作业。字迹工整。
抄写题目。解答题有解答过程。
第3章图的基本概念与性质。
1．计算出下图2.1的结点数与边数。并说明其满足握手定理．
图2.1 习题1的图。
2．试分别画出下列图2.2(a)、(b)、(c)的补图．
图2.2 习题2的图。
3．找出下图2.3中的路、通路与圈．
图2.3 习题3的图。
4．设g为无向图。|g|=9.且g每个结点的度数为5或6.试证明g中至少有5个6度结点或至少有6个5度结点．
5．设有向图d=如图2.4所示。
图2.4 习题5的图。
试问图中是否存在长度分别为3, 4, 5, 6的回路。如存在。试找出．
6．若无向图g有10条边。3度与4度结点均2个。其余结点的度数均小于3.
试问g中至少有几个结点？若无向图g中有6条边。3度与5度结点均有一个。
其余结点的度数均是2.试问g中有几个结点？
7．试求图2.5中有向图的强分图。单侧分图和弱分图．
图2.5 习题7的图。
8．试说明图2.6中g1和g2同构．
图2.6 习题8的图。
解；满足两图同构的必要条件。将两图结点分别标号。建立两图间的一个。
恰当的双射即可。
9．试求图2.7中的邻接矩阵与可达矩阵．
图2.7 习题9的图。
10．有n个结点的无向完全图的边数为。
11．图中度数为奇数的结点为偶数个．
12．已知图g的邻接矩阵为
则g有（ c ）．
a．5点。8边b．6点。7边
c．5点。7边d．6点。8边。
第4章几种特殊图。
1．试分别构造满足下列条件的无向欧拉图。
1）有偶数个结点。奇数条边．
2）有偶数个结点。偶数条边．
3）有奇数个结点。偶数条边．
4）有奇数个结点。奇数条边．
解：见课堂答疑。
2．分别构造满足下列条件的四个汉密尔顿图。
1）偶数个结点。奇数条边．
2）有偶数个结点。偶数条边．
3）有奇数个结点。偶数条边．
4）有奇数个结点。奇数条边．
解：见课堂答疑。
3．试画出一个没有一条欧拉回路。但有一条汉密尔顿回路的图．
解：见课堂答疑。
4．如图2.8是否为欧拉图？试说明理由．
图2.8 判断是否为欧拉图。
5．如图2.9是否为汉密尔顿图？试说明理由．
图2.9 判断是否为汉密尔顿图。
6．试分别说明图4.3（a）、（b）与（c）是否为平面图．
图2.10 判断是否为平面图。
7．试分别求出图2.11（a）、（b）与（c）的每个图的面的次数．
图2.11 求面的次数。
解：因图中面没有标号。见课堂答疑。
8．试利用韦尔奇·鲍威尔算法分别对图2.12（a）、（b）与（c）着色．
图2.12 图的着色。
解：见课堂答疑。
先画成标准的平面图。再着色。使相邻面不同色。且只能少于或等于四种颜色。）
9．若g是一个汉密尔顿图。则g一定是( c )．
a．欧拉图 b．平面图 c．连通图。
10．设g是有n个结点m条边的连通平面图。且有k个面。则k等于( a )．
a．m-n+2 b．n-m-2 c．n+m-2 d．m+n+2
11．无向连通图 g 是欧拉图的充分必要条件是。
应填：图中每个结点的度数都是偶度数。
12．设g是具有n个结点的简单图。若在g中每一对结点度数之和大于等于___则在g中存在一条汉密尔顿路．
应填：n-1（即书中p.123定理4.2.2）
13．现有一个具有个奇数度结点的图。若要使图中有一条欧拉回路。最少要向图中添加___条边．
第5章树及其应用。
1．试指出图2.13中那些是树。那些是森林。并说明理由．
图2.13 习题1的图。
2．试画出图2.14中的一个生成树。并说明其中的树枝、弦。以及对应生成树的补．
图2.14 习题2的图。
解：见课堂答疑。
3．试画出如图2.15的完全图k5 的所有不同构的生成树．
图2.15 习题3的图。
解：见课堂答疑。
4．试求出图2.16中的最小生成树及其权值．
图2.16 习题4的图。
解：见课堂答疑。w(t)=1+1+1+1+1+2=7
5．给定一组权值为1.2.2.3.6.7.9.12.是求出相应的一个最优树．
解：见课堂答疑。
6．无向树t有7片树叶， 3个3度结点，其余的都是4度结点。则t有（ ）个4度结点？
a．1b．2c．3d．4
7．无向树t有3个3度结点，2个4度结点，其余的都是树叶。则t有（ ）片树叶？
a．3b．7c．9d．11
8．无向树t有1个2度结点，3个3度结点，4个4度结点，1个5度结点，其余的都是树叶。则t有（ ）片树叶？
a．12b．14c．16 d．20
9．无向树t有9片树叶，5个3度结点，其余的都是4度结点。则t有几个4度结点？
a．0b．1c．2d．3
离散数学形成性考核作业 一
集合论部分。本课程形成性考核作业共4次，内容由 电大确定 统一布置。本次形考作业是第一次作业，大家要认真及时地完成集合论部分的形考作业，字迹工整，抄写题目，解答题有解答过程。第1章集合及其运算。1 用列举法表示 大于2而小于等于9的整数 集合 2 用描述法表示 小于5的非负整数集合 集合 3 写出集...
离散数学形成性考核作业6答案
1.下列公式成立的为 a.pq pq b.pq pq c.qp p d.p pq q 2.设命题公式g 则使公式g取真值为1的p，q，r赋值分别是 a.0,0,0 b.0,0,1 c.0,1,0 d.1,0,0 3.命题公式 pq q为 a.矛盾式。b.可满足式。c.重言式。d.合取范式。4.下列公...
离散数学形成性作业 一
一 单项选择题。1 若集合a 4 则下列表述正确的是 a ab a c ad a 2 设b 3,4,2 那么下列命题中错误的是 a bb 3,4 b c bd b 3 若集合a b 则 a b a，且bab b a，但ba c b a，但bad b a，且ba 4 设集合a 则p a a c 5 设...