直径为4的双星图的谱排序

介绍了一类直径为4的n阶树即双星图T(a,b)的谱随a变化的规律,其中a≥b≥1,a+b+3=n,n 2-3≤a≤n-4;得到了双星图T(a,b)的邻接谱半径、Laplace谱半径以及代数连通度均随a的值递增的结论,并在此基础上对这类树进行了排序。     

一种变形对树的代数连通度的影响

设T是一个树,uv是T的一条边,其中d(v)=2.考虑经过一种特殊的变形后树的代数连通度的变化为:收缩边uv,并以收缩后的点u(v)为端点增加一条新的悬挂边,这样得到的新树记为T′,则α(T)≤α(T′).     

图与其补图Q谱半径之和的上界

设G为n阶简单图,利用边数m,最小、最大顶点度δ和Δ以及色数k给出了G与其补图-G的Q谱半径之和的上界,当G不含孤立点时有:2(n-1)≤ρ(Q(G))+ρ(Q(-G))≤2(Δ-δ+n-1)和ρ(Q(G))+ρQ(-G))≤2n-3+2-12(n-1)n,其中t=min{k,-k}。当-G含l个孤立点时有:ρ(Q(G))+ρ(Q(-G))≤2n-3+2-1k(n-1)2+l,同时给出了图G与其补图-G的拉普拉斯谱半径之和的一个上界。     

关于子图参数的内插问题

设 G_1和 G_2是图 G 的两个子图,G_1和 G_2对应的某个参数的值分别为非负整数 m 和 n,且 m相似文献   

C.Thomassen猜想的证明

证明了若G是3连通无爪图，且G的每个同构于A的导出子图都满足φ（α1，α2），则G是泛连通图（除了u,v∈V（G），d(u,v)=1时，G中可能不存在（u,v)-k路外）。由此立得C.Thomassen猜想：每个4个连通线图均是Hamilton图。     

一类3-正则3-连通平面Hamilton图

设Γk 是由带如下结构的3-正则3-连通平面图G所组成的图类G中含一个圈C,使得G-E(C)产生k个不相交的树,并且每个树具有至少三条边.本文证明了Γ1 中所有的图都是Hamilton图.     

一类3-正则3-连通平面Hamilton图

设Гk由带如下结构的3-正则3-连通平面图G所组成的图类：G中含一个圈C．使得G—E（C）产生女个不相交的树，并且每个树具有至少三条边．本文证明Г1中所有的图都是Hamilton图．     

色多项式与图的平面性

设图G的色多项式为P（G，λ），α1(G)是P（G，λ）中λ项的系数的绝对值，本文证明了：若1≤α1(G)≤23，则图G是连通的平面图。     

哈密尔顿连通图与邻域并条件

记G＝(V，E)表示简单图，NC＝min{|N(x)∪N(y)|:x,y∈V(G),xy∈E(G)},NC2=min{|N(x)∪N(y)1:x,y∈V（G),d(x,y)=2}。1989年Faudree等4个美国著名图论专家研究课题NC≥(2n 1)／3的哈密尔顿连通图，得到：若3连通n阶图G，NC≥(2n 1)／3，则G是哈密尔顿连通图。本文进一步研究NC2≥(2n 1)／3的哈密尔顿连通图，得到界为最好的结果：若3连通n阶通图G，NC2≥(2n 1)／3，则G是哈密尔领连通图。而且本文的证明极其简捷。     

对边幻图猜测的一个证明

令简单图G =(V ,E)是有 p个顶点 q条边的图。假设G的顶点和边由 1 ,2 ,3 ,… ,p + q所标号 ,且 f :V∪E { 1 ,2 ,… ,p + q}是一个双射。如果对所有的边xy ,f(x) + f(y) + f(xy)是常量 ,则称图G是边幻图 (edge-magic)。毛毛虫图是一个树 ,移走它的所有端点产生一个路 (称为T的脊或主干 )。例如 ,路和星图是毛毛虫图。证明了毛毛虫图是边幻图 ,从而证明了顶点不超过 8的树是边幻图。     

并行处理中树图到超立方体映射问题的矩阵分析

讨论了树型任务图到超立方体的映射问题．基于矩阵分析的方法,建立了以二项树为数据结构的嵌入算法．该算法利用了特殊矩阵的某些性质,克服了以往采用双根树的缺点,使嵌入过程易于自动实现．     

一种多模式匹配高效算法的设计与实现

随着国家信息化的不断推进和计算机网络飞速发展,网络信息安全审计成为网络信息安全中不可或缺的重要组成部分．网络信息安全审计系统从网络关键点采集数据包,对其传送内容进行审计分析,达到网络信息内容的监控．在网络信息安全审计系统中,需要对大量的关键字进行匹配,匹配算法的性能极大程度地影响了整个审计系统的性能．通过比较分析现有的多模匹配算法,设计实现了一种基于二叉树多模匹配的算法,并在最后通过实验测试,得到了良好的性能指标．     

