Matroid Applications: Matroids and Rigid Structures
Matroid Applications: Matroids and Rigid Structures
复制标题
拟阵应用：拟阵和刚性结构
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
W. Whiteley
中科院分区：
文献类型：
--
作者：
W. Whiteley
许多工程问题导致一个线性方程组——一个表示的矩阵——它的秩控制着这个例子的关键定性特征（Sugihara, 1984; 1985; White & Whiteley, 1983）。我们将从空间结构的刚性、多面体图像的重建以及相关的几何问题中选取一些这样的拟阵。对于这些情况，示例的组合模式决定了一个稀疏矩阵模式，该模式既具有一般秩（用于非零条目的一般“独立”值），又具有几何秩（用于相应几何模型的点、线和面的坐标的特殊值）。越来越多的人利用拟阵理论技术来研究这些例子的一般秩。这些几何模型很好地说明了矩阵联合、截断和半模函数等技术的应用。这些例子中的基本未解问题突出了拟阵理论中某些未解问题。他们的研究还将在拟阵理论中产生新的结果。我们从最简单的例子开始，它将介绍词汇和基本模式。我们在一条直线上放置一系列不同的点，并指定某些杆-要保持其距离的关节对-定义直线上的杆框架。我们问整个框架是否是“刚性的”——也就是说，在保持这些距离的情况下，关节沿着直线的任何运动是否会给所有关节带来相同的速度、加速度等？很明显，一个框架有一个底层图G = (V， E)，对于每个结点P i有一个顶点V i，对于每个杆{P i， P j}有一个无向边{i， j}。
Many engineering problems lead to a system of linear equations a represented matroid - whose rank controls critical qualitative features of the example (Sugihara, 1984; 1985; White & Whiteley, 1983). We will outline a selection of such matroids, drawn from recent work on the rigidity of spatial structures, reconstruction of polyhedral pictures, and related geometric problems. For these situations, the combinatorial pattern of the example determines a sparse matrix pattern that has both a generic rank, for general ‘independent’ values of the non-zero entries, and a geometric rank, for special values for the coordinates of the points, lines, and planes of the corresponding geometric model. Increasingly, the generic rank of these examples has been studied by matroid theoretic techniques. These geometric models provide nice illustrations and applications of techniques such as matroid union, truncation, and semimodular functions. The basic unsolved problems in these examples highlight certain unsolved problems in matroid theory. Their study should also lead to new results in matroid theory. Bar Frameworks on the Line - the Graphic Matroid We begin with the simplest example, which will introduce the vocabulary and the basic pattern. We place a series of distinct points on a line, and specify certain bars - pairs of joints which are to maintain their distance - defining a bar framework on the line . We ask whether the entire framework is ‘rigid’ - i.e. does any motion of the joints along the line, preserving these distances, give all joints the same velocity, acceleration, etc.? Clearly a framework has an underlying graph G = (V, E) , with a vertex v i for each joint P i and an undirected edge { i, j } for each bar { p i, p j }.