离散数学形成性考核作业(二）图论部分本课程形成性考核作业共4次,内容由中央电大确定、统一布置。
本次形考作业是第二次作业,大家要认真及时地完成图论部分的形考作业，字迹工整,抄写题目，解答题有解答过程。
第3章 图的基本概念与性质1.计算出下图２．1的结点数与边数，并说明其满足握手定理.图２.１ 习题1的图满足握手定理。
边数为为，按逆时针给结点编号解：结点数为6212022323)deg()deg()deg()deg()deg()deg(6.,,,,,6654321654321⨯==+++++=+++++v v v v v v v v v v v v2.试分别画出下列图2．2(a )、(b )、(c )的补图.图2.2 习题2的图即可。
要画出补图的补图的方法。
此题只上面给出的是求已知图成的图就是它的补图。
个结点和新颜色的边构由，阶完全图原图添加边成阶图，用另一种颜色把是成的图就是它的补图。
个结点和新颜色的边构由，阶完全图原图添加边成阶图，用另一种颜色把是成的图就是它的补图。
个结点和新颜色的边构由，阶完全图原图添加边成阶图，用另一种颜色把是解：444)(555)(555)(455K c K b K a3.找出下图2.3中的路、通路与圈.图2.３ 习题3的图4114.][典型例题例：本题应对应书中注意在根据定义找出。
要先将结点标号，、基本回路（圈），就要找出所有的基本路径回路（圈）。
之间的基本路径、基本指出哪两个点基本回路（圈），并且此题应是求基本路径、路径，也就是通路。
解：书中定义的路就是P4.设G 为无向图，|G |=9，且G 每个结点的度数为5或6,试证明G 中至少有５个６度结点或至少有6个５度结点． 度的结点。
个度的结点或至少有个中至少有于是，。
时，当；时，当；时，当；时，因此，有下述情况：当必为奇数。
，是偶数。
再由握手定理即偶数，奇度数结点的个数应是度的结点。
由定理知，个度的结点，则有个，如果设有知解：设56652)9(74)9(56)9(38)9(1,45225)9(6)9(5)9(69),,(G x x x x x x x x x m x mx x x x x n m n G =-==-==-==-=-==⨯-+⨯--==5．设有向图D ＝<V ,E >如图2.4所示,图２.４ 习题5的图试问图中是否存在长度分别为3， 4， 5， ６的回路，如存在，试找出．.,,,,,,,,,,,6;,,,,,,,,,5;,,,,,,,4;,,,,,365436543122551122551122334455112233551122551〉〈〉〈〉〈〉〈〉〈〉〈〉〈〉〈〉〈〉〈〉〈〉〈〉〈〉〈〉〈〉〈〉〈〉〈v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v 的回路：长度为的回路：长度为的回路：长度为的回路：长度为的回路。
，，，给出一个长度为下面以边序列的形式各的回路。
，，，解：存在长度为6．若无向图G 有１０条边，３度与4度结点均2个，其余结点的度数均小于３,试问G 中至少有几个结点？若无向图Ｇ中有6条边，3度与５度结点均有一个，其余结点的度数均是2，试问Ｇ中有几个结点?)(4422426224131211)2(7743621022)43(2422)1(图是什么样的呢？个结点。
中共有由握手定理知，个结点，个，共有设其余结点有个结点。
中至少有由握手定理知，个结点，个，共有设其余结点有解：G x x x x x x x G x x x x x x x =+==⨯=+⨯+⨯+=++≥+≥≥⨯≥++⨯+=++7．试求图2.5中有向图的强分图,单侧分图和弱分图.图2.5 习题7的图弱分图就是原图。
单向分图为原图：导出的子图；，，，强分图为由结点集，，，，，针将结点编号解：从左上角开始逆时}5{},4{},3{}621{654321８.试说明图２．６中Ｇ１和G 2同构． G 2G 1图2.6 习题８的图解；满足两图同构的必要条件，将两图结点分别标号，建立两图间的一个恰当的双射即可。
9．试求图2．7中的邻接矩阵与可达矩阵.图2．7 习题9的图。
达矩阵也可以直接由图得到可。
法，采用布尔乘法和布尔加，解：P P A A A A A B A =⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=++++=⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=000000011101011011010111100000001000101100101001105432510.有n 个结点的无向完全图的边数为 .)1(21-n n 应添 11.图中度数为奇数的结点为 偶 数个．12.已知图G 的邻接矩阵为，则G 有( C ).Ａ.5点,8边 B ．6点，7边Ｃ.5点,7边 D ．６点,8边第4章 几种特殊图1．试分别构造满足下列条件的无向欧拉图（1）有偶数个结点，奇数条边.（2）有偶数个结点,偶数条边.（3)有奇数个结点,偶数条边．(4）有奇数个结点,奇数条边.解：见课堂答疑。
２.分别构造满足下列条件的四个汉密尔顿图（１)偶数个结点,奇数条边.(2）有偶数个结点，偶数条边．（3)有奇数个结点,偶数条边．(４）有奇数个结点，奇数条边．解：见课堂答疑。
3．试画出一个没有一条欧拉回路,但有一条汉密尔顿回路的图.解:见课堂答疑。
4.如图2.8是否为欧拉图?试说明理由．图2.８ 判断是否为欧拉图的度数不都是偶数。
件，图中结点不满足欧拉图的充要条解：不是欧拉图。
因为5．如图2.9是否为汉密尔顿图?试说明理由．图2.9 判断是否为汉密尔顿图.),(),(),(),(),(),(),(),(1133355566688844422277711v v v v v v v v v v v v v v v v v v v v v v v v v 下，为存在汉密尔顿路。
如解：是汉密尔顿图。
因6.试分别说明图4.3（a )、(ｂ)与(ｃ)是否为平面图．图2．1０ 判断是否为平面图不必陈述上面文字。
应的平面图画出即可，相、、是平面图，把、、指出：回答此问题时，只需注意的交叉点就没有了。
有到内部中间点下面，所联的三条边向正下方拉内部最上面结点及其关上方拉到外边，及其关联的两条边由正图中将内部最下面结点拉到外面即可。
的三边从左斜上方结点以及内部两点对应图中将左下结点、右上拉到外面即可。
结点间的边从左斜上方图中将左下结点和右上都是平面图。
、、解：)()()()()()(][)()()()()()(c b a c b a c b a c b a7.试分别求出图2.１1（a )、（ｂ）与（ｃ）的每个图的面的次数.图2.11 求面的次数解:因图中面没有标号，见课堂答疑。
８.试利用韦尔奇·鲍威尔算法分别对图2.１2（a )、(b ）与（ｃ)着色．图2．12 图的着色解：见课堂答疑。
(先画成标准的平面图,再着色,使相邻面不同色，且只能少于或等于四种颜色。
）9．若G 是一个汉密尔顿图，则G 一定是（ C ）.Ａ．欧拉图 B.平面图 C ．连通图10．设G 是有n 个结点m 条边的连通平面图，且有k 个面,则k 等于( Ａ ).A ．m －n +２ B.n -m -2 C.ｎ＋ｍ－２D ．m +n +22,2+-==+-n m k k m n 所以解：由欧拉公式得，1１．无向连通图 Ｇ 是欧拉图的充分必要条件是＿______＿_＿＿＿＿＿__＿．应填：图中每个结点的度数都是偶度数。
12.设Ｇ是具有ｎ个结点的简单图，若在G 中每一对结点度数之和大于等于______＿＿，则在G 中存在一条汉密尔顿路.应填:n-1（即书中Ｐ．123定理4.2.2)１3．现有一个具有k 个奇数度结点的图,若要使图中有一条欧拉回路,最少要向图中添加_____＿___条边． 条边。
路，最少要向图中添加要使图中有一条欧拉回为偶数，，故度数的结点必有偶数个解：我们知道图中奇数2k k第5章 树及其应用１.试指出图2.13中那些是树，那些是森林，并说明理由.图２．13 习题1的图是由两棵树组成的图。
是树，是森林，因为孤立结点树的定义。
连通且无回路的图符合是树，因为它们分别为、解：)()()()(b b c a2.试画出图2.1４中的一个生成树,并说明其中的树枝、弦，以及对应生成树的补.图2.１４ 习题2的图解:见课堂答疑。
3.试画出如图2.１5的完全图K 5 的所有不同构的生成树．图２．１5 习题３的图解:见课堂答疑。
），，，，），（，，，，），（，，，，别为（它们的顶点度数序列分。
不同构的生成树有三棵1122211123111145K4．试求出图2．1６中的最小生成树及其权值．图2.１6 习题４的图解:见课堂答疑。
W(T)＝1+1+1＋1+1＋2=75．给定一组权值为１,2，２，３，６,7，9，12，是求出相应的一个最优树. 解：见课堂答疑。
6．无向树T 有7片树叶, ３个3度结点,其余的都是4度结点，则Ｔ有（ )个4度结点?A.1 B ．2 Ｃ．３ D ．４11011222)1(2)10(43371)10()37(4171=-∴==-⨯=-⨯+⨯+⨯-=---n n n n n n n n T n T A 由握手定理知，个，的结点有，度数为片树叶的度数都是条边，共有个结点，有设。
解：应填7．无向树T 有３个３度结点,2个4度结点，其余的都是树叶,则T 有( ）片树叶？ Ａ．3 Ｂ.7 C ．9 D ．1１片树叶。
共有由握手定理知，个，，树叶有条边，树叶的度数都是共有个结点，有设。
解：应填9923142589)1(2)23(12433)23(11=--∴=+-+=-⨯=--⨯+⨯+⨯---n n n n n n n T n T C8.无向树Ｔ有1个２度结点，3个3度结点,４个４度结点,1个5度结点，其余的都是树叶，则T 有( )片树叶?A.12B.14 Ｃ.16 D ．２0片树叶。
共有由握手定理知，个，，树叶有条边，树叶的度数都是共有个结点，有设片树叶。
有解：应填16169252951692)1(2)9(115443312)9()1431(1116=-∴=+-+++=-⨯=-⨯+⨯+⨯+⨯+⨯-=-----n n n n n n n n T n T C9.无向树Ｔ有９片树叶,５个3度结点,其余的都是4度结点，则T 有几个4度结点？A ．0B ．１ C.２ Ｄ．３度结点。
个共有由握手定理知，个，度结点共有，条边，树叶的度数都是共有个结点，有设。
解：答案是4111415302)1(2)14(45391)14()59(411=-∴==-⨯=-⨯+⨯+⨯-=---n n n n n n n n T n T B。