去找 http://www.7zhao.net 解：对图的结点和边进行编号如下：
ｖ１ ｅ２ ｖ３ ｅ７ ｅ５ ｖ５ ｅ１１ ｅ６ ｅ８ ｅ１０ ｅ９ ｖ６ ｅ１ ｅ３ ｅ１２ ｖ２ ｅ４ ｖ４ ｖ７ 邻接矩阵： 因此可达矩阵为： 强分图矩阵为： 关联矩阵为： ■ T31. 设P= (pij) n×n是可达性矩阵。证明:P错误！未找到引用源。P中第i行中非零元素所在列号给出了包含结点vi的强分图的全部结点编号。 证明：根据强分矩阵的计算过程可知，其包含的含义是结点间双向可达信息。根据有向图的双向可达关系是一个等价关系，因此P错误！未找到引用源。PT中第i行中非零元素所在列号既是一个等价类，所以包含了一个强分图的所有结点■ 已完成[1，2，3，4，5，6，7，8，9，10，11，12，13,14，15，16，17，18，19，２０,21，２３，２４，２５，２６，２７，２８，29，３０，31] 第２２题未证明 11
去找 http://www.7zhao.net
习题十一
1. 设一个树中度为k的结点数是nk（2≤k），求它的叶的数目。
解：设T的节点总数为n，叶节点数目为t ，根据题意及握手定理有： t + n2 + n3 + …+ nk = n (1)
t + 2n2 + 3n3 + …k(nk) = 2(n-1) (2) 握手定理 (1),(2)联立求解得：
t = n3 + 2n4 + … (k-2)nk + 2■
2. 证明：树T中最长道路的起点和终点必都是T的叶。
证明：假设T中最长道路P=vi1vi2…vik的起点或终点不是T的叶结点，设d(vi1)>1,则vi1的
12l
所有邻接点(v‘,v’…,v’)都在P中，那么在T中可以找到一个回路,那么截取道路P, 得到
l
回路C= vi1 …v’ vi1 .与T中无回路矛盾。对于d(vik)>1时同理。因此，假设不成立，即最长道路P的起点和终点都是T的叶节点■
3. n（n≥3）阶无向树T的最大度Δ至少为几？最多为几？
解：当T中只有一个枝点时，Δ = n-1,为最大值。 当T构成一条链时，只有两个叶结点，其余结点都为2度点，此时Δ = 2，为最小值，因此Δ至少为2 ，最大为n-1■
4. n（n≥3）阶无向树T的最大度Δ=2，则T中最长的简单道路为几？
解：根据第3题结论，当无向树T的最大度Δ=2时 ，T构成一条链，以此最长的简单道路包含所有的节点，道路长度L=n-1■
5. 证明：任何无向树都是二部图。
证明：以树Ｔ中任意结点ｕ为起点，将与ｕ最短距离为偶数的结点放入ｖ１结点集合，将与ｕ最短距离为奇数的结点放入ｖ２结点集合，那么这两个结点集合中，显然不存在公共点，同时两个结点集合组成了树的全部结点，因此是数Ｔ的结点集合的一个分化。假设在Ｖｉ集合中存在两个结点ｕ１，ｕ２是邻结点，那么就存在如下道路：ｐ＝ｕ．．．ｕ１ｕ２．．．．ｕ，
12
去找 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