离散数学图论.pptVIP

信息科学与工程学院第四部分*离散数学图论*第1页，共31页，星期日，2025年，2月5日上节知识回顾图G=V,E，其中V是非空点集，E是边集无向图有向图连通图非连通图树：是一种特殊的图无向树有向树*第2页，共31页，星期日，2025年，2月5日上节知识回顾7-7无向树及其性质定义7-7.1连通无回路的无向图称为无向树，简称树,常用T表示树。平凡图称为平凡树。若无向图G的每个连通分支都是树，则称G为森林。在无向树中，度为1的结点称为树叶，度数大于或等于2的结点称为分枝点或内点。。。。。。。。。。。。。。。*第3页，共31页，星期日，2025年，2月5日上节知识回顾定理7-7.1设G=V,E是n阶m条边的无向图,则下面各命题是等价的：（1）G是树。（2）G中任意两个结点之间有且仅有一条路。（3）G中无回路且m=n-1。（4）G是连通的且m=n-1。(5)G是连通的且G中任何边均为桥。(6)G中没有回路，但在任何两个不同的结点之间加一条新边，在所得的图中得到唯一的一个含新边的圈。。。。。。。*第4页，共31页，星期日，2025年，2月5日7-8根树及其应用1、根树的相关定义2、根树的性质及应用——二叉树、m叉树3、小结本节内容安排*第5页，共31页，星期日，2025年，2月5日第七章图论定义7-8.1设D是有向图，若不考虑D图边的方向时是一棵无向树，则称D为有向树。V1。V2。V5。V3。V4。V6。V7。V8。V9。如：结点度的概念如前所讲*第6页，共31页，星期日，2025年，2月5日第七章图论设T是n(n≥2)阶有向树，若T中恰好有一个结点的入度为0，其余结点的入度均为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页，共31页，星期日，2025年，2月5日第七章图论由于各有向边的方向一致，故常省略，并且树根在最上方。V1。V2。V5。V3。V4。V6。V7。V8。V9。V1。V2。V5。V3。V4。V6。V7。V8。V9。。。。。。。。。。V1V2V3V4V5V6V7V8V9在根树中，若将T中层数相同的结点都标定次序，则称T为有序树。根树的不同画法：*第8页，共31页，星期日，2025年，2月5日第七章图论设T为一棵非平凡的根树，?vi,vj∈V(T),若vi可达vj,则称vi为vj的祖先,vj为vi的后代若vi邻接到vj（即vi,vj∈E(T)），则称vi为vj的父亲，而vj为vi的儿子若vj,vk的父亲相同，则称vj与vk是兄弟。补充定义V1。V2。V5。V3。V4。V6。V7。V8。V9。*第9页，共31页，星期日，2025年，2月5日第七章图论定义7-8.4在根树T中，若每个结点的出度的小于或等于r，则称T为r叉树。若每个结点的出度恰好等于r或0，则称T为完全r叉树。若完全r叉树所有树叶层次相同，则称T为正则r叉树。当r=2时，称为二叉树。*第10页，共31页，星期日，2025年，2月5日第七章图论例：。。。。。。。。。。。。。。。。二叉树?正则二叉树?请证明在完全二叉树中，边的总数等于2(nt-1)，nt为树叶数。。。。。。。。。完全二叉树?*第11页，共31页，星期日，2025年，2月5日第七章图论二叉树在实际生活中应用广泛。例如：M和E两人进行象棋比赛，规定一人连胜两盘或共胜三盘即为获胜，则所有可能的比赛结果可用如下二叉树来描述。。。。。。。。。。。。。。。。。。。。在m叉树中，二叉树相对来讲比较容易处理，所以常常把m叉树的问题转换到二叉树上来讨论。比赛开始*第12页，共31页，星期日，2025年，2月5日第七章图论根树应用1：一棵m叉有序树改写为一棵二叉树方法任何