A CHARACTERIZATION OF FACES OF THE BASE POLYHEDRON ASSOCIATED WITH A SUBMODULAR SYSTEM
A CHARACTERIZATION OF FACES OF THE BASE POLYHEDRON ASSOCIATED WITH A SUBMODULAR SYSTEM
复制标题
与子模系统相关的基多面体面的表征
DOI：
10.15807/jorsj.27.112
复制
发表时间：
1984
影响因子：
--
通讯作者：
S. Fujishige
中科院分区：
文献类型：
--
作者：
S. Fujishige
对于一个分配格J）~ 2 E和J）上的一个次模函数f，f（</1 E J）和f（</1）= 0，称对（J），f）为一个次模系，当E E J）时，由B（f）= {x I x E RE，I X E J）：x（X）~ f（X），x（E）= f（E））给出的多面体称为与（J），f）相联系的基多面体.研究了基多面体B（f）的结构，给出了B（f）所有面的一个刻划.使B（f）的面与J）的某些子格一一对应，使得J）的所有这些子格的集合D与B（f）的所有非空面的集合F反同构。这里，D和F被认为是相对于集合包含的偏序集。根据D中子格的结构，给出了面、面的维数、面的极值点和极值射线之间的关联关系。其中包括最近的结果作为特殊情况（1）偏序集结构的一个polymatroid极端点和连通组件的Bixby，坎宁安和Topkis，（2）极端射线的锥确定的分配格的富泽，和（3）邻接的polymatroid极端点的Topkis。此外，给定J）的一个子格，F（J）I）=（x I x E B（f），| IX EJ）I：x（X）= f（X））是B（f）的一个非空面，并且在D中唯一存在一个对应于面F（J）J）的子格J）2.本文证明了J）J与J）2之间关系的一个定理，J）2被认为是.DJ的一个闭包，这个闭包运算与最近由中村和lri提出的极大骨架的概念密切相关.这些表征的数学方面也进行了讨论。
For a distributive lattice J) ~ 2E and a submodular function f on J) with </1 E J) and f(</1) = 0, the pair (J), f) is called a submodular system and, when E EJ), the polyhedron given by B(f) = {x I x E RE, \IX EJ): x(X) ~ f(X),x(E) = f(E) ) is called the base polyhedron associated with (J), f). We examine the structure of the base polyhedron B(f) and give a characterization of all the faces of B(f). Faces of B(f) are made correspond one-to-one to certain sublattices of J), so that the collection D of all such sublattices of.7) is anti-isomorphic with the collection F of all the non empty faces of B(f). Here, D and F are considered as posets relative to set inclusion. The incidence relation among faces, dimensions of faces, and extreme points and extreme rays of faces are given based on the structure of the sublattices in D. These include as special cases recent results on (1) a poset structure of a polymatroid extreme point and connected components by Bixby, Cunningham and Topkis, (2) extreme rays of a cone determined by a distributive lattice by Tomizawa, and (3) adjacency for polymatroid extreme points by Topkis. Moreover, given a sublattice.7)1 of J) on which f is modular, F(J)I) = (x I x E B(f), \IX EJ)I: x(X) = f(X) ) is a nonempty face of B(f) and there uniquely exists a sublattice J)2 in D which corresponds to the face F(J)J). We show a theorem which characterizes the relationship between J)J and J)2' J)2 is considered as a closure of .DJ and this closure operation is closely related to the concept of maximal skeleton recently considered by Nakamura and lri. Algorithmic aspects of these characterizations are also discussed.