应用离散数学（第4版）（微课版）习题及答案 习题5.3

应用离散数学图论杭电－周丽、方景龙第五章PAGE3§5.3树习题5.3一个树有5个1度顶点，3个2度顶点，其余的顶点都是3度顶点，问一共有几个顶点？解：用树的性质q=p1和握手定理。设有x个顶点，于是,2q=2(x-1)=15+23+（x-8）3解得x=11，故T有11个顶点。一个树有2个2度顶点，3个3度顶点，4个4度顶点，其余顶点度数都是1，问这个树有几个1度顶点？解：用树的性质q=p1和握手定理。设有x个1度顶点，于是,2q=2(x+9-1)=22+33+44+x解得x=13，故T有13个1度顶点。证明：若图是个树组成的森林，则。证明：设个树分别为G1（p1,q1）图，G2（p2,q2）图，…Gk（pk,qk）图，由于每棵树的边都满足q1=p1-1,q2=p2-1,…，qk=pk-1,则q=q1+q2+…+qk=p1-1+p2-1+…+pk-1=（p1+p2+…+pk）-k=p-k4．证明：阶树的顶点度数之和为。证明：用树的性质q=p1和握手定理中所有的顶点度数之和是边数的二倍，得阶树的顶点度数之和为。找出图5.9中二个图的生成树，并求该生成树的所有弦及相应基本回路，该生成树的所有枝及相应基本割集。解：图(a)的生成树如下：176823511491012所有的弦及对应的基本回路：弦（2，4），基本回路（1，2，4，3，1）弦（4，5），基本回路（1，3，4，5，1）弦（6，8），基本回路（6，7，8，6）弦（6，10），基本回路（6，9，10，6）弦（10，11），基本回路（10，11，12，10）所有的枝及对应的基本割集：枝（1，2），基本割集{（1，2），（2，4）}枝（1，3），基本割集{（1，3），（2，4），（4，5）}枝（3，4），基本割集{（4，5），（2，4）}枝（1，5），基本割集{（1，5），（5，4）}枝（5，6），基本割集{（5，6）}枝（6，7），基本割集{（6，7），（6，8）}枝（6，9），基本割集{（6，9），（6，10）}枝（9，10），基本割集{（9，10），（6，10）}枝（10，12），基本割集{（10，11），（10，11）}枝（11，12），基本割集{（10，11），（11，12）}图（a）的另一棵生成树如下图所示，其所有弦：（1，3），（2，4），（7，8），（9，10），（11，12），相应于每条弦的基本回路是（1，3，4，5，1），（2，4，5，1，2），（7，8，6，7），（9，10，6，9），（11，12，10，11）。图（a）的一棵生成树的所有枝：（1，2），（1，5），（3，4），（4，5），（5，6），（6，7），（6，8），（6，9），（6，10），（10，11），（10，12），相应于每条枝的基本割集是，，，,,,,,,,。图（a）的一棵生成树图（b）的一棵生成树 图（b）的一棵生成树如上图所示，其所有弦：（1，2），（1，9），（2，8），（8，9），（5，6），相应于每条弦的基本回路是（1，2，3，8，1），（1，9，2，3，8，1），（2，8，3，2），（8，9，2，3，8），（5，6，7，4，5）。图（b）的一棵生成树的所有枝：（1，8），（2，9），（2，3），（3，8），（3，4），（4，5），（4，7），（7，6），相应于每条枝的基本割集是，，，,,,,。6．在什么情况下，图的某条边是的所有生成树所共有的？解：如果该边是桥，如果不选此条边，图就会变成非连通图，因此是所有生成树所共有的。7．写出普里姆转换算法的算法步骤，并证明普里姆转换算法是正确的，即算法执行的结果会产生一个最小生成树。解：1．procedurePrim(G，s，ET)2． ￡//将起始顶点加入到集合￡中3． 〒//初始边集合为空 //第4～17行在边集〒放入条边4． fortodo ￡￡5． 6． for￡中最近的顶点do7． for不在￡中的每个点do8． ifthen9． 10． 11． 12． end if13． end for14． endfor15． ￡=￡//将选中的顶点放入￡中16． 〒=〒//将选中的边放入〒中17． endfor18． return（〒）19．endPrim8．克鲁斯卡尔（Kruskal）算法用来求解有个顶点的连通加权图的最小生成树。它假设图开始只包含的顶点，不包含边，每次循环都增加权值最小的边到中，且不产生回路，当有条边时，停止。请写出克鲁斯卡尔算法的算法步骤，并证明克鲁斯卡尔算法是正确的，即算法执行的结果会产生最小生成树。解：Kruskal算法基本描述：先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。从带权图的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。（3）依次类推，直至森林中只有一棵树，也即子图中含有n-1条边为止。9图5.16习题9的图解：用Prim算法得到的最小生成树为：用Prim_Alternate算法得到的最小生成树为：用Kruskal算法得到的最小生成树为上面的二种都可以得到。10．判断下面说法是否正确，如果是对的，加以证明，否则给出反例。其中是连通加权图。（1）如果中所有边的权值都不一样，则不同的生成树的权值都不一样。（2）如果是的一条边，权值最低，则被中任意一个最小生成树所包含。（3）如果一直删除中权值最大的边且保证图连通，则最后得到的图为的最小生成树。解：（1）错误。例如二个生成树中只有二条枝不同，其他的枝都相同。其中一个生成树中的一条枝的权值是3，另一条枝的权值是7。而另一个生成树