一类树的SL谱刻画

图的谱理论是图论与组合矩阵论的一个重要研究领域。设图G是一个有n个顶点、m条边的简单图,Q（G）为图G的无符号拉普拉斯矩阵,树图是图论研究的一类重要的图,为了确定一类树的sL谱惟一性,利用图与同谱图之间的关系,运用删边缩边原理,探讨了两组顶点数目的树图。通过比较两组图中子树数目的大小逐项排除和删边删点的方法证明了一类树的SL谱惟一性。     

近完全图的不同构图确定和计数的研究

本文首次定义了近完全图的概念并采用先分解后组合的方法研究出一种边数很多、接近于完全图的不同构图的确定方法及其数目的比较算法,给出了判断定理及其证明和应用。     

有源网络完全k树多项式的产生及其在网络分析中的应用

本文算法产生有源网络无源树边的完全k树多项式,算法时间复杂度与列写无向图全部树的改进的Minty算法相同。用该算法分析有源网络的符号函数可有效地减少对消冗余项数,同时也避免了对无源完全树边的符号鉴别问题。文章讨论了算法的合理性,并举例说明了它在网络分析中的应用。     

基于图的邻接点优先的联合树算法的研究与实现

贝叶斯网络是以概率理论为基础的不确定知识表示模型,联合树算法是一种应用广泛的贝叶斯网络推理算法。提出了基于邻接点优先的联合树算法,从图模型和计算效率两个方面对联合树算法（JT）和基于图的邻接点优先的联合树（AD-JT）算法进行推理时间的比较,实验表明：基于图的邻接点优先的联合树算法能够有效地处理大规模数据,极大地减少了消耗时间,计算效率有显著改进。     

P-ISOMAP:一种新的对邻域大小不甚敏感的数据可视化算法

ISOMAP算法对邻域大小敏感,而邻域大小却难以有效选取.本文根据二阶最小生成树不含有"短路"边的特性提出了能有效删除邻域图中的"短路"边因而对邻域大小不甚敏感的P-ISOMAP算法.由于避免了邻域大小难以有效选取的问题,该算法能更容易地对数据进行可视化,也获得了一定程度的拓扑稳定性和鲁棒性.实验结果很好地验证了该算法的有效性.     

基于直角Steiner树的片上网络互连算法

提出了一种基于最小直角Steiner树,在Manhattan平面上避免障碍物的互连算法,以实现片上网络中各IP核的互连.该算法在定制NoC中将Steiner树的生成算法用于互连设计.算法首先在初始阶段对有障碍两点间的边权重重新赋值,然后调用最小生成树算法,使生成的直角Steiner树总长度最小.实验表明,该算法可以使片上网络的总连线缩短.     

不确定型模糊Kripke结构的计算树逻辑模型检测

本文研究了不确定型模糊Kripke结构的计算树逻辑的模型检测问题,并说明了该问题可以在对数多形式时间内解决.首先给出了不确定型模糊Kripke结构的定义,引入了模糊计算树逻辑的语法和语义.为了刻画存在量词∃和任意量词∀在不确定型模糊Kripke结构中的两种语义解释,在模糊计算树逻辑语法中引入了路径量词∃_sup,∃_inf和∀_sup,∀_inf,分别用于替换存在量词∃和任意量词∀.其次讨论了基于不确定型模糊Kripke结构的计算树逻辑模型检测算法,特别地对于模糊计算树逻辑公式∃_suppUq,∀_suppUq,∃_infpUq和∀_infpUq分别给出时间复杂度为对数多项式时间的改进算法.     

Turbo-MIMO系统中一种基于部分后验概率的软检测算法

迭代树搜索(ITS)是一种有效的基于M-算法的软MIMO检测方案。然而ITS会遇到某些比特的对数似然比(LLR)无法确定的情况,虽可采用赋常数值方法(称为clipping)解决,但这会影响系统性能。为此,该文提出一种新的基于M-算法的软检测方案。该方案在树的每一级递推计算部分符号序列的后验概率,并基于此近似计算从第1级到该级的所有比特LLR,再采用M-算法保留部分符号序列延伸至下一级。该算法可确保每比特都可计算LLR,且能得到可靠性高的LLR值。考虑到某些比特LLR会多次计算,文中给出了算法的低复杂度实现。另外,该文还给出了一种计算符号序列后验概率的简单方法。最后,仿真结果表明所提算法相比ITS具有更好的性能,并使性能与复杂度达到较好的折中。     

工程数学

0153.2 02020009一种新的布尔函数求补算法/陈国章,何王廉,陈敏(夭津理工学院).天津大学学报一2001,3《4)一447一451研究了SOP(积的和型)布尔函数的求补算法,分析了已有的求补算法之间的深层联系,给出了否定树的概念.证明了单边求补算法、Sharp算法与德·摩根律是等效的、不相交的.Shal,p算法是递归算法的一个特例.提出了以否定树为基础的解决SOP型函数求补运算的新算法.图6表1参5(木)的变换族可以用一个矩阵群来描述,多次变换运算完全转化为相应的矩阵乘法运算.最后,数字信号分数Fourier变换的仿真计算表明,分数Fotlrier变换具有独特的…     

