1、本文詳細(xì)研究了在最小分配單位為給定物品組合情況下的組合分配問(wèn)題模型，從計(jì)算理論的角度通過(guò)構(gòu)造性方法證明該問(wèn)題可在多項(xiàng)式時(shí)間規(guī)約為于本文首先提出的無(wú)向圖邊帶權(quán)最大獨(dú)立集問(wèn)題。其次給出了邊帶權(quán)最大獨(dú)立集問(wèn)題的定義并證明該問(wèn)題屬于NP-hard問(wèn)題。同時(shí)還證明了任何無(wú)向圖邊帶權(quán)最大獨(dú)立集問(wèn)題可在問(wèn)題多項(xiàng)式時(shí)間反向規(guī)約于組合分配問(wèn)題。用基于度數(shù)的子圖劃分方法給出邊帶權(quán)最大獨(dú)立集問(wèn)題的一個(gè)近似度為「(1+△′)/3」的近似算法，其中△′為圖中點(diǎn)的

2、最大度數(shù)。最后根據(jù)組合分配問(wèn)題與邊帶權(quán)最大獨(dú)立集問(wèn)題可相互規(guī)約的性質(zhì)給出了這兩個(gè)問(wèn)題的近似度下界。我們?cè)诒疚闹兄饕幸韵鹿ぷ鳎?.首先提出并證明了組合分配問(wèn)題在最小分配單位為給定物品組合時(shí)，該問(wèn)題可多項(xiàng)式時(shí)間規(guī)約為于無(wú)向圖邊帶權(quán)最大獨(dú)立集問(wèn)題。2.給出無(wú)向圖邊帶權(quán)最大獨(dú)立集問(wèn)題的定義，證明邊帶權(quán)最大獨(dú)立集問(wèn)題屬于NP-hard問(wèn)題；同時(shí)證明任何的無(wú)向圖邊帶權(quán)最大獨(dú)立集問(wèn)題可在多項(xiàng)式時(shí)間規(guī)約為最小分配單位為給定物品組合情況下的組合分配問(wèn)題