Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
复制标题
Delta-拟阵、跳跃系统和双亚模多面体
DOI：
--
复制
发表时间：
1995
影响因子：
0.8
通讯作者：
W. Cunningham
中科院分区：
文献类型：
--
作者：
A. Bouchet;W. Cunningham
本文将称为跳跃系统的矩阵的公理概括与由双族模型函数产生的多面体联系起来。与通常的次生次数不同，感兴趣的点并不是相关多面体中的所有积分点，而是其中的一个子集。但是，可以证明跳跃系统的一组点的凸壳是双重模块化的多面体，并且积分bisubmodular polyhedron的积分点确定了（特殊的）跳跃系统。作者证明了跳跃系统的添加和组成定理，这些定理具有多个用于三角形摩托病和矩形的应用。
This paper relates an axiomatic generalization of matroids, called a jump system, to polyhedra arising from bisubmodular functions. Unlike the case for usual submodularity, the points of interest are not all the integral points in the relevant polyhedron but form a subset of them. However, it is shown that the convex hull of the set of points of a jump system is a bisubmodular polyhedron, and that the integral points of an integral bisubmodular polyhedron determine a (special) jump system. The authors prove addition and composition theorems for jump systems, which have several applications for delta-matroids and matroids.