离散数学课后答案五

5.1 习题参考答案 1、阮允准同学提供答案:解：设度数小于 3 的结点有 x 个，则有3×44×32x2×16解得：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、试证明下图中两个图不同构。 晓津证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。我们可以看出，(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 出发的初级回路有：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 中有一个回路，它至少包含每个结点一次时，可以知道，任一结点可达其他所有结点，因此它是强连通的。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 条边。而 e>0.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), 所以至少有一条边连接 v 和其它结点。 下面我用数学归纳法进一步证明： （1）容易证明当 n=1,2 时，结论成立 （2）假设当 n=k 时，结论成立，即若 e0.5（k-1)(k-2) 时结论成立 （3）当 n=k+1 时，若此时每个结点度数为 k，则结论显然成立，否则必存在一个结点 v 度数至多只有 k-1 度，即这个结点最多只有k-1 条边和它相连。因为此时总的边数 e>0.5k(k-1),则其它 k 个结点之间的边数 e'0.5k(k-1)-(k-1)=0.5(k-1)(k-2)。根据归纳假设，显然这 k 个结点之间是连通的，而根据上面我们知道，至少有一条边使 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 中长 度为 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 不是割边。则把 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 习题参考答案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 倍，可列出方程如下：2×4+3×3+n×1=2×(n+2+3-1)解之得：n=95、画出结点数 n5的所有不同构的树。 解：如下图： 6、解：同第 4 题的解法，设叶结点数为 n1，则有：n1+2×n2+3×n3+.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)