自考_赵振坤_离散第五章答案

《自考_赵振坤_离散第五章答案》由会员分享，可在线阅读，更多相关《自考_赵振坤_离散第五章答案（22页珍藏版）》请在金锄头文库上搜索。

1、5.15.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 的结点数为 9，7,5

2、 个结论成立。若度数为 5 的结点数为 6,8 个，结论显然成立。由上可知，G 中至少有 5 个 6 度点或至少有 6 个 5 度点。 3、证明：简单图的最大度小于结点数。 认为题中应指定是无向简单图. 证明如下：设简单图有 n 个结点，某结点的度为最大度，因为简单图任一结点 没有平行边，而任一结点的的边必连有另一结点，则其最多有 n-1 条边与其他 结点相连，因此其度数最多只有 n-1 条，小于结点数 n.4、设图 G 有 n 个结点，n+1 条边，证明：G 中至少有一个结点度数3 。 给出证明如下： 证明：设 G 中所有结点的度数都小于 3，即每个结点度数都小于等于 2，则所有 结点度数之

3、和小于等于 2n，所以 G 的边数必小于等于 n，这和已知 G 有 n+1 条 边相矛盾。所以结论成立。 5、试证明下图中两个图不同构。 证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。 我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边 关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点 和一个一度结点，因此可断定二图不是同构的。6、画出所有 5 个结点 3 条边，以及 5 个结点 7 条边的简单图。 解：如下图所示： (与答案一致) 7、证明：下图中的图是同构的。 证明如下：在两图中我们可以看到有ae,bh,cf,dg

4、两图中存在结点与边的一一对应关系，并保持关联关系。8、证明：下面两图是同构的。 给出证明如下： 证明：找出对应关系：a-q, b-r, c-s, d-t, e-u, f-v, g-w, h-x 9、证明：三次正则图必有偶数个结点。 证明如下：由题意可知每个结点度数都是 3 度，即每个结点均为奇结点，根据有偶数个奇结点可知，三次正则图必有偶数个奇结点。 5.25.2 习题参考答案习题参考答案 1、给定图 G，如下图所示，求出 G 中从 A 到 F 的所有初级路。 解：从 A 到 F 的初级路有：ABCF、ABEF、ADEF、ABECF、ABCEF、ADECF、ADEBCF 2、给定图 G，如下图

5、所示，找到 G 中从 v2 出发的所有初级回路。 认为图中少了一个箭头：从 V1 到 V2 有一箭头。从 V2 出发的初级回路有：V2V4V1V2、V2V3V4V1V2. 3、设 G 为无向连通图，有 n 个结点，那么 G 中至少有几条边？为什么？对有向图如何？ 解：若 G 为无向连通图，有 n 个结点，则 G 中至少有 n-1 条边。因为在 n 个结 点的图中，任取一个结点为起始点，若要连通其他每个结点，则其他每个结点 至少应有 1 度,此结点则有 n-1 度。因此总的度数至少为 2n-2 度，而度数为边 的 2 倍，可算得边数为 n-1. 对于有向图，若是弱连通，则与无向图一样至少为 n-

6、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 会讲英语、意大利语和俄语，d 会讲日语和汉语,e 会讲德语和意大利语，f 会讲法语、日语和俄语，g 会讲法语和德语，试问这七人间可以任意交谈吗？ 答：可以。设七个人为图中的 7 个结点，以他们之间有共同语言为条件画边，可以看出，七个人的

7、结点在图中是连通的，因此这七个人间可以通过相互翻译任意交谈。6、一个有向图是强连通的，当且仅当 G 中有一个回路，它至少包含每个结点一次。 证明如下：必要性：如果图中的任何一个回路都不能包含所有结点,则可知未被包含在回路内的结点不能与其他结点中的某一结点连通。这与本图是强连通的相矛盾。因此必有这样一个路它至少包含每个结点一次。充分性：当 G 中有一个回路，它至少包含每个结点一次时，可以知道，任一结点可达其他所有结点，因此它是强连通的。7、若有简单图至多有 2n 个结点，每个结点度数至少为 n，G 是连通图。 又若简单图 G 至多有 2n 个结点，每个结点度数至少为 n-1，那么 G 是连通图吗

8、？为什么？ 答：G 不再是连通图，假若 n=1 时，G 中至多可有 2 个结点，而每个结点度数至少可以为 0，显然这两个结点不能连通。以下是的答案：方法一：设 v1、v2 是这个简单图的任意两个结点，由已知可得，v1、v2 的度数至少为 n， （1）若 v1、v2 之间有边，则显然 v1、v2 是连通的。 （2）若 v1、v2 无边，则 v1 和剩下的结点中的 n 个结点有边相连，v2 也和剩下的结点中的 n 个结点有边相连。因为剩下的结点最多只有 2n-2 个，由抽屉原理可得，至少存在一个结点，它和 v1、v2 都有边相连，此时 v1 和 v2 也是连通的。 由（1）（2）可知，结论成立 方

9、法二：显然这个图中任意的一对结点的度数之和大于等于 2n，所以这个图是汉密尔顿图，所以这个图是连通的。8、简单图 G 有 n 个结点，e 条边，设 e0.5(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 结点，每个结点

10、度数最多有 n-1 度，因此 n-1 个结点之间最多只有0.5（n-1)(n-2)条边，而 e0.5(n-1)(n-2),所以至少有一条边连接 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 个结点之间的边数 e0.5k(k-1)-(k-1)=0.5(k-1)

