齿轮构成和稳定的集合多面体[外文翻译].rar

齿轮构成和稳定的集合多面体
A. Galluccio_, C. Gentile, P. Ventura




摘要：
我们介绍由一张特定图表H和B生产一张图表G称齿轮的一张固定的图表的新的图表构成，并且我们学习它多面的物产。当G是无爪时，这些构成对在刺面(G)结构的臆想产生反例。
c 2008 Elsevier B.V. 保留所有权。

关键词：稳定的集合多面体；图表构成；多面的组合学; 无爪图表

1：简介
给定图表G = (V、E)和结重量为w∈QV+矢量时，稳定的集合问题就是发现成对地不邻近的结(稳定的集合)最大重量的问题。由刺(G)表示的稳定集合多面体，是稳定系列的发生矢量的凸面船身G，而且它的尺寸是满足的。如果刺(G) = { x ：Ax≦b}，那么一个线性Ax≦b被认为定义为刺(G)。定义刺(G)的小平面不等式，是那些不等式构成刺(G)独特的非冗余的定义的线性本制。很明显，我们发现刺(G)的定义的线性本制是等效的变换原始的优化问题成线性关系max{wT x : Ax≦b}，而且是NP坚硬稳定的集合问题，在一般图表发现这样一个系统是不太可能的。
然而稳定的集合多面体的面部结构是其中一个在多面组合数学的被学习的问题。以下是一张与刺(G)小平面的研究关系不可能的列表：当G是连续并列[13]时，奇怪无K4 [9]或类似线[6]时，产生图表[17,20,15]， t和h完美雕琢平面[11]，刺的描述特性(G)。