发布时间 : 星期一 文章四川大学离散数学（冯伟森版）课后习题答案习题参考解答（图论部分）更新完毕开始阅读
去找 http://www.7zhao.net 其中ｐ１＝ｕ．．．ｕ１代表ｕ到ｕ１的最短路径，ｐ２＝ｕ２．．．ｕ代表ｕ到ｕ２的最短路径，且ｕ１ｕ２边不在最短路径上，否则他们的最短路径不是同奇偶的；因此，Ｐ中包含圈，这与树中无圈相矛盾，所以Ｔ中的边，只能存在于两个点集合之间，所以是二部图■
6. 证明：如果T是树且Δ≥k，则T中至少有k个叶结点。
证明：当T为非平凡树时，根据T的定义，T中每个枝点都是割点，当删除d(v)= Δ 的节点时，ω（T-v）=Δ ，每个分支都是数，如果分支都是平凡树，则这些节点都是T的叶，叶节点数为Δ。如果分支有非平凡数，那么至少有两个叶节点，其中至少一个是删除v时就存在的，因此总的叶节点个数≥Δ≥k。因此Ｔ中至少有ｋ个叶结点■
7. 设G为n（n≥3）阶简单图，证明G或中必含圈。（有误，>4,p223）
证明：反证法，假设G和中都不含圈，那么G和的所有分支都是树。则G所包含的最大边数|E(G)|=n-1, 则所包含的最大边数|E()|=n-1. 因为G及的边数总和|E(G)|+ |E()| = n(n-1)/2, 但根据假设条件，max|E(G)|+max |E()|=2(n-1) < n(n-1)/2, 矛盾.因此，G或中必含圈■
8．证明：恰好有两个顶点的度为1的树必为一道路P。
证明：因为此树仅有2个叶结点，因此Δ<3。那么枝点的度只能为2。所以此树为一条链，及一条道路■
9. 设T是一个n+1阶树，G是最小点度的简单图。证明：Ｇ必含有与Ｔ同构的子图。
证明：采用归纳法证明，对ｎ进行归纳
（１） 当ｎ＝１时，Ｔ为２阶树，因为Ｇ是最小点度的简单图，所以任意意个结点与其邻结点都构成一颗２阶树，成立
（２） 假设ｎ＝ｋ，ｋ≥２时，结论成立，即T是一个ｋ+1阶树，G是最小点度的简单图。
Ｇ必含有与Ｔ同构的子图
（３） 当ｎ＝ｋ＋１时，G是最小点度的简单图，Ｔ是任意一棵ｋ＋２阶树，在Ｔ中删除
一个叶结点ｔ，那么Ｔ－｛ｔ｝是一棵ｋ＋１ 阶树，利用归纳假设，G中必存在与Ｔ－｛ｔ｝同构的子图T’，T’中最大的点度不超过k，所以每个T’中的结点都有邻结点不包含在T’中，所以T’可在某个结点上增加一个额外的结点u，使T’+{u} 与T 同构 综上所述，结论成立■
10.设e是连通图G的一条边。证明：e是G的割边当且仅当e含于G的每个生成树中。
证明：
1）充分性：e是G的割边则e含于G的每个生成树中
假设e不包含在某棵生成树T中，那么e 一定在T的树补边集中，那么G-{e }中依然包含树T,因此G-{e }连通，与e是割边矛盾，因此e含于G的每个生成树中； 2) 必要性：e含于G的每个生成树中则e是G的割边 假设ｅ不是Ｇ的割边，那么Ｇ－｛ｅ｝依然连通，具有生成树，这些生成树也是Ｇ的生成树，
13
去找 http://www.7zhao.net 且不包含ｅ，与e含于G的每个生成树中前提矛盾，因此e是G的割边。
综上所述，题设结论：e是G的割边当且仅当e含于G的每个生成树中成立■
11.设T1和T2是连通图G的两个不同的生成树，a是在T1中但不在T2中的一条边。证明：T2中存在一条边b，使得（T1-a）+b和（T2-b）+a也是G的两个不同的生成树。
证明：从T1中删除边ａ，得树T1－１和T1－２ ，分别用Ｖ１，Ｖ２ 表示这两棵子树的结点集合，设Ea＝｛ｅ｜ｅ的两个端点分别属于Ｖ１，Ｖ２｝，显然，ａ∈Ea．因为ａ不在T2中，所以ａ是T2的树补边。设C（a）为在中T2增加边a后所得到的圈，则C(a)中必然存在T2 的树边b不在T1中但在Ea中。否则，C(a)上的T2的所有树边均在T1中或均不在Ea中。如果C(a)上的T2的所有树边均在T1中，则C(a)上的所有边都在T1中，与T1是树矛盾。如果C(a)上的T2的所有树边均不在Ea中，则C(a)中除ａ外所有的边的端点均在Ｖ１或Ｖ２中，与C(a)是基本回路矛盾。所以C(a)中必然存在不在T1中但在T2中的的树边，设ｂ是其中的一条。则（T1-a）+b连通且无回路是Ｇ的生成子图，它是Ｇ的生成树。同理（T2-b）+a也是Ｇ的生成树■
12.用Kruskal算法求图11.13的一个最小生成树。
解：略，请参考书中算法计算■
13. 设简单连通图G=（V，E）的边集E恰好可以划分为G的两个生成树的边集。证明：如果G中恰有两个4度以下结点u和v，则uv?E。（请冯老师帮助证明下）
14. 已知n阶m条边的无向简单图是由k（k≥2）棵树组成的森林，证明：m = n – k。
证明：设ｋ棵树分别为ｎ１，ｎ２，．．．ｎｋ，根据树的性质有如下公式成立： n 1+n2…nk = n (1) (n 1-1)+(n2-1)…(nk-1) = m (2) (1)-(2) 得：n – m = k => m = n-k■
15. 证明: 简单连通无向图G的任何一条边，都是G的某一棵生成树的边。
证明：简单连通无向图G的任何一条边，要么是割边，要么是非割边。如果是割边，那么此边是所有生成树的树边；如果不是割边，设边为ｅ，那么G-{e}连通，可以求出生存树Ｔ，此Ｔ也是Ｇ的生存数，且不包含ｅ ，那么ｅ 是Ｔ的树补边。则Ｔ+{e},有唯一一个圈Ｃ，删除圈上任意一条非ｅ边，便得到一颗包含ｅ边的树■
16. 证明:在完全二又树中,边的数目等于2(t -1)，式中t是叶的数目。
证明：设Ｔ中的结点数为ｎ，枝点数为ｉ；根据完全二叉树的定义，有下面的等式成立。n=i+t,m=2i,m=n-1.解方程组，得到m=2(t-1) ■
17. 决定一个m叉树中内部道路长度之和与外部道路长度之和的关系。
14
去找 http://www.7zhao.net 解：根据完全二叉树的内部道路长度之和与外部道路长度之和的关系猜测m叉树中内部道路长度之和与外部道路长度之和的关系为：Ｊ＝（ｍ－１）Ｉ＋ｍｉ．其中Ｊ表示各叶结点的道路长度之和，Ｉ表示各分支点道路长度之和，ｉ表示分支结点数。下面对分支结点数ｉ进行归纳：
ｉ＝１时，Ｉ＝０，Ｊ＝ｍ，故Ｊ＝（ｍ－１）Ｉ＋ｍｉ成立． 假设ｉ＝ｋ是结论成立． 当ｉ＝ｋ＋１是，设在完全ｍ叉树Ｔ中，ｖ是一个道路长度为ｌ的分支点且其ｍ个儿子ｖ１，ｖ２．．．ｖｋ都为叶结点，那么Ｔ－｛ｖ１，ｖ２．．．ｖｋ｝是含ｋ个分支点的完全ｍ叉树。由归纳假设有Ｊ｀＝（ｍ－１）Ｉ｀＋ｍｋ，比较Ｔ和 Ｔ－｛ｖ１，ｖ２．．．ｖｋ｝，Ｊ＝Ｊ｀＋ｍ（ｌ＋１）－ｌ＝Ｊ｀＋（ｍ－１）ｌ ＋ｍ ，Ｉ＝Ｉ｀＋ｌ，所以Ｊ＝（ｍ－１）Ｉ｀＋ｍｋ＋（ｍ－１）ｌ ＋ ｍ ＝（ｍ－１）Ｉ＋ｍ（ｋ＋１）■ 18. 给出公式的根树表示。 解：将标示符号看成叶结点，逻辑连接词作为分支结点，按公式的先后顺序构造根树如下： ■Λ ? Λ P ? ` P Q P Q ? R ? Λ ? ■ 19. 给定权1,4,9,1,2,6,4,6,8,10,构造一个最优二叉树。 解：根据带权最优二叉树定理构造过程如下： 15
去找 http://www.7zhao.net 1 4 9 1 2 6 4 6 8 10 1 1 2 4 4 6 6 8 9 10 重新排序 ==== 2 2 4 4 6 6 8 9 10 ==== 4 4 4 6 6 8 9 10 ====== 8 4 6 6 8 9 10 ==== 8 10 6 8 9 10 ==== 8 10 14 9 10 8 9 14 10 10 交换10，9 ======== 17 14 10 10 ==== 17 14 20 ============= 31 20 ============= 51 10 9 6 8 4 6 4 2 1 1 ■
20. 把图11.14的有序林变换成一个二叉树。
解：STEP1: 将每棵有序树采用中间格式表达出来 SETP2： 再用一条有向道路把各分支的根从左到右连接起来
16