β分配問題

Abstract

設Ｕ為圖形Ｇ＝（Ｖ，Ｅ）中Ｖ的子集。一個Ｇ中對Ｕ而言的β分配（β－ASSIGNME NT）是一個邊（EDGE）的子集Ｘ，並對入一在Ｕ中的點ｖ滿足DEGX(v)=1 ；此地DEGX (v) 表點ｖ在Ｘ所造成的Ｇ子圖中的連邊數（DEGREE）。β分配問題即為在Ｇ中對Ｕ 求一β分配Ｘ，使得β（Ｘ）≡MAX{DEGX(V): V V －U}為最小。 在二分圖（BIPARTITE GRAPH ）上的β分配問題首先為張瑞雄及李家同先生（CL）所 提出，他們問以下形式的分配問題。假設現有一ｎ個工作所成之集合Ｓ和ｍ個工人所 成之集合Ｔ，已知每一工人能做那些工作，試問要如何把所有的工作都分給工人做， 才能使做最多事的那個工人所做的工作愈少愈好。我們可以考慮二分圖Ｇ＝（Ｓ，Ｔ ，Ｅ，），其中（Ｓ，Ｔ）為Ｇ的點集合的二分（BIPARTITION ）且（i,j ） Ｅ， 若且唯若工人ｊ能做工作ｉ。則前述問題相當於在Ｇ中找一對Ｓ而言最佳的β分配。 這篇論文的主要目的即為設計並分析幾個高效率的演算法則（ALGORITHMS）來解決β 分配問題，我們也對β分配問題研究其強對偶定理及存在定理。首先我們用類似匈牙 利演算法（HUNGARIAN ALGORITHM ）的演算法在Ｏ（ｎ3 ）的時間內分別解決了在二 分圖中的純量β分配問題，瓶頸β分配問題及加權β分配問題。這些演算法提供的副 產品為這些問題的強對偶定理（STRONG DUALITY THEOREMS ）。接著我們設計一個Ｏ （ｎ3 ）的演算法來解決在一般圖形中的純量β分配問題。最後，這個演算法也幫助 我們證明了一般圖的β分配問題之強對偶定理及存在定理。後者是TUTTE 之一般圖上 的完美配對（PERFECT MATCHING）存在性定理的推廣。