2023年电大离散数学作业答案图论部分 .docxVIP

姓名：

离散数学作业5学号：

离散数学图论部分形成性考核书面作业

本课程形成性考核书面作业共3次，内容重要分别是集合论部分、图论部分、数理逻辑部分日勺综合练习，基本上是按照考试日勺题型（除单项选择题外）安排练习题目，目日勺是通过综合性书面作业，使同学自己检查学习成果，找出掌握日勺微弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完毕图论部分日勺综合练习作业。

规定:将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，规定2010年12月5日前完毕并上交任课教师（不收电子稿）。并在05任务界面下方点击“保留”和“交卷”按钮，以便教师评分。

一、填空题

.已知图G中有1个1度结点，2个2度结点,3个3度结

TOC\o1-5\h\z点,4个4度结点，则G日勺边数是 15.八

.设给定图G（如右由图所示），则图G日勺点割集是 /\ :

{f}. 百

.设G是一种图，结点集合为匕边集合为E，则

G日勺结点度数之和等于边数日勺两倍.

.无向图G存在欧拉回路，当且仅当G连通且等于出

度.

.设G=＜匕E＞是具有n个结点日勺简朴图，若在G中每一对结点度数之和不小于等于 n—1 ，则在G中存在一条汉密尔顿路.

.若图G=＜V,E＞中具有一条汉密尔顿回路，则对于结点集V日勺每个非空子集S,在G中删除S中日勺所有结点得到日勺连通分支数为W,则S中结点数⑻与W满足日勺关系式为W(G-V1)41Vli.

.设完全图Kn有n个结点(n＞2),m条边，当 n为奇数 时,Kn中

存在欧拉回路．

.结点数v与边数e满足 e=v-1关系日勺无向连通图就

是树.

.设图G是有6个结点日勺连通图，结点日勺总度数为18,则可从G中删去

4条边后使之变成树.

10.设正则5叉树日勺树叶数为17,则分支数为i= 5 .

二、判断阐明题(判断下列各题,并阐明理由.)

.假如图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路..

(1)不对日勺，缺了一种条件，图G应当是连通图，可以找出一种反例，例如图G是一种有孤立结点日勺图。

.如下图所示日勺图G存在一条欧拉回路.

2) 不对日勺，图中有奇数度结点，因此不存在是欧拉回路。

.如下图所示日勺图G不是欧拉图而是汉密尔顿图.

a

e °g

图G

解：对日勺

由于图中结点a,b,d,f日勺度数都为奇数，因此不是欧拉图。

假如我们沿着(a,dgfeb,c,a),这样除起点和终点是a外，我们通过每个点一

次仅一次，因此存在一条汉密尔顿回路,是汉密尔顿图

.设G是一种有7个结点16条边日勺连通图，则G为平面图.

解：(1)错误

假设图G是连通日勺平面图，根据定理,结点数v,边数为e，应满足e不不小于等于3V—6,但目前16不不小于等于3*7—6,显示不成立。因此假设错误。

5.设G是一种连通平面图，且有6个结点11条边，则G有7个面.

(2)对日勺

根据欧拉定理，有v-e+r=2,边数v=ll,结点数。=6,代入公式求出面数r

=7

三、计算题

1.设

1.设G=V,E,V={v1,v2,v3,V

V5),E={(V1,v3),(v2,v3),(v2

v4)，(V

3

3,v4)，(v3,V5)，(v4，v5) },试

(1)给出

(1)给出G日勺图形表达;

(2)写出其邻接矩阵；

(3

(3)求出每个结点日勺度数;

(4)画出其补图日勺图形.

解：

解：(1)

(2)邻接矩阵为f(2)

邻接矩阵为

f0

0

1

0

10

0

0

1

1

0

1

1

0

1

1

0

1

1

0

1

0]

0

1

1

0J

(3)

v1结点度数为1

结点度数为2,匕结点度数为3,v4结点度数为2,

v5结点度数

为2

为2

(4)补图图形为

2.图G=匕E,其中V={a,0,c,d,e},E={

2.图G=匕E,其中V={a,0,c,

d,

e},E={(a,b), (a,c),

(a,e),(b,d),Qb,e),(c,e), (c,d),(d,e)}，对应边日勺权值依次为2、

1、2、3、6、1、4及5,试

(1)画出G日勺图形；

(3)求出G权最小日勺生成树及其权值.

(2)写出G日勺邻接矩阵;

(1)G日勺图形如下：

(2)写出G日勺邻接矩阵

TOC\o1-5\h\z厂口 2 1 0 2

\oCurrentDocument2 0 0 3 6

10 0 4 2

0 3 4 0 6

\oCurrentDocument2 6 2 5 0