树的边带宽与叶子数

图G边的一个标号f是指边集E(G)到集合{1,2,…,m}之间的一个一一映射,即:e∈E(G),■t,1≤t≤m,使得f(e)=t.图G的边带宽B'(G)=min B_f'(G),其中B_f'(G)=max{|f(uv)-f(uw)|:uv,uw∈E(G)}.给出树T的边带宽满足「(m-1)/(d-1)」≤B'(T)≤l-s,0≤s≤l/2,其中d为树T的直径,l为树T的叶子数.而且k(为偶数)元正则树的边带宽B'(T*)≤l/2,广义星图T*的边带宽B'(T*)=l或l-1.

度序列与树中的叶子数

给出了树的度序列与叶子总数之间的关系式 ,从而得到一种精确地计算树的叶子数的方法 ,并证明了结论 :度序列满足该关系式的简单连通图必是树 .对树形图中的度序列和叶子数也有类似的结果 .

基于一道二叉树习题的教学案例辨析

二叉树的教学后,布置了一道习题要学生设计算法求二叉树的叶子数,算法的本质思想是在二叉树的遍历过程中对二叉树的结点进行判断并对叶子结点进行统计。二叉树遍历的方式较多,难易不同,算法的设计有所区别;学生初次接触层次结构的习题,觉得无从下手,最后把这道习题改成习题课,经过分析归纳了五种不同类型的十一个设计方法,从而启迪学生的思维,调动了学生学习热情和积极性,达到引导学生勇于探索的教学目的。

无向图可迹的一个充分条件

无向图G是简单连通图,且最小度为δ.如果G中包含一条生成路,则G是可迹的.无向图G的叶子数L(G)是G中生成树所含的叶子数的最大数.基于L(G)和δ,证明了一个充分条件使得无向图G是可迹的,即设G为连通图,最小度为δ≤4.若δ≥(1/2)(L(G)+2),G是可迹的.