第5章獨立集與匹配

第五章獨立集與匹配5.1獨立集5.2支配集5.3匹配5.4最大匹配算法5.5最優(yōu)匹配5.6Ramsey數(shù)

5.1獨立集

點覆蓋

圖中，點覆蓋數(shù)依次為3，4，6。23145678910

邊覆蓋獨立集的應用舉例例：(收款臺的設置問題)某大型商場為加強經營管理，對商品的零售收入實行統(tǒng)一收款制度。為了使顧客在任何一個貨架前都能看到收款臺，問收款臺應設置在什么地方且至少要設置多少個收款臺?

矩陣變換求獨立集

v1v2v4v3v6v5

團的定義：

clique例：求下圖的極大獨立集45236187

5.2支配集

在國際象棋的比賽中，首先出現(xiàn)了支配集的概念。1862年，De考慮了控制整個棋盤所需要的最少的皇后個數(shù)問題。他指出在一個的棋盤具有處在配置下的64個格子，在所給某個位置的皇后控制著同行、同列以及包含這個格子的兩條斜線上的所有格子，這種皇后的最少個數(shù)為5，左圖顯示了一種放置方法。QQQQQ

若要求任兩個皇后都不互相攻擊，即任兩個皇后都不在同一行、同一列或一斜線上，那么這種皇后的最少個數(shù)為7，下圖顯示了一種放置方法。QQQQQQQ支配集的幾個性質定理

注意：不是每個支配集都是獨立集；也不是每個最小支配集都是獨立集。

求極小支配集的一種布爾運算方法例：求在下圖的全部極小支配集。5.3匹配

匹配問題是運籌學的重要問題之一,也是圖論研究的終點內容,它提供了解決“人員分配問題”和“最優(yōu)分配問題”一種新的思想。

說明:(1)完美匹配是最大匹配，反之未必然;(2)匹配的定義與邊的方向無關，故匹配是針對無向圖。

例：下圖中虛線所示為匹配，則(2,3,5,6,9,10)是一條交錯路，而(1，2，3，5，6，8)是一條可增廣路。練習

例：某工廠生產由六種不同顏色的紗織成的雙色布，由這個工廠所生產的雙色布中，每一種顏色至少和其他三種顏色搭配。證明可以挑選出三種不同的雙色布，它們含有所有的六種顏色。

5.4最大匹配算法匈牙利算法

圖（a）圖（b）

MxSTN(S)yN(S)-T{y,u}MP{y1,y2,y3,y4,y5}y1非飽和{x1y2,x2y1,x3y3x5y5}y2飽和y3飽和N(S)=T,停止

圖(c)

例：求下圖最大匹配

匈亞利算法：

00**00

**11*23*00*11*23*

22200*1123*222

0*

44044

**23044**23

5.5最優(yōu)匹配及算法

基于上述定理，Kuhn(1955)和Munkres(1957)提出一個在加權完全二部圖中求最優(yōu)匹配的算法，簡稱為K-M算法。其主要思想如下：

Kuhn-Munkres算法

Kuhn-Munkres算法也可以用來求加權完全二部圖中總權最小的完美匹配。它需要將原來的權重矩陣做相應的變化，即將權重最大問題，轉化為權重最小問題。

x1x2x3x4x5y1y2y3y4y5

5.6Ramsey數(shù)1928年,年僅24歲的英國杰出數(shù)學家Ramsey發(fā)表了著名論文《論形式邏輯中的一個問題》,他在這篇論文中,提出并證明了關于集合論的一個重大研究成果,現(xiàn)稱為Ramsey定理。盡管兩年后他不幸去世，但是他開拓的這一新領域至今仍十分活躍，而且近年來在科技領域獲得了成功的應用。在