自考赵振坤离散附标准答案

1、5.1 习题参考答案1、设无向图 G有 16条边，有 3个 4度结点，4个 3度结点，其余结点的 度数均小于 3，问： G中至少有几个结点 .解：设度数小于 3 的结点有 x 个，则有34432x216解得： x4所以度数小于 3 的结点至少有 4 个 所以 G至少有 11 个结点 矚慫润厲钐瘗睞枥庑赖。2、设无向图 G有 9 个结点，每个结点的度数不是 5 就是 6，证明： G中至 少有 5 个 6 度结点或至少有 6 个 5 度结点 . 聞創沟燴鐺險爱氇谴净。答案：证明：由题意可知：度数为 5 的结点数只能是 0,2 ，4,6 ，8.若度数为 5 的结点数为 0,2 ，4 个，则度数为 6

2、 的结点数为 9，7,5 个结论 成立.若度数为 5 的结点数为 6,8 个，结论显然成立 .由上可知， G中至少有 5个 6度点或至少有 6个 5度点 . 残骛楼諍锩瀨濟溆塹籟。3、证明：简单图的最大度小于结点数认为题中应指定是无向简单图 .证明如下： 设简单图有 n 个结点， 某结点的度为最大度， 因为简单图任一结点没 有平行边， 而任一结点的的边必连有另一结点， 则其最多有 n-1 条边与其他结点 相连，因此其度数最多只有 n-1 条，小于结点数 n. 酽锕极額閉镇桧猪訣锥。4、设图 G有n个结点， n+1条边，证明： G中至少有一个结点度数 3 .给出证明如下：证明：设 G中所有结点的

3、度数都小于 3，即每个结点度数都小于等于 2，则所有 结点度数之和小于等于 2n，所以 G的边数必小于等于 n，这和已知 G有 n+1 条边 相矛盾. 所以结论成立 .彈贸摄尔霁毙攬砖卤庑。5、试证明下图中两个图不同构.证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系 我们可以看出， (a) 图和 (b) 图中都有一个三度结点， (a) 图中三度结点的某条边 关联着两个一度结点和一个二度结点，而 (b) 图中三度结点关联着两个二度结点 和一个一度结点，因此可断定二图不是同构的 . 謀荞抟箧飆鐸怼类蒋薔。6、画出所有 5 个结点 3 条边，以及 5 个结点 7 条边的简单图 .

4、 解：如下图所示： ( 与答案一致 )7、证明：下图中的图是同构的证明如下： 在两图中我们可以看到有 ae,b h,c f,d g两图中存在结点与边的一一对应关系，并保持关联关系8、证明：下面两图是同构的给出证明如下：证明：找出对应关系： a-q, br, cs, dt, eu,fv, gw, hx9、证明：三次正则图必有偶数个结点证明如下：由题意可知每个结点度数都是 3 度，即每个结点均为奇结点， 根据有偶数个奇结 点可知，三次正则图必有偶数个奇结点 . 厦礴恳蹒骈時盡继價骚。5.2 习题参考答案1、给定图 G，如下图所示，求出 G中从 A到 F 的所有初级路.解：从 A到 F的初级路有：A

5、BCF、 ABEF、ADEF、ABECF、ABCE、F ADEC、F ADEBCF茕 桢广鳓鯡选块网羈泪2、给定图 G，如下图所示，找到 G中从 v2 出发的所有初级回V1到 V2有一箭头 .从 V2 出发的初级回路有： V2V4V1V2、V2V3V4V1V2. 鹅娅尽損鹌惨歷茏鴛賴。3、设 G为无向连通图， 有 n 个结点， 那么 G中至少有几条边？为什么？对有向图如何？ 解：若 G为无向连通图，有 n 个结点，则 G中至少有 n-1 条边.因为在 n 个结点 的图中， 任取一个结点为起始点， 若要连通其他每个结点， 则其他每个结点至少 应有 1 度,此结点则有 n-1 度.因此总的度数至少

