共查询到20条相似文献,搜索用时 15 毫秒
1.
Alessandra Frabetti 《Journal of Algebraic Combinatorics》2001,13(1):41-65
Planar binary trees appear as the the main ingredient of a new homology theory related to dialgebras, cf.(J.-L. Loday, C.R. Acad. Sci. Paris
321 (1995), 141–146.) Here I investigate the simplicial properties of the set of these trees, which are independent of the dialgebra context though they are reflected in the dialgebra homology.The set of planar binary trees is endowed with a natural (almost) simplicial structure which gives rise to a chain complex. The main new idea consists in decomposing the set of trees into classes, by exploiting the orientation of their leaves. (This trick has subsequently found an application in quantum electrodynamics, c.f. (C. Brouder, On the Trees of Quantum Fields, Eur. Phys. J. C12, 535–549 (2000).) This decomposition yields a chain bicomplex whose total chain complex is that of binary trees. The main theorem of the paper concerns a further decomposition of this bicomplex. Each vertical complex is the direct sum of subcomplexes which are in bijection with the planar binary trees. This decomposition is used in the computation of dialgebra homology as a derived functor, cf. (A. Frabetti, Dialgebra (co) Homology with Coefficients, Springer L.N.M., to appear). 相似文献
2.
The paper gives the proof of the following fact: all simple, i.e., having no nodes of degree 2, trees that span the vertices of the regular n-dimensional simplex can be realized as nondegenerate minimal parametric networks. 相似文献
3.
4.
DONGHUI CHEN DING-ZHU DU XIAO-DONG HU GUO-HUI LIN LUSHENG WANG GUOLIANG XUE 《Journal of Global Optimization》2000,18(1):17-33
Given n terminals in the Euclidean plane and a positive constant, find a Steiner tree interconnecting all terminals with the minimum number of Steiner points such that the Euclidean length of each edge is no more than the given positive constant. This problem is NP-hard with applications in VLSI design, WDM optical networks and wireless communications. In this paper, we show that (a) the Steiner ratio is 1/ 4, that is, the minimum spanning tree yields a polynomial-time approximation with performance ratio exactly 4, (b) there exists a polynomial-time approximation with performance ratio 3, and (c) there exists a polynomial-time approxi-mation scheme under certain conditions. 相似文献
5.
A gradient-constrained minimum network
T is a minimum length network, spanning a given set of nodes N in space with edges whose gradients are all no more than an upper bound m. The nodes in T but not in N are referred to as Steiner points. Such networks occur in the underground mining industry where the typical maximal gradient is about 1:7 (≈ 0.14). Because
of the gradient constraint the lengths of edges in T are measured by a special metric, called the gradient metric. An edge in T is labelled as a b-edge, or an m-edge, or an f-edge if the gradient between its endpoints is greater than, or equal to, or
less than m respectively. The set of edge labels at a Steiner point is called its labelling. A Steiner point s with a given labelling is called labelled minimal if T cannot be shortened by a label-preserving perturbation of s. Furthermore, s is called locally minimal if T cannot be shortened by any perturbation of s even if its labelling is not preserved. In this paper we study the properties of labelled minimal Steiner points, as well
as the necessary and sufficient conditions for Steiner points to be locally minimal. It is shown that, with the exception
of one labelling, a labelled minimal Steiner point is necessarily unique with respect to its adjacent nodes, and that the
locally minimal Steiner point is always unique, even though the gradient metric is not strictly convex. 相似文献
6.
本文部分地改进了堵丁柱、黄光明所证明的Gilbert-Pollak关于Steiner树的一个猜想,提出一个新的不等式。 相似文献
7.
A Cutting Plane Algorithm for Linear Reverse Convex Programs 总被引:1,自引:0,他引:1
In this paper, global optimization of linear programs with an additional reverse convex constraint is considered. This type of problem arises in many applications such as engineering design, communications networks, and many management decision support systems with budget constraints and economies-of-scale. The main difficulty with this type of problem is the presence of the complicated reverse convex constraint, which destroys the convexity and possibly the connectivity of the feasible region, putting the problem in a class of difficult and mathematically intractable problems. We present a cutting plane method within the scope of a branch-and-bound scheme that efficiently partitions the polytope associated with the linear constraints and systematically fathoms these portions through the use of the bounds. An upper bound and a lower bound for the optimal value is found and improved at each iteration. The algorithm terminates when all the generated subdivisions have been fathomed. 相似文献
8.
主要研究了平面上处于一般位置的19-点集,根据其凸包边数的不同,分别讨论了其所含空凸多边形的个数,得出G(19)≤5.在此基础上,对平面上处于一般位置的n-点集得出G(n)≤[11n/42],从而改进了G(n)的上界. 相似文献
9.
二维严格凸赋范空间单位球面间等距映射的线性延拓 总被引:1,自引:1,他引:0
主要研究二维严格凸实赋范空间E和F的单位球面S_1(E)和S_1(F)之间的等距映射的线性延拓问题.利用二维严格凸赋范空间单位球面的性质得到:若等距映射V_0:S_1(E)→S_1(F)满足一定条件,则V_0可延拓为全空间E上的线性等距映射V:E→F. 相似文献
10.
Stanislav Jendrol 《Geometriae Dedicata》1997,68(1):91-99
In this paper we prove that each convex 3-polytope contains a path on three vertices with restricted degrees which is one of the ten types. This result strengthens a theorem by Kotzig that each convex 3-polytope has an edge with the degree sum of its end vertices at most 13. 相似文献
11.
研究了极大代数上无穷阵序列{Gi}0∞的实现问题.首先给出了周期阵序列的概念,得到了1-阶和2-阶周期阵序列{Gi}0∞元素之间的关系,并得到多输入多输出情况下线性系统存在1维和2维最小实现的充要条件. 相似文献
12.
Tobias Gerken 《Discrete and Computational Geometry》2008,39(1-3):239-272
Erdős asked whether every sufficiently large set of points in general position in the plane contains six points that form
a convex hexagon without any points from the set in its interior. Such a configuration is called an empty convex hexagon.
In this paper, we answer the question in the affirmative. We show that every set that contains the vertex set of a convex
9-gon also contains an empty convex hexagon. 相似文献
13.
Banach空间上凸泛函的某些对偶性质 总被引:2,自引:0,他引:2
本语文对Banach空间上的凸泛函建立了若干对偶性质,通过对偶的手段,建立了非常简洁的凸泛函极小化序列弱收敛的特征定理。 相似文献
14.
Song Pu SHANG Tong JING 《数学学报(英文版)》2007,23(9):1577-1586
This paper considers the Steiner Minimal Tree (SMT) problem in the rectilinear and octilinear planes. The study is motivated by the physical design of VLSI: The rectilinear case corresponds to the currently used M-architecture, which uses either horizontal or vertical routing, while the octilinear case corresponds to a new routing technique, X-architecture, that is based on the pervasive use of diagonal directions. The experimental studies show that the X-architecture demonstrates a length reduction of more than 10-20%. In this paper, we make a theoretical study on the lengths of SMTs in these two planes. Our mathematical analysis confirms that the length reduction is significant as the previous experimental studies claimed, but the reduction for three points is not as significant as for two points. We also obtain the lower and upper bounds on the expected lengths of SMTs in these two planes for arbitrary number of points. 相似文献
15.
M. Brazil J.H. Rubinstein D.A. Thomas J.F. Weng N.C. Wormald 《Journal of Global Optimization》2001,21(2):139-155
In three-dimensional space an embedded network is called gradient-constrained if the absolute gradient of any differentiable point on the edges in the network is no more than a given value m. A gradient-constrained minimum Steiner tree T is a minimum gradient-constrained network interconnecting a given set of points. In this paper we investigate some of the fundamental properties of these minimum networks. We first introduce a new metric, the gradient metric, which incorporates a new definition of distance for edges with gradient greater than m. We then discuss the variational argument in the gradient metric, and use it to prove that the degree of Steiner points in T is either three or four. If the edges in T are labelled to indicate whether the gradients between their endpoints are greater than, less than, or equal to m, then we show that, up to symmetry, there are only five possible labellings for degree 3 Steiner points in T. Moreover, we prove that all four edges incident with a degree 4 Steiner point in T must have gradient m if m is less than 0.38. Finally, we use the variational argument to locate the Steiner points in T in terms of the positions of the neighbouring vertices. 相似文献
16.
研究了极大代数上线性系统的3维最小实现问题,给出了特征方程为λ<'3> c<,0>λ<'0>=c<,2>λ<'2> c<,1>λ,当c<,1>=c<'2><,2>,c<,0>=C<,1>C<,2>时,无穷序列{g<,2>}<,0><'∞>存在3维最小实现的充要条件. 相似文献
17.
求线性约束凸规划问题的最优解。方法:在鞍梯度法的基础上提出了一个具有全局收敛性的原一对偶外点算法。结果:每步迭代利用Lagrange函数的鞍梯度构造搜索方向,生成次可行解序列,由此得到的序列的极限就是原-对偶问题的最优解。结论:即使从原一对偶问题的不可行点开始迭代算法也收敛。 相似文献
18.
讨论了极大代数上线性系统的3维最小实现问题.给出了特征方程为λ~3⊕c_0λ~0=c_2λ~2⊕c_1λ的一类无穷序列{gi}_0~∞存在3维最小实现的充要条件,彻底解决了存在3维最小实现的充要条件问题. 相似文献
19.
Klaus Metsch 《Designs, Codes and Cryptography》1997,10(2):251-263
We show that every non-degenerate planar space with v points and planes can be embedded as a linear space into PG(3,q) for some prime power q provided that 1000( - v) v5/6; 相似文献