齒輪構(gòu)成和穩(wěn)定的集合多面體
A. Galluccio_, C. Gentile, P. Ventura




摘要：
我們介紹由一張?zhí)囟▓D表H和B生產(chǎn)一張圖表G稱齒輪的一張固定的圖表的新的圖表構(gòu)成，并且我們學(xué)習(xí)它多面的物產(chǎn)。當(dāng)G是無(wú)爪時(shí)，這些構(gòu)成對(duì)在刺面(G)結(jié)構(gòu)的臆想產(chǎn)生反例。
c 2008 Elsevier B.V. 保留所有權(quán)。

關(guān)鍵詞：穩(wěn)定的集合多面體；圖表構(gòu)成；多面的組合學(xué); 無(wú)爪圖表

1：簡(jiǎn)介
給定圖表G = (V、E)和結(jié)重量為w∈QV+矢量時(shí)，穩(wěn)定的集合問(wèn)題就是發(fā)現(xiàn)成對(duì)地不鄰近的結(jié)(穩(wěn)定的集合)最大重量的問(wèn)題。由刺(G)表示的穩(wěn)定集合多面體，是穩(wěn)定系列的發(fā)生矢量的凸面船身G，而且它的尺寸是滿足的。如果刺(G) = { x ：Ax≦b}，那么一個(gè)線性Ax≦b被認(rèn)為定義為刺(G)。定義刺(G)的小平面不等式，是那些不等式構(gòu)成刺(G)獨(dú)特的非冗余的定義的線性本制。很明顯，我們發(fā)現(xiàn)刺(G)的定義的線性本制是等效的變換原始的優(yōu)化問(wèn)題成線性關(guān)系max{wT x : Ax≦b}，而且是NP堅(jiān)硬穩(wěn)定的集合問(wèn)題，在一般圖表發(fā)現(xiàn)這樣一個(gè)系統(tǒng)是不太可能的。
然而穩(wěn)定的集合多面體的面部結(jié)構(gòu)是其中一個(gè)在多面組合數(shù)學(xué)的被學(xué)習(xí)的問(wèn)題。以下是一張與刺(G)小平面的研究關(guān)系不可能的列表：當(dāng)G是連續(xù)并列[13]時(shí)，奇怪無(wú)K4 [9]或類似線[6]時(shí)，產(chǎn)生圖表[17,20,15]， t和h完美雕琢平面[11]，刺的描述特性(G)。