离散数学 邱晓红 第12章

《离散数学 邱晓红 第12章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十二章树主讲:熊焕亮第十二章树树是图论中重要内容之一，在计算机科学技术中有着广泛的应用。树的概念由数学家约当（Jordan）给出了统一的定义。在讨论本章内容之前，首先作个说明，就是本章所谈回路均指初级回路（圈）或简单回路，而不含复杂回路（有重复边出现的回路）。2第十二章树12.1树的概念及性质12.2最小生成树12.3根树12.4树的应用*312.1树的概念及性质12.1.1树的定义12.1.2树的一些性质412.1.1树的定义定义12.1.1若简单连通无回路的无向图称为无向树，或简称树，常用表示树，平凡图称为平凡树。无向树中度数为1的顶

2、点称为树叶，度数大于等于2的顶点称为分支点，只有一个顶点（无边）的简单图称为平凡树；若无向图G至少有两个连通分支，则称G为森林。也就是说，（无向）树是连通无回路的简单图，后面提到树时，如果没有特别说明都是指无向树，在证明树的性质前，先回忆一下桥（或说割边）的定义，将看到树的每一条边都是桥。512.1.1树的定义定义12.1.2给定图，说边是G的桥（割边），如果，即G中删除之后会增加连通分支数。显然，如果e是G的桥，则有，即删除一条边，最多增加一个连通分支，另一方面，若e是G的桥，则e不属于G的任意回路。612.1.2树的一些性质无向树有许多

3、性质，这些性质中有些既是树的必要条件又是充分条件，因而都可以看作树的等价定义，见下面定理712.1.2树的一些性质定理12.1.1设是n阶m条边的无向图，则下面各命题是等价的：（1）G是树。（2）G中任意两个顶点之间存在惟一的路径。（3）G中无回路且。（4）G是连通的且。（5）G是连通的且G中任何边均为桥。（6）G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的圈。812.1.2树的一些性质证（1）（2）对n作归纳，n=1时，m=0，显然有m=n-1。假设n=k时命题成立，现证n=k+1也成立。由于G连通而

4、无回路，所以G中至少有一个度数为1的结点,在G中删去及其关联的边，便得到k个结点的连通而无回路的图，由归纳假设知它有k-1条边。再将结点及其关联的边加回到原图G，所以G中含有k+1个结点和k条边，符合公式m=n-1。所以，G中无回路，且m=n-1。912.1.2树的一些性质（2）（3）：首先证明G中无回路。若G中存在关联某顶点v的环，则v到v存在长为0和1的两条路径（注意初级回路是路径的特殊情况），这与已知矛盾。若G中存在长度大于或等于2的圈，则圈上任何两个顶点之间都存在两条不同的路径，这也引出矛盾，下面用归纳法证明m=n-1。n=1时，G

5、为平凡图，结论显然成立。设n时结论成立，当n=k+1时，设为G中的一条边，由于G中无回路，所以G-e为两个连通分支。设分别为中的顶点数和边数，则，由归纳假设可知,于是，。1012.1.2树的一些性质（3）（4）：只要证明G是连通的。否则设G有个连通分支，中均无回路，因而全为树，由（1）（2）（3）可知，。于是由于，这与矛盾。1112.1.2树的一些性质（4）（5）：若G不连通，则存在两结点和，在和之间无通路，此时增加边（，），不会产生回路，但这与题设矛盾。由于G无回路，所以删去任一边，图便不连通。1212.1.2树的一些性质（5）（6）：由

6、于G中每条边均为桥，因而G中无圈，又由于G连通，所以G为树，由（1）（2）可知，且，则之间存在惟一的路径，则（（）为加的新边）为中G的圈，显然圈是惟一的。1312.1.2树的一些性质（6）（1）：只要证明G是连通的。且，则新边产生惟一的圈，显然有为G中u到v的通路，故u~v，由的任意性可知，G是连通的。1412.2最小生成树12.2.1生成树12.2.2最小代价生成树1512.2.1生成树任何无向连通图都有一种特殊的生成子图，这就是树。1612.2.1生成树定义12.2.1设T是无向图G的子图并且为树，则称T为G的树。若T是G的树且为生成子

7、图，则称T是G的生成树。设T的G生成树，若则称e为T的树枝，否则称e为T的弦。并称导出子图为T的余树，记作。注意不一定连通，也不一定不含回路。在图12.2.1所示图中，实边图为该图的一棵生成树T，余树为虚边所示，它不连通，同时也含回路。1712.2.1生成树图12.2.1余树概念示意图1812.2.1生成树定理12.2.1无向图G具有生成树当且仅当G是连通图。证必要性显然。只需证明充分性。若G中无回路，G为自己的生成树。若G中含圈，任取一圈，随意地删除圈上的一条边，若再有圈再删除圈上的一条边，直到最后无圈为止，易知所得图无圈（当然无回路）、

8、连通且为G的生成子图，即G的生成树。常称此种产生生成树的方法为破圈法。1912.2.1生成树推论12.2.1设G为n阶m条边的无向连通图，则。证由定理12.2.1可知，G有生成树