离散数学课后答案五

1、5.1 习题参考答案 1、阮允准同学提供答案:解：设度数小于 3 的结点有 x 个，则有34432x216解得：x4所以度数小于 3 的结点至少有 4 个所以 G 至少有 11 个结点 2、阮允准同学答案：证明：由题意可知：度数为 5 的结点数只能是 0,2，4,6，8。若度数为 5 的结点数为 0,2，4 个，则度数为 6 的结点数为 9，7,5 个结论成立。若度数为 5 的结点数为 6,8 个，结论显然成立。由上可知，G 中至少有 5 个 6 度点或至少有 6 个 5 度点。 3、晓津证明如下：设简单图有 n 个结点，某结点的度为最大度，因为简单图任一结点没有平行边，而任一结点的的边必连有另一结点，则其最多有 n-1 条边与其他结点相连，因此其度数最多只有 n-1 条，小于结点数 n.4 阮同学给出证明如下：证明：设 G 中所有结点的度数都小于 3，即每个结点度数都小于等于 2，则所有结点度数之和小于等于 2n，所以 G 的边数必小于等于 n，这和已知 G 有 n+1 条边相矛盾。所以结论成立。 5、试证明下图中两个图不同构。 晓津证明：同构的充要条件是两图的结点和边分别存在一一对

2、应且保持关联关系。我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定二图不是同构的。6、画出所有 5 个结点 3 条边，以及 5 个结点 7 条边的简单图。 解：如下图所示： (晓津与阮同学答案一致 ) 7、证明：下图中的图是同构的。 证明如下：在两图中我们可以看到有ae,bh,cf,dg 两图中存在结点与边的一一对应关系，并保持关联关系。8、证明：下面两图是同构的。 阮同学给出证明如下： 证明：找出对应关系：a-q, b-r, c-s, d-t, e-u, f-v, g-w, h-x 9、证明：三次正则图必有偶数个结点。 阮同学证明如下：由题意可知每个结点度数都是 3 度，即每个结点均为奇结点，根据有偶数个奇结点可知，三次正则图必有偶数个奇结点。 5.2 习题参考答案 1、解：从 A 到 F 的初级路有：ABCF、ABEF、ADEF、ABECF、ABCEF、ADECF、ADEBCF 2、晓津认为图中少了一个箭头：从 V1 到 V2 有一箭头。从 V2 出发的初

3、级回路有：V2V4V1V2、V2V3V4V1V2. 3、 解：若 G 为无向连通图，有 n 个结点，则 G 中至少有 n-1 条边。因为在 n 个结点的图中，任取一个结点为起始点，若要连通其他每个结点，则其他每个结点至少应有 1 度,此结点则有 n-1 度。因此总的度数至少为 2n-2 度，而度数为边的 2 倍，可算得边数为 n-1. 对于有向图，若是弱连通，则与无向图一样至少为 n-1,若是单侧连通也是如此，而强连通边数至少为 n。(此题根据阮允准同学的答案更正)4、 解： G-E的连通分支数一定是 2，而 G-V的连通分支数就不是定数了。有可能大于 2.5、答：可以。设七个人为图中的 7 个结点，以他们之间有共同语言为条件画边，可以看出，七个人的结点在图中是连通的，因此这七个人间可以通过相互翻译任意交谈。6、证明如下：必要性：如果图中的任何一个回路都不能包含所有结点,则可知未被包含在回路内的结点不能与其他结点中的某一结点连通。这与本图是强连通的相矛盾。因此必有这样一个路它至少包含每个结点一次。充分性：当 G 中有一个回路，它至少包含每个结点一次时，可以知道，任一结点可达其他所有结点

4、，因此它是强连通的。7、若有简单图至多有 2n 个结点，每个结点度数至少为 n，G 是连通图。 又若简单图 G 至多有 2n 个结点，每个结点度数至少为 n-1，那么 G 是连通图吗？为什么？ 答：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）可知，结论成立 方法二：显然这个图中任意的一对结点的度数之和大于等于 2n，所以这个图是汉密尔顿图，所以这个图是连通的。8、证明如下：n 个结点的简单无向图，连通的最低条件是有 n-1 条边。而 e0.5(n-1)(n-2) 可得

5、 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), 所以至少有一条边连接 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)(k-2)。根据归纳假设，显然这 k 个结点之间是连通的，而根据上面我们知道，至少有一条边

