《第8章 树.ppt》由会员分享，可在线阅读，更多相关《第8章 树.ppt（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 第第8章章 树树 8.1 8.1 树的基本性质树的基本性质 定义定义8.18.1树树:树是不包含回路的连通图。树是不包含回路的连通图。在在 图图 8.18.1中中 图图 8.18.1（a a）是是 树树，图图 8.18.1（b b）、图图8.18.1（c c）不是树。）不是树。（a）（b）（c）图图8.1 树与非树的例图树与非树的例图1 第第8章章 树树 树的三个基本特性树的三个基本特性:定理定理8.1:8.1:在（在（n n，m m）树中必有）树中必有m mn1n1 定定理理8.2:8.2:树树是是最最小小连连通通图图，最最大大无无回回路路图图，即即在在树树中中增增加加一一条条边边，得得到
2、到并并仅仅得得到到一一条条回回路路，树树删删去去一一条条边就不再连通。边就不再连通。定定理理8.3:8.3:图图G G是是树树的的充充分分必必要要条条件件是是图图G G的的每每对对结结点点间只有一条通路。间只有一条通路。2 第第8章章 树树 8.2 8.2 有向树有向树 定定义义8.28.2有有向向树树:在在有有向向图图中中如如果果不不考考虑虑边边的的方方向向而而构成树，则称此有向图为有向树。构成树，则称此有向图为有向树。图图8.28.2（a a）为有向树，图）为有向树，图8.28.2（b b）不是有向树。）不是有向树。（a a）（b b）图图8.2 8.2 有向树与非有向树实例有向树与非有向
3、树实例 3 第第8章章 树树 定义定义8.3:8.3:外向树外向树:满足下条件的有向树满足下条件的有向树T T为外向树。为外向树。（l l）T T有有一一个个结结点点（也也仅仅有有一一个个）它它的的引引入入次次数数为为0 0，这个结点称为这个结点称为T T的根；的根；（2 2）T T的其他结点的引入次数均为的其他结点的引入次数均为1 1；（3 3）T T有有一一些些结结点点，它它的的引引出出次次数数为为00这这些些结结点点称称为为T T的叶。的叶。图图8.38.3给出了外向树的例子。给出了外向树的例子。图图8.3 外向树例图外向树例图 4 第第8章章 树树 在在外外向向树树中中，非非根根非非叶
4、叶的的结结点点称称为为分分支支结结点点，在在分分支结点中它的引入次数及引出次数均不为支结点中它的引入次数及引出次数均不为0。定定义义8.4外外向向树树的的级级:由由外外向向树树的的根根到到结结点点vl的的通通路路长长度称为结点度称为结点vi的级。的级。例：可用外向树表示家属关系。设有某祖宗a生两个儿子：b及c，b与c又分别生三个儿子，它们分别为d、e、f及g、h、i，而d与g又分别生了一个儿子，它们是j与k，这样的家属关系可用图8.5所示的外向树表示，它称为家属材树。5 第第8章章 树树 由于可用外向树表示家属关系，由于可用外向树表示家属关系，故现在一般均用家属关系中的故现在一般均用家属关系中
5、的术语来称呼外向树中结点间的术语来称呼外向树中结点间的关系。外向树中如从结点关系。外向树中如从结点a到到b有一条边，则称有一条边，则称b是是a的儿子，的儿子，而称而称a是是b的父亲或双亲（父、的父亲或双亲（父、母母）。外外向向树树中中从从结结点点a到到b及及a到到c均均有有一一条条边边，则则称称b、c为为兄兄弟弟，从从结结点点a至至结结点点f有有一一条条有有向向通通路路，则则称称f是是a的子孙，而称的子孙，而称a是是f的祖先。的祖先。a b cde f g h ij k 图图8.5 家属树例图家属树例图6 第第8章章 树树 由家属树所引出的第二个概念是关于有序树的概念。由家属树所引出的第二个概
6、念是关于有序树的概念。在家属树中兄弟间是有一定次序的，老大、老二、老在家属树中兄弟间是有一定次序的，老大、老二、老三三等等，它们是不能随意颠倒的。如等等，它们是不能随意颠倒的。如e与与d是不能是不能相互替代的，因为相互替代的，因为d有儿子有儿子j，而而e无儿子，这给我们无儿子，这给我们一个启示，在有些外向树中需要对每个分支结点（及一个启示，在有些外向树中需要对每个分支结点（及根）的儿子顺序编号。如一结点有三个儿子，则从左根）的儿子顺序编号。如一结点有三个儿子，则从左到右可编以到右可编以1、2、3，也可以编成，也可以编成1、3、5等等。图等等。图8.6（a）、（）、（b）给出了有序树的两个实例。
7、）给出了有序树的两个实例。7 第第8章章 树树 1 2 3 1 2 3 5 1 2 （a）（b）图图8.6 有序树实例有序树实例8 第第8章章 树树我们还可以用类似的方法定义内向树：我们还可以用类似的方法定义内向树：（1）T有有一一个个结结点点（也也仅仅有有一一个个结结点点）它它的的引引出出次次数为数为0，这个结点称为，这个结点称为T的根；的根；（2）T的其他结点引出次数均为的其他结点引出次数均为1；（3）T有有一一些些结结点点，它它的的引引入入次次数数为为0，这这些些结结点点称称为为T的叶。的叶。图图8.7给出了内向树的例子给出了内向树的例子.9 第第8章章 树树图图8.7 内向树例图内向树
8、例图10 第第8章章 树树 8.3 8.3 二元树二元树 定义定义8.5 8.5 m m元树元树:n n个结点的外向树如满足：个结点的外向树如满足：degdeg（v vi i）mm，（，（i il l，2 2，3 3，n n）则称此外向树为则称此外向树为m m元树。元树。如满足（除叶外）：如满足（除叶外）：degdeg（v vi i）m m，（，（i il l，2 2，3 3，n n）则称此外向树为则称此外向树为m m元完全树。元完全树。当当m m2 2时则分别称为二元树及二元完全树。时则分别称为二元树及二元完全树。11 第第8章章 树树图图8.8（a）、（b）、（c）、（d）分分别别给给出出
9、了了四四元元树、四元完全树、二元树及二元完全树的例子。树、四元完全树、二元树及二元完全树的例子。（a）（b）（c）（d）图图8.8 m元树例图元树例图12 第第8章章 树树 8.4 8.4 生成树生成树 定定义义8.68.6生生成成树树：连连通通图图G GVE的的生生成成树树T TG GV 是是G G的子图，它是树，且有的子图，它是树，且有V V V V，E E E E。定理定理8.48.4：连通图连通图G G至少有一棵生成树。至少有一棵生成树。算法算法8.18.1 生成树的寻找算法。生成树的寻找算法。由一个连通图由一个连通图G G寻找它的生成树的算法是：寻找它的生成树的算法是：（1 1）G
10、G是是否否有有回回路路，若若无无回回路路则则G G就就是是生生成成树树；若若有有回路则转（回路则转（2 2）（2 2）删删除除回回路路中中一一条条边边，再再判判别别之之，若若有有回回路路，继继执行（执行（2 2），若无回路则转（），若无回路则转（3 3）（3 3）算法结束，所得的图即为生成树。）算法结束，所得的图即为生成树。13 第第8章章 树树 例：设有六个城市v1，v2，v6，它们间有输油管连通，其布置图如图9.14（a）,为了保卫油管不受破坏，在每段油管间须派一连士兵看守，为保证正常供应最少需多少连士兵看守？他们应驻于哪些油管处？（a）（b）（c）（d）图图8.14 例例8.8之图及生成
11、树之图及生成树14 第第8章章 树树 定定义义8.7最最小小生生成成树树：图图G的的生生成成树树中中其其权权之之和和为为最最小的生成树叫最小生成树。小的生成树叫最小生成树。算算 法法 8.2最最 小小 生生 成成 树树 寻寻 找找 算算 法法 克克 鲁鲁 斯斯 克克 尔尔（Kruskal）算法：）算法：（1）在在（n，m）图图G中中先先将将所所有有m个个边边按按权权值值大大小小顺顺序序放放入入专专用用表表内内，此此时时G中中只只剩剩n个个结结点点，选选最最小小权的边权的边e1至至G，置置i=1；（2）当当i=n-1时结束，否则转（时结束，否则转（3）；）；（3）已已选选e1，e2，ei，此此时
12、时选选ei+1为为剩剩余余边边中权最小者且加入后不构成回路；中权最小者且加入后不构成回路；（4）置）置i=i+1转（转（2）。）。15 第第8章章 树树例：在上面例子中我们希望所选择的生成树使它的总长度最短，这样就更便于守卫，这个问题即是最小生成树问题，为了讨论这个问题，首先对图中的每个边必须赋以一个权。在上例中，这个权即是两城市间的距离，我们用图8.15（a）表示，对每条边按距离长短顺序排列得到表8.2，然后按表8.2排定的次序将边加入仅有六个结点的图中，如出现回路则另选一个边，这样加入n1个边后即得最小生成树。图8.15（b）8.15（i）给出了此过程。16 第第8章章 树树 表表8.2
13、8.2 例中各边按距离长短排列表例中各边按距离长短排列表 顺顺 序序1 2 3 4 5 6 7 8 9 10 11 边边 S2 S6 S1 S3 S7 S9 S8 S4 S10 S11 S5 权权 1 1 2 2 2 2 3 4 4 4 5 17 第第8章章 树树S1（2）S（2）v1 v2 v1 v2S2 S4 S5 S3v3 S6 v4 v3 v4 S11 S10S7 S8v5 v6 v5 v6 （a）（b）(1)(5)(4)(2)(1)(2)(4)(4)(3)v1 v2v3 v4v5 v6S2(1)S6（1）v1 v2v3 v4v5 v6S2(1)（c）（d）18 第第8章章 树树S6（1）v1 v2v3 v4v5 v6S2(1)S1(2)S6（1）v1 v2v3 v4v5 v6S2(1)S1(2)(2)S3S6（1）v1 v2v3 v4v5 v6S2(1)S1(2)S6（1）v1 v2v3 v4v5 v6S2(1)S1(2)S7(2)S6（1）v1 v2v3 v4v5 v6S2(1)S1(2)S7(2)(2)S9（e）（f）（g）（h）（i）19