On the error of a priori sampling: Zero forcing sets and propagation time
On the error of a priori sampling: Zero forcing sets and propagation time
复制标题
关于先验采样的误差：迫零集和传播时间
DOI：
10.1016/j.laa.2018.03.031
复制
发表时间：
2019
影响因子：
1.1
通讯作者：
Lin, Jephian C.-H.
中科院分区：
文献类型：
--
作者：
Kenter, Franklin H.J.;Lin, Jephian C.-H.
迫零是一个迭代过程，用于限制图的最大零值。该过程首先选择着色的顶点，其余顶点可以根据特定的颜色更改规则着色。目标是找到一个最小的顶点集，使得在迭代应用规则后，所有的顶点都变成有色的（即最小迫零集）。特别感兴趣的是所选集合的传播时间，这是为了给图的所有顶点着色而必须应用规则的步骤数。我们给出了迫零的纯线性代数观点：找到一组顶点S，使得对于任何加权邻接矩阵A，每当Ax= 0时，x的整体可以仅使用x S来恢复，对应于S的条目。这里的关键是S必须在A之前被选择。在这种情况下，我们能够给出传播时间的线性代数解释：x S中的任何误差都会影响x在传播时间中的指数误差。该误差可以使用新定义的零强迫相关参数、误差多项式向量和方差多项式向量来定量测量。从这个意义上说，即使两个迫零集大小相同，传播时间相同，它们的质量也可以客观地进行比较。给出了实例和构造。
Zero forcing is an iterative process on a graph used to bound the maximum nullity. The process begins with select vertices as colored, and the remaining vertices can become colored under a specific color change rule. The goal is to find a minimum set of vertices such that after iteratively applying the rule, all of the vertices become colored (ie, a minimum zero forcing set). Of particular interest is the propagation time of a chosen set which is the number of steps the rule must be applied in order to color all the vertices of a graph. We give a purely linear algebraic view of zero forcing: Find a set of vertices S such that for any weighted adjacency matrix A, whenever Ax= 0, the entirety of x can be recovered using only x S, the entries corresponding to S. The key here is that S must be chosen before A. In this light, we are able to give a linear algebraic interpretation of the propagation time: Any error in x S effects the error of x exponentially in the propagation time. This error can be quantitatively measured using newly defined zero forcing-related parameters, the error polynomial vector and the variance polynomial vector. In this sense, the quality of two zero forcing sets can objectively be compared even if the sets are the same size and their propagation times are the same. Examples and constructions are given.