裝填問題(packing problem)是一類典型的組合最佳化問題。設I={v1，v2，…，vm}是一個有限集，E={E1，E2，…，En}為I的子集所形成的一個集簇，若E的一個子族E′={Ej1，…，Ejs}使得I中的每個元素包含在E′的至多一個元素之中，則稱E′為I的一個裝填，求I的一個裝填E′使得所含的元素數為最多就是所謂裝填問題。一般地，賦E中每個元素以一個權，而將E中的元素最多改為其中元素的權和為最大，當每個元素的權均為1時，即這裡所說的裝填問題，若將E′中的每個元素視為一個車廂，這時的裝填問題也被稱為裝箱問題，若E′使得I中的每個元素包含在E′的至少一個元素之中，則稱E′為I的一個覆蓋，求I的一個覆蓋E′使得E′含E中的元素最小就是所謂覆蓋問題，也可以將它推廣到帶權的情形，若E′使得I中的每個元素包含在E′的恰好一個元素之中，則稱E′為I的一個劃分，求I的一個劃分E′使得E′中含的元素數為最少就是劃分問題，同樣可以有帶權情形下之推廣，這裡所述的裝填問題、覆蓋問題，以及劃分問題均是NP完全問題，因此，要想用好的算法解這些問題是不現實的。
基本介紹
- 中文名：裝填問題
- 外文名：packing problem
- 所屬學科：數學
- 所屬問題：組合學（組合最最佳化)
- 簡介：一類典型的組合最佳化問題
基本介紹,相關定理,
基本介紹
圖論中有兩類相互有一定聯繫然而又是性質不同的問題，一類是研究用某種類型的子圖
去覆蓋圖G的點集或邊集(即
，或
)，這就是所謂覆蓋問題。例如正常邊染色是用邊不交的邊無關集覆蓋E(G)；團覆蓋集是用團去覆蓋V(G)等等。一般說來，我們希望用最少個數的子圖去完成覆蓋，這就是最小覆蓋問題。另一類問題是研究從給定圖中，能取出多少個不交的某類子圖，或者反其意而說成是可以往給定圖中裝填多少個不交的某類子圖，這就是裝填問題。一般說來，我們希望裝填的子圖個數儘可能地多，這就是最大裝填問題。例如有向圖中弧形式的Menger定理所研究的是往D中裝填弧不交的(
)路。Menger定理是以最大最小定理的形式研究了能裝填k個弧不交的()路的充分必要條件。
相關定理
給圖
，對任意的
，記
{
含過e的圈}，定義
稱為E1-的閉集。一個子集
，若
不含圈，且
，則稱
為
的一個基集。不難證明，的任何兩個基集，總包含相同個數的邊，定義
為的基集所含的邊數。
定理1(Tutte,Nash-Williams，1961) 中含有k個邊不交的支撐樹的充分必要條件是對任何，
定理1可以寫成另一種形式。
定理1' 圖有k個邊不交的支撐樹，若且唯若對V的任意剖分
，有
需要指出的是定理1(1')對多重圖也是成立的，利用定理1，我們可以得到覆蓋邊集合所需要的森林的最小個數(記之為a(G)，稱為圖G的蔭度)。
定理2 令G是非平凡的多重圖，
是G中m階子圖的最大邊數，令
