离散数学图论.ppt

《离散数学图论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三十二讲图论7-8根树及其应用上节知识回顾图G=，其中V是非空点集，E是边集无向图有向图连通图非连通图树：是一种特殊的图无向树有向树2上节知识回顾7-7无向树及其性质定义7-7.1连通无回路的无向图称为无向树，简称树,常用T表示树。平凡图称为平凡树。若无向图G的每个连通分支都是树，则称G为森林。在无向树中，度为1的结点称为树叶，度数大于或等于2的结点称为分枝点或内点。。。。。。。。。。。。。。。3上节知识回顾定理7-7.1设G=是n阶m条边的无向图,则下面各命题是等价的：（1）G是树。（2）G中任意两个结点之间有且仅有一条

2、路。（3）G中无回路且m=n-1。（4）G是连通的且m=n-1。(5)G是连通的且G中任何边均为桥。(6)G中没有回路，但在任何两个不同的结点之间加一条新边，在所得的图中得到唯一的一个含新边的圈。。。。。。。47-8根树及其应用1、根树的相关定义2、根树的性质及应用——二叉树、m叉树3、小结本节内容安排5第七章图论定义7-8.1设D是有向图，若不考虑D图边的方向时是一棵无向树，则称D为有向树。V1。V2。V5。V3。V4。V6。V7。V8。V9。如：结点度的概念如前所讲6第七章图论设T是n(n≥2)阶有向树，若T中恰好有一个结点的入度为0，其余

3、结点的入度均为1，则称T为根树定义7-8.2——根树入度为0的结点称为根层次最大结点的层次称为树高入度为1出度为0的结点称为叶出度不为0的结点称为内点或分枝点从树根到T的任意结点v的单向通路长度称为v的层次定义7-8.3：根树包含一个或多个结点，这些结点中某一个称为根，其他所有结点被分成有限个子根树平凡树也称为根树。V1。V2。V5。V3。V4。V6。V7。V8。V9。。。。。。。。。。。。7第七章图论由于各有向边的方向一致，故常省略，并且树根在最上方。V1。V2。V5。V3。V4。V6。V7。V8。V9。V1。V2。V5。V3。V4。V6。V

4、7。V8。V9。。。。。。。。。。V1V2V3V4V5V6V7V8V9在根树中，若将T中层数相同的结点都标定次序，则称T为有序树。根树的不同画法：8第七章图论设T为一棵非平凡的根树，vi,vj∈V(T),若vi可达vj,则称vi为vj的祖先,vj为vi的后代若vi邻接到vj（即∈E(T)），则称vi为vj的父亲，而vj为vi的儿子若vj,vk的父亲相同，则称vj与vk是兄弟。补充定义V1。V2。V5。V3。V4。V6。V7。V8。V9。9第七章图论定义7-8.4在根树T中，若每个结点的出度的小于或等于r，则称T为r叉树。若每个结

5、点的出度恰好等于r或0，则称T为完全r叉树。若完全r叉树所有树叶层次相同，则称T为正则r叉树。当r=2时，称为二叉树。10第七章图论例：。。。。。。。。。。。。。。。。二叉树?正则二叉树?请证明在完全二叉树中，边的总数等于2(nt-1)，nt为树叶数。。。。。。。。。完全二叉树?11第七章图论二叉树在实际生活中应用广泛。例如：M和E两人进行象棋比赛，规定一人连胜两盘或共胜三盘即为获胜，则所有可能的比赛结果可用如下二叉树来描述。。。。。。。。。。。。。。。。。。。。在m叉树中，二叉树相对来讲比较容易处理，所以常常把m叉树的问题转换到二叉树上来讨论

6、。比赛开始12第七章图论根树应用1：一棵m叉有序树改写为一棵二叉树方法任何一棵有序树都可以改写为一个对应的二叉树：除了最左边的分枝结点外，删去所有从每一个结点长出的分枝。在同一层次中，兄弟结点之间用从左到右的有向边连接。选定二叉树的左儿子和右儿子如下：直接处于给定结点下面的结点，作为左儿子，对于同一水平线上与给定结点右邻的结点，作为右儿子，依次类推。13第七章图论例：把下面的m叉树改写为二叉树。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。除了最左边的分枝结点外，删去所有从每一个结点长出的分枝在同一层次中，兄弟结点之间用从左到

7、右的有向边连接直接处于给定结点下面的结点，作为左儿子，对于同一水平线上与给定结点右邻的结点，作为右儿子14第七章图论练习：把下面的有序树改写为二叉树。。。。。。。。。。。。。。。。。。知识点提示：此方法可推广至有序森林到二叉树的转换。此方法具有可逆性。课下自学15第七章图论定理7-8.1设有完全m叉树，共有t片树叶，i个分枝点，则(m-1)i=t-1。证明：完全m叉树中结点总数为:t+i也可表示为mi+1故得(m-1)i=t-1根树应用2：完全m叉树的应用。。。。。。。。。16第七章图论例：有28盏灯，拟用一个电源插座，问至少需要多少块四插座的

8、接线板？解：将四叉树的每个分枝点看作是四插座的接线板，树叶看作是灯，则根据定理7-8.1可知需要9块。请思考？分析：四插座——m叉树——m接线板——分