最小费用k度限制树对策

本在Glover—Klingman算法及最小费用支撑树对策的基础上，讨论了最小费用k度限制树对策问题．利用威胁、旁支付理论制订了两种规则，并利用优超、策略等价理论分别给出了在这两种规则下最小费用k度限制树对策核心中的解，从而证明了在这两种规则下其核心非空．     

Locally minimal uniformly oriented shortest networks

The Steiner problem in a λ-plane is the problem of constructing a minimum length network interconnecting a given set of nodes (called terminals), with the constraint that all line segments in the network have slopes chosen from λ uniform orientations in the plane. This network is referred to as a minimum λ-tree. The problem is a generalization of the classical Euclidean and rectilinear Steiner tree problems, with important applications to VLSI wiring design.A λ-tree is said to be locally minimal if its length cannot be reduced by small perturbations of its Steiner points. In this paper we prove that a λ-tree is locally minimal if and only if the length of each path in the tree cannot be reduced under a special parallel perturbation on paths known as a shift. This proves a conjecture on necessary and sufficient conditions for locally minimal λ-trees raised in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222]. For any path P in a λ-tree T, we then find a simple condition, based on the sum of all angles on one side of P, to determine whether a shift on P reduces, preserves, or increases the length of T. This result improves on our previous forbidden paths results in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222].     

STRONG LAW OF LARGE NUMBERS AND ASYMPTOTIC EQUIPARTITION PROPERTY FOR NONSYMMETRIC MARKOV CHAIN FIELDS ON CAYLEY TREES

Some strong laws of large numbers for the frequcncies of occurrence of states and ordered couples of states for nonsymmetric Markov chain fields(NSMC)on Cayley trees are studied.In the proof,a new technique for the study of strong liinit theorems of Markov chains is extended to the case of Markov chain fields.The asymptotic equiparti- tion properties with almost everywhere(a.e.)convergence for NSMC on Cayley trees are obtained.     

LIMITING BEHAVIOR OF UNIFORM RECURSIVE TREES

The authors consider the limiting behavior of various branches in a uniform recursive tree with size growing to infinity.The limiting distribution ofζ_(n,m),the number of branches with size m in a uniform recursive tree of order n,converges weakly to a Poisson distribution with parameter 1/m with convergence of all moments.The size of any large branch tends to infinity almost surely.     

Tree-gel and loop-gel conversions in nonlinear polymerization

Ａｓｉｓｗｅｌｌｋｎｏｗｎ,ｔｈｅｔｈｅｏｒｙｆｏｒｎｏｎｌｉｎｅａｒｐｏｌｙｍｅｒｉｚａｔｉｏｎｓｗａｓｉｎｉｔｉａｔｅｄｂｙＦｌｏｒｙａｎｄＳｔｏｃｋｍａｙｅｒ[1—3].ＭｉｌｌｅｒａｎｄＭａｃｏｓｋｏ[4—6]ｐｒｏｐｏｓｅｄａｒｅｃｕｒｓｉｖｅｍｅｔｈｏｄｆｏｒｄｅａｌｉｎｇｗｉｔｈｔｈｅｐｒｏｂｌｅｍｏｆｔｈｅｐｏｓｔｇｅｌｐｒｏｐｅｒｔｉｅｓｏｆｔｈｅｎｅｔｗｏｒｋｆｏｒｍｉｎｇｐｏｌｙｍｅｒｉｚａｔｉｏｎ.Ｓｔｅｐｔｏ[7]ｉｎｖｅｓｔｉｇａｔｅｄｔｈｅｇｅｌｇｅｌｒｅａｃｔｉｏｎｏｆＲＡｆｔ…     

Equilibrium polymerization in a solvent: Solution on the Bethe lattice

