第9章 树(3).pptVIP

第9章 树 9.1 无向树 9.2 根树及其应用 9.3 例题选解 习 题 九 9.3 例 题 选 解 【例9.3.1】 判断下列命题是否为真。 （1）若n阶无向简单图G的边数m=n-1，则G一定是树。 （2）若有向图G仅有一个顶点的入度为0，其余顶点的入度都是1，则G一定是有向树。 （3）任何树T都至少有两片树叶。 （4）任何无向图G都至少有一棵生成树。 （5）根树中最长初级通路的端点都是树叶。 （6）无向连通图G中的任何一条边都可以成为G的某棵生成树的树枝。 （7）（n，m）图的每棵生成树都有n-1条树枝。 （8）以1，1，1，1，2，2，4为度数列的非同构的树有2棵。 （9）任何无向树的边均是桥。 （10）G是（n，m）无向图，若m≥n，则G中必有圈。 （11）G是（n，m）无向连通图，若要求G的一棵生成树，必删去G中的m-n+1条边。 解答与分析 （1）假命题。当G是非连通无向图时，顶点数和边数可能满足m=n-1，但G不是树（如图9.3.1所示）。 ? （2）假命题。当G是非连通的有向图时，各点入度可能满足命题条件，但G不是有向树（如图9.3.2所示）。 （3）假命题。在平凡树中没有两片树叶。 （4）假命题。当且仅当G是连通图时，G中才有生成树。例如图9.3.1所示非连通图没有生成树。 （5）假命题。根树中最长初级通路的两个端点，一个是树叶，而另一个是树根。 （6）假命题。无向连通图G中若有环，则环永远无 法成为生成树的树枝，因为树中无圈。 （7）真命题。因为（n，m）图的每棵生成树都是其生成子图，必有n个顶点。 （8）真命题。如图9.3.3所示，在一棵中两个2度顶点邻接，在另一棵中两个2度顶点不邻接。 （9）真命题。由树的等价定义可知。 （10）真命题。若G是非简单图，则G中必有环或平行边，故G中有圈。 若G是简单连通图，则G中必有圈，否则G是树，m=n-1，这与m≥n矛盾。 ? 若G是简单非连通图，设其有k个连通分支，若每个连通分支均无圈，则G是森林，必有m=n-k，与m≥n矛盾，故至少有一个连通分支不是树，在此分支中有圈。 （11）　真命题。因每棵生成树必有n-1条边。 【例9.3.2】 （1）若T是高度为k的二元树，则T的树叶数最多为2 k （2）若T是高度为k的二元完全正则树，则T的顶点数为2 k+1-1。 分析 （1）在同样高度的二元树中，二元完全正则树的树叶最多，只需证明二元完全正则树的树叶数是2 k片。 （2）利用（1）的结果即可。 证明 （1）对k做归纳： 当k=1时，树叶数t=2=2 1，结论成立。 假设k=n时结论成立，t=2 n。 当k=n+1时，因为在原来2 n片树叶中，每片叶均增加了2个儿子变成分支点，所以有树叶 t=2×2 n=2 n+1，结论成立。 （2）利用（1）知，在二元完全正则树中，高度为k的顶点有2 k个，故树高为k的顶点总数为 1+2+2 2+…+2 k= 【例9.3.3】 若图G=〈V，E〉连通且e∈E，证明： （1）e属于每一个生成树的充要条件是e为G的割边。 （2）e不属于G的任一个生成树的充要条件是e为G中的环。 分析 本题（1）、（2）均需从充分和必要两部分予以论证。在（1）中如e属于每个生成树，需证G中删去e后必不连通，否则e必不属于某个生成树，与题设矛盾。在（2）中要证明e是环，可证e是仅含其本身的一个回路，否则e必属于某棵生成树。 证明 （1）先证充分性。设e属于G中每个生成树T，若e不是割边，则G-e连通，因此在G-e中必存在生成树T，因为V（G-e）=V（G），所以T也是G中的生成树。但T中不包含e，与题设矛盾。 再证必要性。设e是G的割边，若有