Compatible decompositions and block realizations of finite metrics
Compatible decompositions and block realizations of finite metrics
复制标题
DOI：
10.1016/j.ejc.2007.10.003
复制
发表时间：
2008-10
期刊：
影响因子：
--
通讯作者：
A. Dress;K. Huber;J. Koolen;V. Moulton
中科院分区：
文献类型：
--
作者：
A. Dress;K. Huber;J. Koolen;V. Moulton
给定一个定义在有限集合X上的度量D，我们定义X上的度量的有限集合D为D的相容分解，如果D中任意两个不同的度量线性无关（被认为是RX×X中的向量），D=∑d∈Dd成立，并且对于D中任意两个不同的度量d，d′存在点x，x′∈X，使得d（x，y）d′（x′，y）=0对每个y∈X成立.本文证明了这样的分解与D的块实现（同构类）一一对应，即D的图实现G是块图，且G中每个不被X标号的顶点的度至少为3，并且是G的割点.这推广了系统发育组合学中的一个基本结果，即定义在X上的度量D可以由树实现，当且仅当存在D的相容分解D，使得所有度量d∈D都是分裂度量，并为度量分解的更一般理论奠定了基础，这将在未来的论文中进行探讨。
Given a metric D defined on a finite set X, we define a finite collection D of metrics on X to be a compatible decomposition of D if any two distinct metrics in D are linearly independent (considered as vectors in RX×X), D=∑d∈Dd holds, and there exist points x,x′∈X for any two distinct metrics d,d′in D such that d(x,y)d′(x′,y)=0 holds for every y∈X. In this paper, we show that such decompositions are in one-to-one correspondence with (isomorphism classes of) block realizations of D, that is, graph realizations G of D for which G is a block graph and for which every vertex in G not labelled by X has degree at least 3 and is a cut point of G. This generalizes a fundamental result in phylogenetic combinatorics that states that a metric D defined on X can be realized by a tree if and only if there exists a compatible decomposition D of D such that all metrics d∈D are split metrics, and lays the foundation for a more general theory of metric decompositions that will be explored in future papers.