10图论-树11-24解释.ppt

单位元： 1）自然数N上的加法中的单位元为0，乘法中的单位元是1. 2）M(R)实数n阶矩阵上的加法中的单位元为全0矩阵 乘法中的单位元为单位矩阵 3）幂集P(S)上的并运算中的单位元是： 交运算中的单位元是： 对称差运算中的单位元是： 4）函数集合AA上的复合运算中的单位元是： 5)若对非零实数集合R*上定义运算：a▲b = a 分析该运算的单位元： 下面二个运算的单位元是： * a b c a a b c b b c a c c a b Δ a b c a a b c b a b c c a b c 返回 V1 V2 V3 +,*可交换可结合 ∪，∩可交换可结合 ∨，∧可交换可结合 *对+可分配 互相可分配 互相可分配 *，+无等幂律 ∪,∩都有等幂律 ∨∧都有等幂律 *，+无吸收律 ∪,∩有吸收律 ∨∧都有吸收律 *，+有消去律 ∪,∩无消去律 ∨∧无消去律 返回 上次课主要内容 一、无向树 1）定义：设G＝V，E是n阶m条边的无向图 连通无回路（初级回路或简单回路）的无向图称为无向树， 或简称树。 常用T表示树，平凡图称为平凡树． 树的等价定义 G中任意两个顶点之间存在惟一的路径． G中无回路且 m = n - 1． G是连通的且 m = n - 1． G中没有回路，但在任何两个不同的顶点之间加一条新边， 在所得图中得到惟一的一个含新边的初级回路． G是连通的，但删去任何一条边后，所得图不连通． 特征是：连通、无回路、边数=结点数-1 在无向树中：悬挂顶点（度为1）称为树叶 度数大于或等于2的顶点称为分支结点． 2）树的性质 给定的无向图—树是边数最小的连通图（mn-1则不连通） 树是边数最多的无回路图（mn-1则有回路） 无向树结点的度： Σd(vi) = 2 m =2(n-1) T是n阶非平凡的无向树，则T中至少有两片树叶 二、生成树 一些连通图不是树，但子图是树-重要的是生成树 1、定义：设T是无向图G的子图并且为树，则称T为G的树 若T是G的树且为生成子图，则称T是G的生成树 T是G的生成树，则称T的边e为T的树枝 否则称e为T的弦（虚线）． 并称由弦导出子图G[E(G)—E(T)]为T的余树， 记作T （T不一定连通，也可能含有回路） 2、生成树的性质 定理：无向图G具有生成树当且仅当G是连通图 设G为n阶m条边的无向连通图，则m =|E(G)|≥|E(T)| = n - 1 设G是n阶m 条边的无向连通图，T为G的生成树 则T的余树T中含m - n十1条边(即T有m—n+1条弦) 3、任何无向连通图G都存在生成树 无向连通图G的生成树是不唯一的 实边图为该图的一棵生成树T， 余树T为虚边所示，它不连通，同时也含回路 4、无向图G的生成树的确定： 二种方法：1、破圈法：每次去掉回路中的一条边， 去掉总数为 m-n+1 条弦 2、避圈法：由一个结点开始选一条边， 逐加与边关联的结点（只要不构成回路即可） 直到所有结点被添加 5、带权图的最小生成树 (1) 定义5 设无向连通带权图：G＝V ，E，W ，T是G的一棵生成树． T的各边权之和称为T的权，记作W(T)； G的所有生成树中权最小的生成树称为G的最小生成树 (2) 最小生成树的求法（这里介绍避圈法Kruskal算法) 设n阶无向连通带权圈G ＝ V ，E, W 有m条边． 不妨设G中没有环(否则，可以将所有的环先删去)，将m条边按权从小到次顺序排列，设为e1,e2，…,em 取e1在T中，然后依次检查e2，e3，…，em.若ej(j≥2)与已在T中的边 不能构成回路，则取ej在T中，否则弃去ej． 算法停止时得到的T为G的最小生成树