离散数学课件-第七章-树trees

第7章树trees分类根树有序树定位树无向树标号{a,b}无有无有无有无有N=1N=2N=3§7.1树定义1：T是集合A上一个二元关系，T称为树tree，如果存在v0∈A，任意v∈A，v≠v0，到v0都有唯一一条路径，（v0,v0）T.T叫做根树，记做（T，v0）。A中元素称为T的顶点vertex，T中元素称为边，v0称为根root。定理1.设（T，v0）是树，则(a)T中没有回路。(b)只有一个根v0。(c)任意v∈A，v≠v0，v有入度1，v0入度是0。证明：定义2层次levelv0的层次为0，v0的子女offspring层次为1，v0是子女的父母parent。vi的层次为k，vi的子女offspring层次为k＋1，vi是子女的父母parent，T的最大层次称为高度height。无子女的顶点叫叶leaf。vi的子女叫同胞sibling，同胞如有长幼，从左到右，老大，老二，老三等，组成线性序，T称为有序树，orderedtree定理2.设（T，v0）是根树，则(a)T反自反。(b)T反对称。(c)(a,b)∈T，(b，c)∈T(a，c)T。定义3：n－树：每个顶点至多n个子女。二叉树：2－树。完全n－树：每个非叶顶点恰有n个子女。定义4Arootedbinarytreeisarooted\o"Treedatastructure"treeinwhicheverynodehasatmosttwochildren.Afullbinarytree(sometimesproperbinarytreeor2-tree)isatreeinwhicheverynodeotherthantheleaveshastwochildren.Aperfectbinarytreeisafullbinarytreeinwhichallleavesareatthesamedepthorsamelevel.[1](Thisisambiguouslyalsocalledacompletebinarytree.)Acompletebinarytreeisabinarytreeinwhicheverylevel,exceptpossiblythelast,iscompletelyfilled,andallnodesareasfarleftaspossible.[2]Aninfinitecompletebinarytreeisatreewithlevels,whereforeachleveldthenumberofexistingnodesatleveldisequalto2d.Thecardinalnumberofthesetofallnodesis.Thecardinalnumberofthesetofallpathsis.Abalancedbinarytreeisatreewherethedepthofallthesub-treesdiffersbyatmost1.定理3.设（T，v0）是根树，v∈T，则T(v)是T的子树，T(v)的根是v。HomeworkP248－24918，19，20，21，26，28§7.2标识树labeledtrees中缀表达式centraloperatorexpression（3－2×x）＋（（x－2））＋（3＋x））定位树positionaltree定义Positionaln-treeisan-treewhosevertexpotentiallyhasexactlynoffspringorderedby1,2,…,n,butsomeoftheoffspringsmaybemissing.定位3－树每个顶点的子女都有一定位置。定位2－树左右子树普通二叉树。问题7.2.1n个节点的定位二叉树有多少个？如何枚举？定位二叉树的计算机表示ComputerRepresentationofBinaryPositionalTreesIndexLeftDataRight12start026＋337+4483550x0610-12711-098030902010030110x01214×13130x014020HomeworkPP253－25410，11，12，16，18，§7.3树的遍历treesearching（自学）二叉树的遍历中序遍历的递归算法定义(1)遍历左子树；(2)访问根结点；(3)遍历右子树。先序遍历的递归算法定义(1)访问根结点；(2)遍历左子树；(3)遍历右子树。后序遍历得递归算法定义(1)遍历左子树；(2)遍历右子树；(3)访问根结点树的搜索深度优先搜索广度优先搜索启发式搜索博弈树搜索§7.4无向树undirectedtrees无向图连通不含回路的图叫无向树例bbfgdcea无向树：有向树的对称闭包。定义：有向树的对称闭包。定理1.R是对称关系。则下列命题等价thefollowingstatementareequivalent：（TFAE）a)R是无向树。b)R连通connected，无回路acycle。证明：b)R显然连通若R有回路a)若R连通无回路，我们可以在R上构造一棵树。定理2.R是对称关系。TFAER是无向树。R无回路，每增加一条边，都产生一个新的回路。证明：R连通，所以没加一边都有新的回路若R不连通则有两个以上连通分支，所以可以加一边不产生回路R连通，去掉任意一条边都不连通。证明：若去掉一边还连通，则原图一定有回路。若原图有回路，则可以去掉一边后仍连通。R无回路，且有n-1条边对定点做归纳即可得边数为n-1若原图不连通，则有k个连通分支，每支都是树，总边数为n-k。R连通，且有n-1条边若原图有回路，则删掉k条边后为树，则总边数为n-1+k连通图的生成树spanningtree:定义含有所有顶点的极小连通图.存在性n个顶点连通图至少有n-1条边。m条边的连通图去掉m－n＋1条边可以得到生成树。从连通图中如有回路，去掉回路中的一条边，继续直至没有回路，就得到生成树唯一性最小生成树：权重最小的生成树。带权的边：带边长的边。带权的图：每边都带权。Prim算法：设G=<V,E>,1.U={v0},W=V-U,T={}.2.U=U∪{v1},W=W-{v1},T=T∪{(u1,v1)}3.重复2，直至U=V.例UABCDEFu1v1TKruskal克鲁斯卡尔算法G=(V,E)连通图令T=(V,{})是G的所有顶点而无边的非连通图。选择E中权值最小的边，若该边连接T的两个连通分量，将它加入T,这时T的连通分量减少1；否则选下一条权值最小的边。3重复1n-1次直到T连通。T就是最小生成树ACDFBECFADCDBCABCEEF1234555666ABCDEF123456其他相关内容介绍最快的算法Thefastestminimumspanningtreealgorithmtodatewasdevelopedby\o"BernardChazelle"BernardChazelle,whichisbasedonthe\o"Softheap"softheap,anapproximatepriorityqueue.[1][2]Itsrunningtimeis\o"BigOnotation"O(m

α(m,n)),wheremisthenumberofedges,nisthenumberofverticesandαistheclassicalfunctionalinverseofthe\o"Ackermannfunction"Ackermannfunction.Thefunctionαgrowsextremelyslowly,sothatforallpracticalpurposesitmaybeconsideredaconstantnogreaterthan4;thusChazelle'salgorithmtakesveryclosetolineartime.Degree-constrainedspanningtreeInput:n-nodeundirectedgraphG(V,E);positive\o"Integer"integerk≤n.Question:DoesGhaveaspanningtreeinwhichno\o"Node(computerscience)"nodehasdegreegreaterthank?Degree-constrainedspanningtreeproblemisNPCDirectedminimumspanningtreeEdmonds'salgorithmO(EV)1986,Gabow,Galil,Spencer,andTarjanO(E+VlogV).求从点1出发的最小树形图对除1以外的每个点，选一条指向它的最小权的边。将所得到的图为G，其对应的无向图为H若H连通，则已经找到。否则H的每个连通分支，要么是从点1出发