通信网中链路重要性的评价方法

本文提出了一种通信网链路重要性的评价方法,该方法可以评价全网范围内的链路重要性.最重要的链路是将其进行边收缩操作后,得到的图的生成树数目最多.通过比较生成树的数目,我们可以判断通信网中任意两条链路的相对重要性.基于生成树数目的边收缩方法反映了某条链路处于正常工作时,对整个通信网的贡献大小.实验结果和理论分析均证明了该方法的有效性和可行性.     

A two-layer recurrent Neural Network based approach for overlay multicast

Overlay multicast has become one of the most promising multicast solutions for IP network, and Neutral Network（NN） has been a good candidate for searching optimal solutions to the constrained shortest routing path in virtue of its powerful capacity for parallel computation. Though traditional Hopfield NN can tackle the optimization problem, it is incapable of dealing with large scale networks due to the large number of neurons. In this paper, a neural network for overlay multicast tree computation is presented to reliably implement routing algorithm in real time. The neural network is constructed as a two-layer recurrent architecture, which is comprised of Independent Variable Neurons （IDVN） and Dependent Variable Neurons （DVN）, according to the independence of the decision variables associated with the edges in directed graph. Compared with the heuristic routing algorithms, it is characterized as shorter computational time, fewer neurons, and better precision.     

Order of complexity of linear active networks and a common tree in the 2-graph method

An upper bound on the order of complexity of a linear active network is the sum of the numbers of tree capacitances and link inductances, defined by a common tree of the voltage and current graph that contains a maximum number of capacitances and a minimum number of inductances. It is valid as far as a common tree exists, and is the lowest possible upper bound if only the network topology is known.     

STATE SPACE TREE METHOD AND EXACT DECOMPOSITION ALGORITHM FOR FINDING NETWORK OVERALL RELIABILITY

First,the state space tree method for finding communication network overall re-liability is presented.It directly generates one disjoint tree multilevel polynomial of a networkgraph.Its advantages are smaller computational effort(its computing time complexity is O(en_l),where e is the number of edges and n_l is the number of leaves)and shorter resulting expression.Second,based on it an exact decomposition algorithm for finding communication network overallreliability is presented by applying the hypergraph theory.If we use it to carry out the m-timedecomposition of a network graph,the communication network scale which can be analyzed by acomputer can be extended to m-fold.     

基于不完全分解预优共轭梯度法的电源和地线网络求解器

在超大规模集成电路的电源和地线网络的设计中 ,求解由该网络上每个节点的电压和每条边上的电流是最基本的运算 ,它对电源和地线网络拓扑结构设计和线宽优化算法的质量具有直接的影响 .针对电源和地线网络的特殊性 ,提出了一个高效的电源和地线网络求解器 ,包括电路网络中树结构的合并与恢复和用不完全分解的预优共轭梯度法来求解节点电压方程 .该求解器的运算速度很快 ,所耗费的内存很小 ,同时具有很强的鲁棒性     

有向树图的最小K点连通扩充

本文解决了图论的连通性理论中的一个重要的问题——以最小边集扩充一个任意有向树图为K点连通图,证明了该问题在算法上属于P问题,提出了一个时间复杂度为O(|V|³)的有效算法DTKA,该算法为可靠通讯网的计算机辅助设计提供了一个基础.     

求网络总可靠度的状态空间树法和精确分解算法

本文提出了求通信网络总可靠度的状态空间树法。它直接产生网络图的一个不交化树多层多项式,优点是计算量较小[计算时间复杂度为0(?),(?)为边数,n_1为叶数],所得表达式较短。在此基础上应用超图理论提出了求通信网络总可靠度的精确分解算法。用它进行网络图的m次分解,一台计算机所能计算的通信网络规模可以扩大m倍。     

Finding the most vital edges with respect to the number of spanningtrees

A most vital edge of a graph (w.r.t. the spanning trees) is an edge whose deletion most drastically decreases the number of spanning trees. We present an algorithm for determining the most vital edges based on Kirchoff's matrix-tree theorem whose asymptotic time-complexity can be reduced to that of the fastest matrix multiplication routine, currently O(n^2.376). The foundation for this approach is a more general algorithm for directed graphs for counting the rooted spanning arborescences containing each of the arcs of a digraph. A network can be modeled as a probabilistic graph. Under one such model proposed by Kel'mans, the all-terminal network reliability, maximizing the number of spanning trees is critical to maximizing reliability when edges are very unreliable. For this model, the most vital edges characterize the locations where an improvement of the reliability of the link most improves the reliability of the network     

Realization of state equations by RC network and one controlled source†

The realization of a class of state equations by RC network and one voltage-controlled voltage source is described. The linear graph of the network has at least one complete tree such that the tree branches correspond to all capacitances, to all voltage sources and to the controlled source only.