6、为 2n-2 度，而度数为边的 2 倍， 可算得边数为 n-1. 籟丛妈羥为贍偾蛏练淨。对于有向图，若是弱连通，则与无向图一样至少为 n-1, 若是单侧连通也是 如此，而强连通边数至少为 n.（ 此题根据的答案更正 ） 預頌圣鉉儐歲龈讶骅籴。4、设 V 和 E分别为无向连通图 G的点割集和边割集， G-E 的连通分支数 一定是多少？ G-V 的连通分支数也是定数吗 ? 渗釤呛俨匀谔鱉调硯錦。解：G-E的连通分支数一定是 2，而 G-V的连通分支数就不是定数了 .有可能大 于 2.5、设有七人 a,b,c,d,e,f,g, 已知： a 会讲英语， b 会讲汉语和英语， c 会 讲英语、意大利语和

7、俄语， d 会讲日语和汉语 ,e 会讲德语和意大利语， f 会讲法 语、日语和俄语， g 会讲法语和德语，试问这七人间可以任意交谈吗？ 铙誅卧泻噦 圣骋贶頂廡。答：可以. 设七个人为图中的 7 个结点，以他们之间有共同语言为条件画边， 可以看出， 七个人的结点在图中是连通的， 因此这七个人间可以通过相互翻译任 意交谈 . 擁締凤袜备訊顎轮烂蔷。6、一个有向图是强连通的， 当且仅当 G中有一个回路， 它至少包含每个结 点一次 .证明如下：必要性：如果图中的任何一个回路都不能包含所有结点 , 则可知未被包含在 回路内的结点不能与其他结点中的某一结点连通 . 这与本图是强连通的相矛盾 . 因此必有这

8、样一个路它至少包含每个结点一次 . 贓熱俣阃歲匱阊邺镓騷。充分性：当 G中有一个回路，它至少包含每个结点一次时，可以知道，任 一结点可达其他所有结点，因此它是强连通的 . 坛摶乡囂忏蒌鍥铃氈淚。7、若有简单图至多有 2n个结点，每个结点度数至少为 n，G是连通图 .又若简单图 G至多有 2n个结点，每个结点度数至少为 n-1 ，那么 G是连通 图吗？为什么？答：G不再是连通图，假若 n=1时，G中至多可有 2 个结点，而每个结点度 数至少可以为 0，显然这两个结点不能连通 . 蜡變黲癟報伥铉锚鈰赘。以下是的答案：方法一：设 v1、v2是这个简单图的任意两个结点，由已知可得， v1、v2 的度数

9、 至少为 n， 買鲷鴯譖昙膚遙闫撷凄。（1）若 v1、v2 之间有边，则显然 v1、v2 是连通的 .（2）若 v1、 v2 无边，则 v1 和剩下的结点中的 n 个结点有边相连， v2 也 和剩下的结点中的 n 个结点有边相连 . 因为剩下的结点最多只有 2n-2 个，由抽屉 原理可得，至少存在一个结点，它和 v1、v2 都有边相连，此时 v1和 v2 也是连 通的. 綾镝鯛駕櫬鹕踪韦辚糴。由（ 1）（ 2）可知，结论成立方法二：显然这个图中任意的一对结点的度数之和大于等于2n，所以这个图是汉密尔顿图，所以这个图是连通的 . 驅踬髏彦浃绥譎饴憂锦8、简单图 G有n个结点，e条边，设 e0.5

10、(n-1)(n-2), 证明：G是连通的.证明如下： n个结点的简单无向图，连通的最低条件是有 n-1 条边. 而 e0.5(n-1)(n-2)可得 en-1 ，因此 G是连通的 .上面的答案是错误的，纠正如下：因为一个连通图至少要有 n-1 条边，但 并不是说至少有 n-1 条边的图一定是连通图 . 并且容易验证这个结论不成立 .猫虿 驢绘燈鮒诛髅貺庑。证明如下：在图 G中，它的结点数为 n，设 v是 G中任一结点，若把 v去掉后，其 它 n-1 结点，每个结点度数最多有 n-1 度，因此 n-1 个结点之间最多只有 0.5 ( n-1)(n-2) 条边，而 e0.5(n-1)(n-2),

