特殊图类.docVIP

第七章 特 殊 图 类树是图论中最重要的概念之一。Kirchhoff)对电网络研究。树又是图论中应用最广泛的分支之一。特别是在计算机科学中。这一节主要研究无向树。树的定义及性质 定义7.1-1 连通无圈图称为树，记作T。无圈图称为森林Forest). 树中的1度结点称为树叶Leaf)，其余结点称为分支结点。每个连通分支均为树的图森林。平凡图称为平凡树。图7.1-1中的图是五个结点的树。 树有很多等价的特征，这些特征由下述定理一并给出。 定理7.1-1 设图T是图，下列命题等价。 T是树（连通且无圈）； T连通且每条均是割边（这时称T是最小连通图）； T连通且；T无圈且； T无圈且在T中任意两个不相邻的结点之间加一条边，恰得一圈（这时称T为最大无圈图）；T的每对结点间有唯一路。 证明⑵。因T是树，所以T连通，下面用反证法证明T的每条边均是割边。假设T中有一条边不是割边，即仍连通，则在中有u到v的路，因此，图中有圈，这与T无圈矛盾。 ⑶。由知T连通。下面对n用数学归纳法证明。当n=1时，因为所有边都是割边，所以图不能有边，即，结论成立。 假设对于任何结点数小于的图结论都成立现在研究图T，设e是T中一边（当然是割边），则两个连分支，分别是图和图，且均有中的性质。由归纳假设，分别有，，因此,，即故。由第二数学归纳法原理，结论成立。 ⑷。由知，，现在对n用归纳法证明无圈。当n=1,2时显然无圈。设点数为n-1结，考查结点数为n的。由于T是连通的，所以T中每个结点v有，又，所以必有一结点否则，若对于任意结点v均有，则由握手定理有从而这与题设矛盾。现在从T中删去及其关联的边，得到图，由归纳假设无圈。又因为，故在中增加边仍无圈，图T无圈。 ⑸。已知T无圈下面证连通设连通分支，由于每个连通分支不存在圈它们都是树设有个结点，其边数为；现在，所以的边数。然而已知，从而必有，。 既然连通，则任意两点间都有路在任意二不相邻的结点间加一边则至少得一圈若得两圈，则两圈必都经过，因此仍有回路，图中有圈，矛盾。 ⑹。设是中任意一对结点相邻路不相邻由题设有一圈则中有路。由于无圈，则任意两点间只有一条路若某一对结点有两条路是一回路，即中有圈，矛盾。 ⑴。因为的任何一对结点间有路，所以连通。又的任何一对结点间有唯一路，则无圈。否则，若有圈，则圈上的任何二结间都至少有两条路，矛盾。树中，边数，则由握手定理得 ① ⑴若T没有树叶，由于T是连通图，所以T中任一结点均有，从而 ② 则①与②矛盾。 ⑵若T仅有一片树叶，则其余n-1个结点的度数均不小于2，于是 ③ 则①与③矛盾。 综合⑴、⑵知树中至少有两片树叶。 7.1.2 生成树 定义7.1-2 无向图的生成子图是树，则的生成树。中的边称为的树枝，不在中的边称的弦。的所有弦的集的导出子图称的树。 图7.1-2是的生成树，是的余树。要注意的是余树不一定是树。 一个是否连通与它是否有生成树关系密切，我们有下面的定理。 定理7.1-2 图连通的充分条件是有生成树。 证明 充分性。若有生成树，即的子图是连通的，所以也是连通的。 必要性。设连通若中无圈，则本身就是生成树；若中有圈，则任取一圈，并删去圈上一边得图，仍连通若无圈就是生成树若还有圈，则取的一圈，并删去圈上一边重复上述过程，直到无圈即得一棵生成树。。 例7.1-4 图7.1-3中，是的生成树，是的生成子图，但不是树，不是的生成子图、都不是的生成树。 定理7.1-2生成树—破圈图7.1-4是的一棵生成树到是圈生成树。 求连通图的生成树—避圈生成树 7.1.3 最小生成树 最小生成树问题有很广泛的应用，在大规模集成电路、管道网、公路网和通讯网的布线等问题中常常遇到。 定义7.1-3 设是带权连通图，T是G的一棵生成树，T的各树枝的权之和称为T的权(Weight)，记作，即。 G的所有生成树中权最小的生成树称为最小生成树(Minimal Spanning Tree)（或称最小支撑树）。 下面介绍一个求最小生成树的算法—克鲁斯克尔（Kruskal）算法，它是一种避圈法，其基本思想是：选择图中权最小的一条边，相继添加不与已经选择的边形成圈的权最小的边，挑选n-1条边为止（其中n为结点的个数）。 设是有n个结点的连通简单带权图。则由下述算法可求得G的最小生成树。 克鲁斯克尔算法（1956）： ⑴ 选取边，使得最小，令,置i为1； ⑵ 若已选好，则从中选取边使其满足： ①中无圈；②是中满足①的所有边中权最小的。 ⑶ 若存在，则令， ⑷ 若，则停止，否则转(2)。 此时得到的En-1的边导出子图就是所求的最小生成树。 定理7.1-3 由克