一种改进的NJ方法及其应用

传统的邻接法(Neighbor-joining Method,简称NJ)存在"Tied trees"问题,即它从同一数据集中产生的进化树可能不唯一.为解决这一问题,提出了一种改进的NJ方法——INJ,该方法利用速率校正距离把多个最近的种群进行合并,并从理论和应用上说明INJ产生的进化树具有更好的唯一性,而且在NJ树唯一时,INJ树和NJ树完全相同.因此在传统NJ算法产生的二叉树不唯一时,INJ算法也能产生一棵具有唯一拓扑结构的多叉树.     

分布式决策树算法研究与实现

提出了一种基于分布多库环境下的决策树生成算法DDTA（Distributed Decision Tree Algorithm）．该算法使用基于信息熵增益的思想分割各个分布的、同构训练样本集,各分布站点利用服务器传来的分割属性分割自己的样本集,服务器则通过对所有分布站点传来的信息计算各个属性的信息熵增益得到分割属性．实验表明DDTA算法能对分布同构样本集进行有效决策树挖掘,分布多库环境下生成的决策树是正确的．与算法INDUS相比,该算法的通信代价小．     

树状网络上k-tree center问题

树状网络上的k-tree center问题是指在树上选择一棵叶子数恰好为k的子树,使得树上其他节点到该子树的最大距离最小化。由于center问题的目标函数是满足最大距离最小化,如果S是问题的最优解,则S肯定包含树的中心,因此在求解k-tree center问题时,首先找到树的中心,然后从中心出发,利用树收缩的思想逐步找到满足要求的子树。该文基于此对该问题给出了时间复杂度为O(kn)的多项式时间算法。     

基于XML的学习流模型

在学习流理论的基础上,采用XML规范来实现学习流模型.利用树空间具有层次关系清晰、体系可扩展、定位方式多样、新技术规范及便于技术实现等优点,把复杂知识体系映射到树状结构空间中,以构建学习流模型.给出了模型结构的XML描述.该模型的构建为教学信息网络的计算机控制和管理提供了一种新的方法.     

一种构建严格平衡二叉搜索树的非递归算法

针对传统算法所构造的平衡二叉搜索树并非真正平衡的二叉搜索树,设计了一种构建严格平衡二叉搜索树的非递归算法。改进后的算法具有计算速度快、占用内存小、计算机易于实现等优点。改进算法的核心是生成严格二叉搜索树的先序序列,提出了对升序序列的进行二分得到严格二叉搜索树的先序序列,讨论并给出了构建严格二叉搜索树的快速算法,该算法充分利用了栈在计算过程中提供的二分信息得到严格二叉搜索树的先序序列,该算法与传统算法相比可更快地构建严格二叉搜索树。     

均衡Huffman树的构造算法

给出了一种构造均衡Ｈｕｆｆｍ ａｎ 树的算法,并给出了算法正确性的证明     

Ballot序列和一类二元树的表示

本文从Ballot序列出发推广定义了广义Ballot序列,利用它来表示一类具有n内节点的二元树,并且给出了自动生成广义Ballot序列和n内节点二元树的有效算法。文中还解决了对n内节点二元树的计数问题。     

基于攻防行为树的网络安全态势分析

现代网络面临遭受组合攻击的风险,通过构建基于攻防行为的安全态势分析模型来对每一个独立及组合攻击行为进行威胁分析十分必要。本文针对传统的攻击树模型没有考虑防御因素影响,防御树模型缺乏较好的可扩展性,故障树模型难以对外部攻击进行分析等问题,在攻击树模型中引入博弈论,以描述具体网络攻防事件场景。首先,分析网络中不同层次攻击行为的逻辑关系,整合不同层次攻击事件对应的攻防树,获得完整网络攻防行为树,进而构建网络攻防行为树模型。其次,从网络攻防行为、网络检测设备以及网络防御措施3方面对基本攻防行为树进行扩展,提出攻击目标成功率算法,计算其攻击概率。在此基础上,对攻击威胁进行评估,分析网络安全态势。最后,为验证网络攻防行为树模型的可行性和有效性,在BGP（border gateway protocol）攻击树的基础上构建攻防行为树模型,通过概率计算可知：攻击路径PATH1概率最大;且在没有防御措施的情况下,5条攻击路径的攻击成功率均得到增大,PATH2至PATH5概率增大倍数显著高于PATH1,与实际相符。本文所提的网络攻防行为树模型能很好地计算各种防御措施的效果,且能够在任意节点添加和删除攻防行为,具有较强的可扩展性,可为网络管理者与运营者提供科学的决策依据。