The lattice model for equilibrium polymerization in a solvent proposed by Wheeler and Pfeuty is solved exactly on a Bethe lattice (core of a Caylay tree) with general coordination numberq. Earlier mean-field results are reobtained in the limitq, but the phase diagrams show deviations from them for finiteq. Whenq=2, our results turn into the solution of the one-dimensional problem. Although the model is solved directly, without the use of the correspondence between the equilibrium polymerization model and the diluten0 model, we verified that the latter model may also be solved on the Bethe lattice, its solution being identical to the direct solution in all parameter space. As observed in earlier studies of the puren0 vector model, the free energy is not always convex. We obtain the region of negative susceptibility for our solution and compare this result with mean field and renormalization group (-expansion) calculations.     

On the Randić Index of Acyclic Conjugated Molecules

The Randić index of an organic molecule whose molecular graph is G is the sum of the weights (d(u)d(v))^−1/2 of all edges uv of G, where d(u) and d(v) are the degrees of the vertices u and v in G. We give a sharp lower bound on the Randić index of conjugated trees (trees with a perfect matching) in terms of the number of vertices. A sharp lower bound on the Randić index of trees with a given size of matching is also given Mei Lu: Partially supported by NNSFC (No. 60172005) Lian-zhu Zhang: Partially supported by NNSFC (No. 10271105) Feng Tian: Partially supported by NNSFC (No. 10431020)     

Fast folding and comparison of RNA secondary structures

Summary Computer codes for computation and comparison of RNA secondary structures, the Vienna RNA package, are presented, that are based on dynamic programming algorithms and aim at predictions of structures with minimum free energies as well as at computations of the equilibrium partition functions and base pairing probabilities.An efficient heuristic for the inverse folding problem of RNA is introduced. In addition we present compact and efficient programs for the comparison of RNA secondary structures based on tree editing and alignment.All computer codes are written in ANSI C. They include implementations of modified algorithms on parallel computers with distributed memory. Performance analysis carried out on an Intel Hypercube shows that parallel computing becomes gradually more and more efficient the longer the sequences are.

---

Schnelle Faltung und Vergleich von Sekundärstrukturen von RNA

Zusammenfassung Die im Vienna RNA package enthaltenen Computer Programme für die Berechnung und den Vergleich von RNA Sekundärstrukturen werden präsentiert. Ihren Kern bilden Algorithmen zur Vorhersage von Strukturen minimaler Energie sowie zur Berechnung von Zustandssumme und Basenpaarungswahrscheinlichkeiten mittels dynamischer Programmierung.Ein effizienter heuristischer Algorithmus für das inverse Faltungsproblem wird vorgestellt. Darüberhinaus präsentieren wir kompakte und effiziente Programme zum Vergleich von RNA Sekundärstrukturen durch Baum-Editierung und Alignierung.Alle Programme sind in ANSI C geschrieben, darunter auch eine Implementation des Faltungs-algorithmus für Parallelrechner mit verteiltem Speicher. Wie Tests auf einem Intel Hypercube zeigen, wird das Parallelrechnen umso effizienter je länger die Sequenzen sind.

     

Oriented hypergraphs: Balanceability

An oriented hypergraph is an oriented incidence structure that extends the concepts of signed graphs, balanced hypergraphs, and balanced matrices. We introduce hypergraphic structures and techniques that generalize the circuit classification of the signed graphic frame matroid to any oriented hypergraphic incidence matrix via its locally-signed-graphic substructure. To achieve this, Camion's algorithm is applied to oriented hypergraphs to provide a generalization of reorientation sets and frustration that is only well-defined on balanceable oriented hypergraphs. A simple partial characterization of unbalanceable circuits extends the applications to representable matroids demonstrating that the difference between the Fano and non-Fano matroids is one of balance.     

N叉树上的离散时间量子随机行走

通过离散时间量子随机行走的框架,我们研究了在N叉树上的离散时间量子随机行走,该框架不需要硬币空间,仅仅只需要选择一个除了酉性再无其它限制的演化算子,并且包含了使用再生结构的轨道枚举和z变换.作为结果,我们在封闭形式中计算了在根处的振幅的生成函数.