6、使 v 和其它结点相连，所以此时这个图是连通的。 根据（1）（2）（3）可知结论成立。 5.3 习题参考答案1、设图 G=,V=v1,v2,v3,v4的邻接矩阵 解：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、 答：长度为 4 的路径总数为 15 条，其中 3 条是回路。从 v3 到 v4 的迹有 3 条。 3、 解:邻接矩阵如图：(按字母顺序)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 的出度是 2，入度为 3d 的出度是 2，入度为 2A(G)= 0 1 0 1 1 0 1 1 1 1 0 0 1 0 0 0e 的出度是 1，入度为 1晓津补充一下：出度就可以数该行的非零个数，入度则可数该列的非零个数从结点 c 出发长度为 3 的回路有：c-e-b-c , c-d-d-c4、给定 G 如图所示， a)写出邻接矩阵 b)G 中长

7、度为 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、 答：不连通晓津补充一下：原矩阵为：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、 解：邻接矩阵为：M(G)=0 1 0 10 0 1 1 0 1 0 10 1 0 0其余答案略，用阮同学的话说就是：太麻烦了，自己算一算吧:)7、证明：必要性：设 e 是 G 某一连通分支的一条边。假设 e 包含在 G 的某一回路中，若把 e 去掉后，显然该连通分支仍是连通的，所以W（Ge ） W（G）。这和 e 是 G 的割边矛盾。充分性：设 e 是连接 vi,vj 的一条边，假设 e 不是割边。

8、则把 e 去掉后，该连通分支仍是连通的vi 到 vj 必有路，不妨设此路为 vi.vj,则必有 vi.vjevi,这和 e 不包含在 G 的任一回路中相矛盾，所以 e 是割边。5.4 习题参考答案1、。 都可以实现：如图： 2、答：n 是奇数。因为完全图中，每个结点度数均为 n-1，显然要有欧拉回路，n1 必须是偶数，所以 n 是奇数。3、 解：如下：4、答：不一定。若该图是连通的，则可以一笔画出，否则不可以。如下图5、答：不存在，因为欧拉图中，存在一条回路，包含各边一次且仅一次，所以任意去掉一条边，该图仍是连通的。 6、答：（1）是，因为存在一条欧拉回路，所以任意两个结点都是可达的（2）不是，如： 7、答：(1)是。a-i-h-g-d-e-f-b-c-j-a(2)不是。因为我找不出这样的回路，若学友们找出的话请告诉我，谢谢。 8、答：不能。根据定理 5.4.3 9、答：可能。我们把每个人看成一个结点，若是朋友的用一条边连接。因此每个结点的度数都大于等于 10，所以任意两个结点的度数之和都大于等于 20，因此这个图中一定存在一条汉密尔顿回路，按这个回路排座位就可以了。 5.5 习题参考

9、答案1、证明：设结点数为 v，边数为 e（1）若 v 3，则结论显然成立。（2）若 v3,则 3v6e ，解得 v(e+6)/3假设图中每个结点的度数都大于 4，即大于等于 5。则所有结点的度数之和就大于等于 5(e+6)/3，因此边数 e5(e+6)/6 ，解得e30，这和已知边数小于 30 相矛盾。所以结论成立。 2、证明：设这个图的面数为 r，由欧拉公式 nm+r=2 得 r=m-n+2因为 deg(R)4，所以 2m=deg(R)4(m-n+2)，解得 m2n4 3、证明：（1）彼得森图每个结点的度数都等于 3，所以不是欧拉图。（2）证明思路：只要能找出和 K5 或 K3,3 同胚的子图就行了。不过我找不出来，请各位学友找一找。4、证明：由欧拉公式可得， r8 ，假设至少有一个面不是 3 条边围成，则必定大于 3 条边，所以 2e3r 24 ，所以 e12，这与已知有 12 条边相矛盾。5.6 习题参考答案1、答：应是 6 个。因为它是连通且无回路的无向树，因此在此树中只能有 5 条边。将这 5 条边按不同方式连接 6 个结点可得到 6 种形态的无向树，大家不妨画一画。2 答：c)不是树。每个结点都有路，则也包括回路，而树是无回路的，因此 c)不是树。3、答：b)是树，因为在树中，删去任一条边均使图变得不连通，则此边就是割边。4、解：设叶子数为 n,则根据树的定义和图中总度数是边数的 2 倍，可列出方程如下：24+33+n1=2(n+2+3-1)解之得：n=95、画出结点数 n5的所有不同构的树。 解：如下图： 6、解：同第 4 题的解法，设叶结点数为 n1，则有：n1+2n2+3n3+.knk=2(n1+n2+n3+.+nk-1)解之得：n 1=n3+2n4+3n5+.+knk+2+2 7、解： 要解本题，实际上是求该网点组成的图的最小生成树，呵呵，这对学过数据结构的同学来说是比较容易的： 请看下图：线路的长度为 1+2+3+5+7=188、求算式(a+(b*c)*d)-e)(f+g)

《离散数学课后答案五》由会员豆浆分享，可在线阅读，更多相关《离散数学课后答案五》请在金锄头文库上搜索。