11、所以至少有一条边连接 v 和其它结点 . 锹籁饗迳琐筆襖鸥娅薔。下面我用数学归纳法进一步证明： ( 1)容易证明当 n=1,2 时，结论成立(2)假设当 n=k 时，结论成立，即若 e0.5 (k-1)(k-2) 时结论成立(3) 当 n=k+1时，若此时每个结点度数为 k，则结论显然成立，否则必存 在一个结点 v 度数至多只有 k-1 度，即这个结点最多只有 k-1 条边和它相连 . 因 为此时总的边数 e0.5k(k-1), 则其它 k 个结点之间的边数 e 0.5k(k-1)-(k-1)=0.5(k-1)(k-2). 根据归纳假设，显然这 k 个结点之间是连通 的，而根据上面我们知道，

12、至少有一条边使 v 和其它结点相连， 所以此时这个图 是连通的 . 構氽頑黉碩饨荠龈话骛。根据( 1)( 2)( 3)可知结论成立 .5.3 习题参考答案1、设图G=,V =v1,v2,v3,v4 的邻G)=0 1 0 11 0 1 11 1 0 01 0 0 0接矩阵则 v1 的入度 deg(v1) 是多少？ v4 的出度 deg(v4) 是多少？从 v1 到 v4 长度为 2 的路有几条？ 輒峄陽檉簖疖網儂號泶。解： 1、v1 的入度是 3. v4 的出度是 1， 因为2 0 1 12 2 0 1A2(G)=1 1 1 20 1 0 1所以从 v1到v4长度为 2的路有 1条.2、有向图

13、G如图所示， 求 G中长度为 4 的路径总数，并指出其中有多少条是回 路.v3 到 v4 的迹有几条 .答：长度为 4的路径总数为 15条，其中 3条是回路.从v3 到 v4的迹有 3 条.3、给定图 G如下图 求： a) 给出 G的邻接矩阵b) 求各结点的出、入度c) 求从结点 c 出发长度为 3 的所有回路 尧侧閆繭絳闕绚勵蜆贅。解:邻接矩阵如图： (按字母顺序 )M（G） 0 0 0 1 1a 的出度是 1 ，入度为 1b 的出度是 1，入度为 1c 的出度是 2，入度为 3d 的出度是 2，入度为 2e 的出度是 1，入度为 1 补充一下：出度就可以数该行的非零个数， 数入度则可数该列

14、的非零个从结点 c 出发长度为 3 的回路有： c-e-b-c , c-d-d-c4、给定 G 如图所示，a) 写出邻接矩阵b)G中长度为 4 的路有几条？ c)G 中有几条回路？识饒鎂錕缢灩筧嚌俨淒。解：(有疑问， v2、v3 间没有箭头，则此图有错，暂且理解为双向连通吧 )a）M（ G） 0 1 0 0 11 0 1 0 0b) 有 52 条c) 无数条( 看到这里，以为 v2、v3 间的箭头应向右更符合其本意， 因为图中有某种对应的 关系 .) 凍鈹鋨劳臘锴痫婦胫籴。5、试用矩阵法判断有向图G=a,b,c,d,|, 连通性 .答：不连通补充一下：原矩阵为：1 0 0 10 0 0 0 M

15、(G)=0 1 0 10 0 0 0由此矩阵得到的路径矩阵为：1 0 0 14 0 0 0 0 M4(G)= 0 1 0 10 0 0 0v2 到 v3 长度为 3可以发现图中些结点间没有路径存在 .6、求出下图所示图 G的邻接矩阵、可达矩阵，找出从的初级路，并计算出 A2,A 3进行验证 . 恥諤銪灭萦欢煬鞏鹜錦解：邻接矩阵为：0 0 1 1 M(G)=0 1 0 10 1 0 0其余答案略，用的话说就是： 太麻烦了，自己算一算吧 :)7、设图 G中的边满足 W(G-e)W(G),称为 e 为 G的割边(桥) . 证明： e 是割边，当且仅当 e 不包含在 G的任一回路中 . 鯊腎鑰诎褳鉀沩

