本课程形成性考核作业共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 =<V ,E >如图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同构．
同构．
G1
G2
图2.6 习题8的图
过氧化酶9．试求图2.7中的邻接矩阵与可达矩阵．
中的邻接矩阵与可达矩阵．
图2.7 习题9的图
10．有n个结点的无向完全图的边数为
个结点的无向完全图的边数为 ．11．图中度数为奇数的结点为
数个． ．图中度数为奇数的结点为 数个．
12．已知图G的邻接矩阵为
的邻接矩阵为
，
有（ ）．
则G有（
A．5点，8边B．6点，7边
C．5点，7边D．6点，8边
第4章几种特殊图1．试分别构造满足下列条件的无向欧拉图 ．试分别构造满足下列条件的无向欧拉图
（1）有偶数个结点，奇数条边．
）有偶数个结点，奇数条边．
）有偶数个结点，偶数条边．
（2）有偶数个结点，偶数条边．
）有奇数个结点，偶数条边．
（3）有奇数个结点，偶数条边．
上海财务管理进修学院）有奇数个结点，奇数条边．
（4）有奇数个结点，奇数条边．
2．分别构造满足下列条件的四个汉密尔顿图
．分别构造满足下列条件的四个汉密尔顿图
）偶数个结点，奇数条边．琼脂糖凝胶
（1）偶数个结点，奇数条边．
（2）有偶数个结点，偶数条边．
）有偶数个结点，偶数条边．
）
有奇数个结点，偶数条边．
gb2626一2006（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 图的着
中那些是树，那些是森林，并说明理由．
．试指出图2.13中那些是树，那些是森林，并说明理由．
图2.13 习题1的图
中的一个生成树，并说明其中的树枝、弦，以及对应生成树的补．
中的一个生成树，并说明其中的树枝、弦，以及对应生成树的补．
图2.14 习题2的图
的所有不同构的生成树．
的完全图K5 的所有不同构的生成树．
图2.15 习题3的图
中的最小生成树及其权值．
中的最小生成树及其权值．
图2.16 习题4的图
结点？
结点？
A．1 B．2 C．3 D．4 北京市朝阳区环保局
7．无向树T有3个3度结点,2个4度结点，其余的都是树叶，则T（
有（ ）片树叶？
）片树叶？
A．3 B．7 C．9 D．11
8．无向树T有1个2度结点,3个3度结点,4个4度结点,1个5度结点，其余的都是树叶，）片树叶？
有（ ）片树叶？
则T有（
A．12 B．14 C．16 D．20
9．无向树T有9片树叶,5个3度结点，其余的都是4度结点，则T有几个4度结点？
度结点？
A．0 B．1 C．2 D．3
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议