首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
Let T be a tree with n vertices and let D be the distance matrix of T. According to a classical result due to Graham and Pollack, the determinant of D is a function of n, but does not depend on T. We allow the edges of T to carry weights, which are square matrices of a fixed order. The distance matrix D of T is then defined in a natural way. We obtain a formula for the determinant of D, which involves only the determinants of the sum and the product of the weight matrices.  相似文献   

2.
3.
In this note, we show how the determinant of the distance matrix D(G) of a weighted, directed graph G can be explicitly expressed in terms of the corresponding determinants for the (strong) blocks Gi of G. In particular, when cof D(G), the sum of the cofactors of D(G), does not vanish, we have the very attractive formula .  相似文献   

4.
汉明距离矩阵Ds是由测量定义在F_s~q:={0,1,…,q-1}^s上的码字的汉明距离的元素构成.汉明距离矩阵Ds可以由递归的形式表示出来.利用汉明距离矩阵Ds的递归公式求得了矩阵D_s所有特征根以及特征向量.在文章的最后还得出-cDs的Schur指数形的所有特征根.如果c〉0的话,-cDs的Schur指数形的所有特征根都大于零,从而-cDs的Schur指数形是正定的.  相似文献   

5.
The permanental spread of a complex square matrix A is defined to be the greatest distance between two roots of the equation per(zIA) = 0. A preliminary study of this number as well as of two related quantities is given. In particular, we derive upper and lower bounds and deal with comparisons of different bounds. Finally, two inequalities involving the permanental spread are treated.  相似文献   

6.
Let T be a tree with line graph T*. Define K = 2I + A(T*), where A denotes the adjacency matrix. Then the eigenvalues of -2K?1 interlace the eigenvalues of the distance matrix D. This permits numerous results about the spectrum of K to be transcribed for the less tractable D.  相似文献   

7.
8.
A different approach is given to recent results due mainly to R. C. Johnson and A. Leal Duarte on the multiplicities of eigenvalues of a Hermitian matrix whose graph is a tree. The techniques developed are based on some results of matching polynomials and used a work by O. L. Heilmann and E. H. Lieb on an apparently unrelated topic.   相似文献   

9.
10.
A connected graph G, whose 2-connected blocks are all cliques (of possibly varying sizes) is called a block graph. Let D be its distance matrix. By a theorem of Graham, Hoffman and Hosoya, we have det(D)?≠?0. We give a formula for both the determinant and the inverse, D ?1 of D.  相似文献   

11.
Let T be a tree with n vertices, where each edge is given an orientation, and let Q be its vertex-edge incidence matrix. It is shown that the Moore-Penrose inverse of Q is the (n-1)× n matrix M obtained as follows. The rows and the columns of M are indexed by the edges and the vertices of T respectively. If e,ν are an edge and a vertex of T respectively, then the (e,ν)-entry of M is, upto a sign, the number of vertices in the connected component of T\e which does not contain ν. Furthermore, the sign of the entry is positive or negative, depending on whether e is oriented away from or towards ν. This result is then used to obtain an expression for the Moore-Penrose inverse of the incidence matrix of an arbitrary directed graph. A recent result due to Moon is also derived as a consequence.  相似文献   

12.
We present a new scheme for representing binary trees. The scheme is based on rotations as a previous scheme of Zerling. In our method the items of a representation have a natural geometric interpretation, and the algorithms related to the method are simple. We give an algorithm for enumerating all the representations for trees onn nodes, and an algorithm for building the tree corresponding to a given representation.This work was supported by the Academy of Finland.  相似文献   

13.
An elementary proof of a formula for the 2-norm distance from a normal matrix A to the set of matrices with a multiple zero eigenvalue is given. Earlier, the authors obtained this formula as an implication of a nontrivial result due to A. N. Malyshev. Bibliography: 4 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 323, 2005, pp. 50–56.  相似文献   