16、懼統庫。证明： 必要性：设 e是 G某一连通分支的一条边 .假设 e 包含在 G 的某一回路中， 若把 e 去掉后，显然该连通分支仍是连 通的， 所以W(Ge)W(G).这和 e是 G的割边矛盾.充分性：设 e是连接 vi,vj 的一条边，假设 e不是割边.则把 e去掉后，该连通 分支仍是连通的vi 到 vj 必有路，不妨设此路为 vivj, 则必有 vivjevi, 这和 e 不包含在 G的任一回路中相矛盾，所以 e 是割边 . 硕癘鄴颃诌攆檸攜驤蔹。5.4 习题参考答案1、构造一个欧拉图，其结点数 v 和边数 e 满足下述条件：a) v 、e 的奇偶性一样；b) v,e 的奇偶性相反 .

17、阌擻輳嬪諫迁择楨秘騖。如果不可能，请说明原因都可以实现：如图：2、确定 n 取怎样的值，完全图 Kn 有一条欧拉回路 .答：n是奇数.因为完全图中， 每个结点度数均为 n-1 ，显然要有欧拉回路， n1必须是偶数，所以 n是奇数 .氬嚕躑竄贸恳彈瀘颔澩。3、a) 画一个有一条欧拉回路和一条汉密尔顿回路的图 .b) 画一个有一条欧拉回路但没有一条汉密尔顿回路的图 . 釷鹆資贏車贖孙滅獅赘。c) 画一个没有一条欧拉回路，但有一条汉密尔顿回路的图 .解：如下：4、如果图 G中中度数为奇数的结点个数为 0或 2，则G可一笔画出吗？说 明理由.答：不一定 . 若该图是连通的，则可以一笔画出，否则不可以

18、. 如下图5、若无向图 G 是欧拉图， G中是否存在割边？为什么？答：不存在，因为欧拉图中，存在一条回路，包含各边一次且仅一次，所 以任意去掉一条边，该图仍是连通的 .6、若一个有向图 G是欧拉图，它是否一定是强连通？若有一个有向图 G 是强连通的，它是否一定是欧拉图？说明理由 . 怂阐譜鯪迳導嘯畫長凉。答：（ 1）是，因为存在一条欧拉回路，所以任意两个结点都是可达的2）不是，如：7、下图所示的 G1和 G2是否是汉密尔顿图， 若是，请给出一条从 a 出发的答： (1) 是 .a-i-h-g-d-e-f-b-c-j-a(2) 不是. 因为我找不出这样的回路，若学友们找出的话请告诉我，谢谢 .

19、谚辞調担鈧谄动禪泻類。8、有割点的连通图是否能是汉密尔顿图？为什么？答：不能 . 根据定理 5.4.39、某次会议有 20 人参加，其中每人都至少有 10 个朋友，这 20人围一圆 桌入席，要想使每人相邻的两位都是朋友是否可能？根据什么？ 嘰觐詿缧铴嗫偽純铪 锩。答：可能 . 我们把每个人看成一个结点，若是朋友的用一条边连接 . 因此每 个结点的度数都大于等于 10，所以任意两个结点的度数之和都大于等于 20，因 此这个图中一定存在一条汉密尔顿回路，按这个回路排座位就可以了 . 熒绐譏钲鏌觶 鷹緇機库5.5 习题参考答案1、证明：小于 30 条边的简单平面图有一个结点度数小于等于 4.证明：

20、设结点数为 v ，边数为 e ( 1)若 v3r 24，所以 e12，这与已知有 12条边相矛盾 .濫驂膽閉驟羥闈詔寢賻。5.6 习题参考答案1、说明具有 6 个结点的非同构的无向树的数目是多少答：应是 6 个. 因为它是连通且无回路的无向树，因此在此树中只能有 5 条边.将这 5条边按不同方式连接 6个结点可得到 6种形态的无向树，大家不妨 画一画 . 銚銻縵哜鳗鸿锓謎諏涼。2、下面哪一种图不是树？ a)无回路的连通图 b)有 n个结点， n-1 条边的连通图；c) 每对结点间都有路的图； d) 连通但删去一条边则不连通的图 .答：c) 不是树. 每个结点都有路，则也包括回路，而树是无回路的