11、(k-2)。根据归纳假设，显然这 k 个结点之间是连通的，而根据上面我们知道，至少有一条边使 v 和其它结点相连，所以此时这个图是连通的。根据（1）（2）（3）可知结论成立。 5.35.3 习题参考答案习题参考答案1、设图 G=,V=v1,v2,v3,v4的邻接矩阵 则 v1 的入度 deg(v1)是多少？ v4 的出度 deg(v4)是多少？ 从 v1 到 v4 长度为 2 的路有几条？ 解：1、v1 的入度是 3.v4 的出度是 1，因为A2(G)= 2 0 1 1 2 2 0 1 1 1 1 20 1 0 1所以从 v1 到 v4 长度为 2 的路有 1 条。 2、有向图 G 如图所示，

12、求 G 中长度为 4 的路径总数，并指出其中有多少条是回路。v3 到 v4 的迹有几条。 答：长度为 4 的路径总数为 15 条，其中 3 条是回路。从 v3 到 v4 的迹有 3 条。 3、给定图 G 如下图 求： a)给出 G 的邻接矩阵 b) 求各结点的出、入度 c) 求从结点 c 出发长度为 3 的所有回路 A(G)= 0 1 0 1 1 0 1 1 1 1 0 0 1 0 0 0解:邻接矩阵如图：(按字母顺序)M（G）0 0 1 0 0 1 0 1 0 0 0 0 0 1 10 0 1 1 0 0 1 0 0 0 a 的出度是 1，入度为 1b 的出度是 1，入度为 1c 的出度是

13、2，入度为 3d 的出度是 2，入度为 2e 的出度是 1，入度为 1补充一下：出度就可以数该行的非零个数，入度则可数该列的非零个数从结点 c 出发长度为 3 的回路有：c-e-b-c , c-d-d-c4、给定 G 如图所示， a)写出邻接矩阵 b)G 中长度为 4 的路有几条？ c)G 中有几条回路？ 解：(有疑问，v2、v3 间没有箭头，则此图有错，暂且理解为双向连通吧)a)M（G）0 0 0 0 1 1 0 1 0 00 1 0 0 11 0 1 0 00 1 0 1 0b) 有 52 条c)无数条(看到这里，以为 v2、v3 间的箭头应向右更符合其本意，因为图中有某种对应的关系。)5

14、、试用矩阵法判断有向图。 G=,连通性。 答：不连通补充一下：原矩阵为：M(G)=1 0 0 1 0 0 0 00 1 0 10 0 0 0由此矩阵得到的路径矩阵为： M4(G)=1 0 0 1 0 0 0 00 1 0 10 0 0 0可以发现图中些结点间没有路径存在。6、求出下图所示图 G 的邻接矩阵、可达矩阵，找出从 v2 到 v3 长度为 3的初级路，并计算出 A2,A3进行验证。 解：邻接矩阵为：M(G)=0 1 0 10 0 1 1 0 1 0 10 1 0 0其余答案略，用的话说就是：“太麻烦了，自己算一算吧“:)7、设图 G 中的边满足 W(G-e)W(G),称为 e 为 G

15、的割边（桥）。 证明：e 是割边，当且仅当 e 不包含在 G 的任一回路中。 证明：必要性：设 e 是 G 某一连通分支的一条边。假设 e 包含在 G 的某一回路中，若把 e 去掉后，显然该连通分支仍是连通的， 所以 W（Ge）W（G）。这和 e 是 G 的割边矛盾。充分性：设 e 是连接 vi,vj 的一条边，假设 e 不是割边。则把 e 去掉后，该连通分支仍是连通的vi 到 vj 必有路，不妨设此路为 vi.vj,则必有 vi.vjevi,这和 e 不包含在 G 的任一回路中相矛盾，所以 e 是割边。5.45.4 习题参考答案习题参考答案1、构造一个欧拉图，其结点数 v 和边数 e 满足下

16、述条件： a) v、e 的奇偶性一样； b) v,e 的奇偶性相反。 如果不可能，请说明原因。 都可以实现：如图： 2、确定 n 取怎样的值，完全图 Kn 有一条欧拉回路。 答：n 是奇数。因为完全图中，每个结点度数均为 n-1，显然要有欧拉回路，n1 必须是偶数，所以 n 是奇数。3、a)画一个有一条欧拉回路和一条汉密尔顿回路的图。 b)画一个有一条欧拉回路但没有一条汉密尔顿回路的图。 c)画一个没有一条欧拉回路，但有一条汉密尔顿回路的图。 解：如下：4、如果图 G 中中度数为奇数的结点个数为 0 或 2，则 G 可一笔画出吗？说明理由。 答：不一定。若该图是连通的，则可以一笔画出，否则不可以。如下图5、若无向图 G 是欧拉图，G 中是否存在割边？为什么？ 答：不存在，因为欧拉图中，存在一条回路，包含各边一次且仅一次，所以任意去掉一条边，该图仍是连通的。 6、若一个有向图 G 是欧拉图，它是否一定是强连通？若有一个有向图 G是强连通的