14.
We study the behavior of dynamic programming methods for the tree edit distance problem, such as [P. Klein, Computing the edit-distance between unrooted ordered trees, in: Proceedings of 6th European Symposium on Algorithms, 1998, p. 91–102; K. Zhang, D. Shasha, SIAM J. Comput. 18 (6) (1989) 1245–1262]. We show that those two algorithms may be described as decomposition strategies. We introduce the general framework of cover strategies, and we provide an exact characterization of the complexity of cover strategies. This analysis allows us to define a new tree edit distance algorithm, that is optimal for cover strategies.  相似文献   

15.
If G is a connected graph with vertex set V, then the degree distance of G, D(G), is defined as , where degw is the degree of vertex w, and d(u,v) denotes the distance between u and v. We prove the asymptotically sharp upper bound for graphs of order n and diameter d. As a corollary we obtain the bound for graphs of order n. This essentially proves a conjecture by Tomescu [I. Tomescu, Some extremal properties of the degree distance of a graph, Discrete Appl. Math. (98) (1999) 159-163].  相似文献   

16.
For a matrix polynomial P(λ) and a given complex number μ, we introduce a (spectral norm) distance from P(λ) to the matrix polynomials that have μ as an eigenvalue of geometric multiplicity at least κ, and a distance from P(λ) to the matrix polynomials that have μ as a multiple eigenvalue. Then we compute the first distance and obtain bounds for the second one, constructing associated perturbations of P(λ).  相似文献   

17.
We study the problem of uniformly partitioning the edge set of a tree with n edges into k connected components, where k?n. The objective is to minimize the ratio of the maximum to the minimum number of edges of the subgraphs in the partition. We show that, for any tree and k?4, there exists a k-split with ratio at most two. For general k, we propose a simple algorithm that finds a k-split with ratio at most three in O(nlogk) time. Experimental results on random trees are also shown.  相似文献   

18.
It is shown that H = Γ(T)v is normal in G = Γ(Tv) for any tree T and any vertex v, if and only if, for all vertices u in the neighborhood N of v, the set of images of u under G is either contained in N or has precisely the vertex u in common with N and every vertex in the set of images is fixed by H. Further, if S is the smallest normal subgroup of G containing H then GS is the direct product of the wreath products of various symmetric groups around groups of order 1 or 2. The degrees of the symmetric groups involved depend on the numbers of isomorphic components of Tv and the structure of such components.  相似文献   

19.
An axiomatic characterization of the distance function of a connected graph is given in this note. The triangle inequality is not contained in this characterization.  相似文献   

20.
A subset X in the d-dimensional Euclidean space is called a k-distance set if there are exactly k distinct distances between two distinct points in X and a subset X is called a locally k-distance set if for any point x in X, there are at most k distinct distances between x and other points in X.Delsarte, Goethals, and Seidel gave the Fisher type upper bound for the cardinalities of k-distance sets on a sphere in 1977. In the same way, we are able to give the same bound for locally k-distance sets on a sphere. In the first part of this paper, we prove that if X is a locally k-distance set attaining the Fisher type upper bound, then determining a weight function w, (X,w) is a tight weighted spherical 2k-design. This result implies that locally k-distance sets attaining the Fisher type upper bound are k-distance sets. In the second part, we give a new absolute bound for the cardinalities of k-distance sets on a sphere. This upper bound is useful for k-distance sets for which the linear programming bound is not applicable. In the third part, we discuss about locally two-distance sets in Euclidean spaces. We give an upper bound for the cardinalities of locally two-distance sets in Euclidean spaces. Moreover, we prove that the existence of a spherical two-distance set in (d−1)-space which attains the Fisher type upper bound is equivalent to the existence of a locally two-distance set but not a two-distance set in d-space with more than d(d+1)/2 points. We also classify optimal (largest possible) locally two-distance sets for dimensions less than eight. In addition, we determine the maximum cardinalities of locally two-distance sets on a sphere for dimensions less than forty.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号