21、，因此 c) 不是树 .3、连通图 G是一棵树 ，当且仅当满足下述条件中哪一个？a) 有些边不是割边；b) 每条边都是割边； 挤貼綬电麥结鈺贖哓类。c) 无边割边；d) 每条边都不是割边；答：b) 是树，因为在树中，删去任一条边均使图变得不连通，则此边就是 割边.4、一个树有 2 个 4度结点， 3 个3 度结点，其余结点都是叶子，则叶子数 是多少？解：设叶子数为 n,则根据树的定义和图中总度数是边数的 2 倍，可列出方 程如下：24+33+n1=2(n+2+3 -1)解之得： n=95、画出结点数 n5的所有不同构的树解：如下图：6、设图 G是一棵树，它有 n2个2度分枝点， n3个3度分枝

22、点， .n k个k 度分枝点，求 G 中叶结点数 .解：同第 4 题的解法，设叶结点数为 n1，则有：n1+2n2+3n3+.kn k=2(n 1+n2+n3+.+n k-1)解之得： n1=n3+2n4+3n5+.+kn k+2+27、某城市拟在六个区之间架设有线电话网， 其网点间距离如下面有权图矩 阵给出，试给架设线路的最优方案，请画出图，并计算出线路的长度 . 赔荊紳谘侖驟 辽輩袜錈。A=|0 1 0 2 90 |104085|0403010|2 0 3076 |980700|0510600|要解本题，实际上是求该网点组成的图的最小生成树，呵呵，这对解：请看下图：线路的长度为学过数据结构

23、的同学来说是比较容易的： 1+2+3+5+7=18塤礙籟馐决穩賽釙冊庫。8 、求算式 (a+(b*c)*d)- e) (f+g)+(h*i)*j的树形表示 .解：如图所示：9、画出下图中的一棵最小生成树，并写出该生成树的关系矩阵答：注意，由于题图中所给权值位置不对， 将其作了 挪动 . 大家能明白吧 . 该生成树的关系矩阵如下：|0 1 1 1 0 0 |1 0 0 0 0 0 |M(A)=|1 0 0 0 1 0 |1 0 0 0 0 0 |0 0 1 0 0 1 |0 0 0 0 1 0 |10、设 T1和T2是连通图 G的两棵生成树， a是 T1中但不在 T2中的一条 边.证明存在边 b

24、，它在 T2中但不在 T1中，使得(T1-a) b 和(T2- b) a 都是 G的生成树 . 裊樣祕廬廂颤谚鍘羋蔺。以下是峰飞同学给出的证明： (感谢峰飞 )首先证明存在边 b，它在 T2 中但不在 T1中.设不存在边 b，它在 T2中但不在 T1中. 也就是说 T2中的所有边都 T1中. 因为存在边 a,它在 T1中但不在 T2中，所以有 T2是T1的真子集.T1 是树，且有 T1和 T2有同样的结点， T1 的所有真子集不可能是树，有 T2不是树，这与 T2 是树相矛盾 . 所以必存在边 b，它在 T2中但不在 T1中. 仓嫗盤紲嘱珑詁鍬齊驁。设边 b在T2中但不在 T1中，边 a在 T1中但不在 T2中 (T1-a)Ub(T1Ub)-a,T1Ub 后必存在唯一的环 . 设边 a 不在此环中， 那么有此环中的所有边都在 T2 中，也就是说 T2中存在环，这与 T2是树相矛盾， 也就是说， T1Ub 的环中有边 a，那么 T1Ub-a ，也是连通的并且没有环，也 是树，又因为有 G的所有结点，是 G的生成树 .则(T1-a)Ub 是 G的生成树.绽萬璉轆娛閬蛏鬮绾瀧。同理可证 (T2-b)Ua 是 G的生成树 .得证：存在边 b，它在 T2中但不在 T1中，使得( T1-a) b 和 (T2- b) a 都是 G的生成树