上頁 1234 次頁

相異代表系古今談 (第 3 頁)

張鎮華

 

首頁 | 搜尋

.原載於數學傳播第十卷第一期
對外搜尋關鍵字
 
3.電腦帶來的衝擊:匈牙利算法

在1960年代的熱潮堙A另外一個異軍突起的是電腦。 電腦的興起完成人類快速計算的美夢,許多以前人們不敢奢望的問題, 再度被拿出來借助電腦無怨言的快速計算順利完成。但是電腦的快速也有其一定的極限, 於是一門新興的學問-算法(Algorithm)-廣泛的研究。

舉例來說,站在理論的觀點,何氏定理無疑的是一個極漂亮的定理, 但從實用的立場來看,它似乎毫無發揮的餘地。隨便給n個集合, 若想用何氏定理驗證是否存在一個相異代表系, 就必須把 2n-1 種不同的 k 個集合拿出來, 看它們聯集是否存在最少k個元素。一方面,當n大時,2n 大得不可思議, 再者即使驗證出的答案是肯定的,何氏定理也沒告訴我們那一組是相異代表系, 為此,我們需要一個有效的算法。

把相異代表系轉換成二分圖網 (bipartite graph) 上求對集 (matching) 的問題是一種方便的語言。 一般而言,一個圖網 (graph) 包含有限個頂點 (vertices) 以及一些聯接兩個頂點的邊 (edges),如圖1 的 A1,A2,A3,A4,a,b,c,d 是頂點, (A1,a),(A1,b),$\cdots\cdots$ 是邊,但圖上 (A1,c)(A3,b) 兩邊另外相交的點並不算做頂點,換言之,聯接某兩頂點的邊其實只表示這兩點是 「有關係」或「相鄰」而已,至於用直線或曲線表示,實無區別。



圖1

圖1的圖網就是所謂的二分圖網,因為頂點可以分為兩部分,其中任一部分內的任二頂點不相鄰。這個二分圖網事實上也就是例1的集族的圖網表示法; $a\in A_1$ 所以 (A1,a) 是一條邊, $b \not \in A_2$ 所以 (A2,b) 不是一條邊。 (A1,A2,A3,A4)是一組相異代表(a,b,c,d),在圖網上相當於(A1,a), (A2,c),(A3,b),(A4,d)四邊,分別表示$a\in A_1$,$c\in A_2$, $b\in A_3$,$d\in A_4$;這四邊中的任兩邊沒有共同頂點, 因為我們找不同集合的相異代表,圖2中粗線表示這四邊。 像這種兩兩不含共同頂點的邊所組成的集合稱為對集(matching)。 所以求$(A_1,\cdots$ $\cdots,A_n)$的一組相異代表, 相當於在它所對應的二分圖網中找一個有n邊的對集。



圖2

用二分圖網表示集合族 $(A_1,\cdots\cdots,A_n)$的另一好處是可以看出集合Ai和元素aj的對稱性, 如果對每一元素aj,定義集合 $B_j=\{i;\:a_j\in A_i\}$, (A1,$\cdots\cdots$,An)(B1,$\cdots\cdots$,Bm) 所對應出來的二分圖網實際上是同一圖網(可能頂點左右相反,名稱各異)。在婚姻問題中,這表示男女平等。

隨便給一集合族 (A1,$\cdots\cdots$,An) 不一定存在相異代表系, 所以在它的二分圖網中,也不見得能找到一個n邊的對集。一般來說, 我們有興趣的是,隨便給一個二分圖網,求一個具有最多邊的對集, 有名的匈牙利方法(Hungarian method)就是解決這問題的好算法。

給定一個二分圖網G=(X,Y,E),其中XY合成所有頂點,E是邊集, 任一邊的一端點在X內,另一端點在Y內。另給定G中的一個對集M, 如圖3(a)是一個例子,粗線代表對集M



圖3(a)



圖3(b)

G 的一條M-可擴張路徑 (M-augmenting path) 是含有 2n+1 個頂點的一條路徑 (v0,v1,v2,$\cdots\cdots$, v2n,v2n+1),其中 $(v_{2i},v_{2i+1})\in E\setminus M$, $i=0,1,\cdots\cdots,n$, 但是 $(v_{2i-1},v_{2i})\in M$, $i=1,\cdots\cdots,n$ 並且 v0v2n+1M-暴露頂點(M-exposed vertices), 也就是 v0v2n+1 不是 M 內任何邊的端點。 例如圖3(a)中 (x3,y1,x1,y3) 是一條 M-可擴張路徑。

找到一條M-可擴張路徑 P 的好處是,如果將MP的邊去掉,換上P 中不在M的邊,將造成一個新對集M*,其邊數比原來M的邊數增加1。 圖3(b)就是用上述M-可擴張路徑做出來為M*

貝爾齊定理(Berge Theorem): 任一圖網(不一定是二分圖網)中的對集M是最大對集的充分條件是不存在 M-可擴張路徑。

匈牙利方法簡單的說就是從二分圖網G=(X,Y,E)的任意對集M(例如空集合) 開始,有系統的尋找M-可擴張路徑,若找到就得到一個更大的對集, 再繼續一直到不存在M-可擴張路徑為止。 尋找M-可擴張路徑的方法如下述。

(甲) $i\longleftarrow 0$;列出所有M-暴露頂點當作第i層。
(乙) 當i是偶數時:依次列出和第i層頂點相鄰的頂點當作第i+1層, 但被列出過的頂點不再重複;若第i+1層沒有頂點則停止, 表示沒有M-可擴張路徑。當i是奇數時: 若有某個第i層的頂點是M-暴露頂點, 表示找到一條M-可擴張路徑; 否則將第i層每一頂點所聯接的一條M邊找出來, 另一端點當作第i+1層頂點。
(丙) $i\longleftarrow i+1$;回到(乙)重做。

以圖3(a)為例,可以得到下圖;其中我們賦予偶(奇)數層的頂點以正(負)號, 這是為了以後說明方便。



圖4

因為y3(負號)是M-暴露頂點,所以找一條M-可擴張路徑, 就是 (y3,x1,y1,x3),這是由y3倒返回去找到的。 由這個M-可擴張路徑得到一個更大的對集,如圖3(b)所示, 再做一次得到下圖,表示不存在M-可擴張路徑,所以已經找到最大對集。



圖5

   

上頁 1234 次頁

回頁首
 
(若有指正、疑問……,可以在此 留言寫信 給我們。)
EpisteMath

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有


編輯:林君怡 / 校對:黃怡碧 / 繪圖:簡立欣 最後修改日期:4/26/2002