第5章獨(dú)立集與匹配

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

5.1獨(dú)立集

點(diǎn)覆蓋

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

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

矩陣變換求獨(dú)立集

v1v2v4v3v6v5

團(tuán)的定義：

clique例：求下圖的極大獨(dú)立集45236187

5.2支配集

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

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

注意：不是每個(gè)支配集都是獨(dú)立集；也不是每個(gè)最小支配集都是獨(dú)立集。

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

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

說(shuō)明:(1)完美匹配是最大匹配，反之未必然;(2)匹配的定義與邊的方向無(wú)關(guān)，故匹配是針對(duì)無(wú)向圖。

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

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

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)提出一個(gè)在加權(quán)完全二部圖中求最優(yōu)匹配的算法，簡(jiǎn)稱為K-M算法。其主要思想如下：

Kuhn-Munkres算法

Kuhn-Munkres算法也可以用來(lái)求加權(quán)完全二部圖中總權(quán)最小的完美匹配。它需要將原來(lái)的權(quán)重矩陣做相應(yīng)的變化，即將權(quán)重最大問題，轉(zhuǎn)化為權(quán)重最小問題。

x1x2x3x4x5y1y2y3y4y5

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