8．结点数v与边数e满足 e= v－1 关系的无向连通图就是树．
9．设图g是有6个结点的连通图，结点的总度数为18，则可从g中删去。
条边后使之变成树．
10．设正则5叉树的树叶数为17，则分支数为i = 4 ．
二、判断说明题（判断下列各题，并说明理由．）
1．如果图g是无向图，且其结点度数均为偶数，则图g存在一条欧拉回路．．
答：错误。应叙述为：“如果图g是无向连通图，且其结点度数均为偶数，则图g存在一条欧拉回路。”
2．如下图所示的图g存在一条欧拉回路．
答：错误。因为图中存在奇数度结点，所以不存在欧拉回路。
3．如下图所示的图g不是欧拉图而是汉密尔顿图．
答：正确。因为有4个结点的度数为奇数，所以不是欧拉图；而对于图中任意点集中的非空子集，都有v1。其中是从图中删除结点及其关联的边。
4．设g是一个有7个结点16条边的连通图，则g为平面图．
答：错误。若g是连通平面图，那么若，而16>3×7－6，所以不满足定理条件，叙述错误。
5．设g是一个连通平面图，且有6个结点11条边，则g有7个面．
答：正确。因为连通平面图满足欧拉公式。即：。由此题条件知6-11+7=2成立。
三、计算题。
1．设g=，v=，e=，试。
1) 给出g的图形表示2) 写出其邻接矩阵；
3) 求出每个结点的度数4) 画出其补图的图形．答：（1
2．图g=，其中v=，e=，对应边的权值依次为及5，试。
1）画出g的图形2）写出g的邻接矩阵；
3）求出g权最小的生成树及其权值．
b c解：（1
a。 64
e 5 d
3） b c
2 1a1
e d其权值为：7
3．已知带权图g如右图所示．
1) 求图g的最小生成树； (2)计算该生成树的权值．答：(1
2) 权值为18。
4．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．解65
权值为65。
四、证明题。
1．设g是一个n阶无向简单图，n是大于等于3的奇数．证明图g与它的补图中的奇数度顶点个数相等．
证明：设a为g中任意一个奇数度顶点，由定义，a仍为顶点，为区分起见，记为a’, 则deg(a)+deg(a’)=n-1, 而n为奇数，则a’必为奇数度顶点。由a的任意性，容易得知结论成立。
2．设连通图g有k个奇数度的结点，证明在图g中至少要添加条边才能使其成为欧拉图．
证明：由定理推论知：在任何图中，度数为奇数的结点必是偶数个，则k是偶数。
又由欧拉图的充要条件是图g中不含奇数度结点。因此，只要在每对奇数度结点间各加一条边，使图g的所有结点的度数变为偶数，成为欧拉图。故最少要加条边才能使其成为欧拉图。
离散数学作业答案
1 第7页第3题。1 解 逆命题 如果我去公园，则天不下雨 反命题 如果天下雨，则我不去公园 逆反命题 如果我不去公园，则天下雨了。2 解 此题注意 p仅当q翻译成 逆命题 如果你去，那么我逗留。反命题 如果我不逗留，那么你没去。逆反命题 如果你没去，那么我不逗留。3 解 逆命题 如果方程无整数解，...
离散数学作业答案
作业题与解答。第一章 19 2 4 6 21 1 2 3 解答 p p q 真值表如下 所以公式 p q q 为可满足式。解答 p q q p 真值表如下 所以公式 p q q p 为永真式。19 6 解答 p q q r p r 真值表如下 所以公式 p q q r p r 为永真式。21 1 解...
离散数学作业34答案
离散数学 课程。作业3 p64 3 某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人中有4人会打排球。求不会打球的人数。解 直接使用容斥原理。我们做如下设定 a 会打篮球的学生 b 会打排球的学生 c 会打网球的...