R-Trees and Symmetric Differences of Sets
R-Trees and Symmetric Differences of Sets
复制标题
R 树和集合的对称差
DOI：
10.1006/eujc.1996.0134
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
W. Terhalle
中科院分区：
文献类型：
--
作者：
W. Terhalle
对称差分的上确界？y：=（x\y）？（y\x）的子集x，y的R满足所谓的四点条件;也就是说，对于所有x，x？，y，y？? R，一个有sup（x？x？）+ sup（y？y？）？max { sup（x？y）+ sup（x？? y？），sup（x？y？）+ sup（x？? y）}。由此得出R的所有有界子集的集合E构成一个相对于映射E×E的赋值拟阵。{-∞}？R：（x，y）？sup（x？y）。因此，根据T-理论，存在一个R-树T（E，v），它唯一地由（E，v）确定直到等距，其末端以一对一的方式对应于（E，v）的完成的元素。此外，T（E，v）的点可以与R的包含其下确界的有界子集相一致，在这里，我们证明了这些观察在更一般的情况下成立：给定任意非空集合和任意映射：B？{-∞}？R，映射P（B）× P（B）？R？{±∞}：（x，y）？supr（x？y）再次满足四点条件;所以B的子集的任何非空集合Z具有supr（x？y）<∞对于所有x，y？Z相对于该映射形成一个秩为2的赋值拟阵，从而产生一个R-树，本文证明了每一个秩为2的赋值拟阵都可以通过选择适当的系统（B，r：B？{-∞}？R Z P（B））;因此，由于每个R-树都可以等距嵌入到T（E，v）中，对于某个赋值拟阵（E，v），每个R-树原则上都可以用这样一个系统来描述。
The supremum of the symmetric differencex?y:= (x\y)?(y\x) of subsetsx,yof R satisfies the so-called four-point condition; that is, for allx,x?,y,y? ? R, one has sup (x?x?) + sup(y?y?)? max { sup(x?y) + sup(x? ?y?), sup (x?y?) + sup(x? ?y)}. It follows that the setEof all subsets of R which are bounded from above forms a valuated matroid relative to the mapv:E×E?{-∞}?R : (x,y)?sup (x?y). Hence, according to T-theory, there exists an R-treeT(E,v)uniquely determined by (E,v) up to isometry, the ends of which correspond in a one-to-one fashion to the elements of the completion of (E,v). In addition, the points ofT(E,v)can be identified with those bounded subsets of R which contain their infimum.Here, we show that these observations hold true in a much more general setting: given an arbitrary non-empty setBand an arbitrary mapr:B?{-∞}?R, the map P(B) × P(B)?R?{±∞}: (x,y)?supr(x?y) again satisfies the four-point condition; so any non-empty setZof subsets ofBwith supr(x?y)<∞ for allx,y?Zforms a valuated matroid of rank 2 relative to this map and, therefore, gives rise to an R-tree.It is shown here that every valuated matroid of rank 2 can be realized in this way by choosing an appropriate system (B,r:B?{-∞}?R ,Z? P(B)); consequently, since every R-tree can be embedded isometrically intoT(E,v)for some valuated matroid (E,v), every R-tree can, in principle, be described in terms of such a system.