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

1、第五章第五章 獨(dú)立集與匹配獨(dú)立集與匹配 5.1 5.1 獨(dú)立集獨(dú)立集 5.2 5.2 支配集支配集 5.3 5.3 匹配匹配 5.4 5.4 最大匹配算法最大匹配算法 5.5 5.5 最優(yōu)匹配最優(yōu)匹配 5.6 Ramsey5.6 Ramsey數(shù)數(shù)5.1 獨(dú)立集獨(dú)立集點(diǎn)覆蓋點(diǎn)覆蓋圖中，點(diǎn)覆蓋數(shù)依次為圖中，點(diǎn)覆蓋數(shù)依次為3，4，6。23145678910邊覆蓋邊覆蓋獨(dú)立集的應(yīng)用舉例獨(dú)立集的應(yīng)用舉例例例：(收款臺(tái)的設(shè)置問題收款臺(tái)的設(shè)置問題)某大型商場(chǎng)為加強(qiáng)經(jīng)營(yíng)管某大型商場(chǎng)為加強(qiáng)經(jīng)營(yíng)管理，對(duì)商品的零售收入實(shí)行統(tǒng)一收款制度。為了使顧理，對(duì)商品的零售收入實(shí)行統(tǒng)一收款制度。為了使顧客在任何一個(gè)貨架前都能看到

2、收款臺(tái)，問收款臺(tái)應(yīng)設(shè)客在任何一個(gè)貨架前都能看到收款臺(tái)，問收款臺(tái)應(yīng)設(shè)置在什么地方且至少要設(shè)置多少個(gè)收款臺(tái)置在什么地方且至少要設(shè)置多少個(gè)收款臺(tái)?矩陣變換求獨(dú)立集矩陣變換求獨(dú)立集v1v2v4v3v6v5團(tuán)的定義：團(tuán)的定義：clique例：求下圖的極大獨(dú)立集例：求下圖的極大獨(dú)立集452361875.2 支配集支配集 在國(guó)際象棋的比賽中，首先出在國(guó)際象棋的比賽中，首先出現(xiàn)了現(xiàn)了支配集支配集的概念。的概念。1862年，年，De考考慮了控制整個(gè)棋盤所需要的最少的慮了控制整個(gè)棋盤所需要的最少的皇后個(gè)數(shù)問題。他指出在一個(gè)的棋皇后個(gè)數(shù)問題。他指出在一個(gè)的棋盤具有處在配置下的盤具有處在配置下的64個(gè)格子，在個(gè)格子，

3、在所給某個(gè)位置的皇后控制著同行、所給某個(gè)位置的皇后控制著同行、同列以及包含這個(gè)格子的兩條斜線同列以及包含這個(gè)格子的兩條斜線上的所有格子，這種皇后的最少個(gè)上的所有格子，這種皇后的最少個(gè)數(shù)為數(shù)為5，左圖左圖顯示了一種放置方法。顯示了一種放置方法。QQQQQ 若要若要求任兩個(gè)皇后都不互相攻擊，即任兩個(gè)皇后求任兩個(gè)皇后都不互相攻擊，即任兩個(gè)皇后都不在同一行、同一列或一斜線上，那么這種皇后的都不在同一行、同一列或一斜線上，那么這種皇后的最少個(gè)數(shù)為最少個(gè)數(shù)為7，下圖顯示了一種放置方法。，下圖顯示了一種放置方法。QQQQQQQ支配集的幾個(gè)性質(zhì)定理支配集的幾個(gè)性質(zhì)定理注意：不是注意：不是每個(gè)支配集都是獨(dú)立集每

4、個(gè)支配集都是獨(dú)立集；也不是每個(gè)也不是每個(gè)最小支配集都是獨(dú)立集最小支配集都是獨(dú)立集。 求極小支配集的一種布爾運(yùn)算方法求極小支配集的一種布爾運(yùn)算方法 例：例：求在下圖的全部極小支配集。求在下圖的全部極小支配集。5.3 匹配匹配 匹配問題匹配問題是運(yùn)籌學(xué)的重要問題之一是運(yùn)籌學(xué)的重要問題之一,也是圖論研究的也是圖論研究的終點(diǎn)內(nèi)容終點(diǎn)內(nèi)容,它提供了解決它提供了解決“人員分配問題人員分配問題”和和“最優(yōu)分配最優(yōu)分配問題問題”一種新的思想。一種新的思想。說明說明:(1)完美匹配是最大匹配，反之未必然完美匹配是最大匹配，反之未必然;(2)匹配的定義與邊的方向無(wú)關(guān)，故匹配是針對(duì)無(wú)向圖。匹配的定義與邊的方向無(wú)關(guān)，

5、故匹配是針對(duì)無(wú)向圖。例：例：下圖中虛線所示為匹配，則下圖中虛線所示為匹配，則(2,3,5,6,9,10)是一條是一條交錯(cuò)路，而交錯(cuò)路，而(1，2，3，5，6，8)是一條可增廣路。是一條可增廣路。練習(xí)練習(xí) 例：例： 某工廠生產(chǎn)由六種不同顏色的紗織成的雙色布，某工廠生產(chǎn)由六種不同顏色的紗織成的雙色布，由這個(gè)工廠所生產(chǎn)的雙色布中，每一種顏色至少和其他由這個(gè)工廠所生產(chǎn)的雙色布中，每一種顏色至少和其他三種顏色搭配。證明可以挑選出三種不同的雙色布，它三種顏色搭配。證明可以挑選出三種不同的雙色布，它們含有所有的六種顏色。們含有所有的六種顏色。5.4 最大匹配算法最大匹配算法匈牙利算法匈牙利算法圖（圖（a a

6、） 圖（圖（b） MxSTN(S)yN(S)-Ty,u MPy1,y2,y3,y4,y5y1非飽和非飽和x1y2,x2y1,x3y3 x5y5y2飽和飽和y3飽和飽和N(S)=T,停止停止圖圖(c)1x2x3x4x5x1y2y3y4y5y例：例：求下圖最大匹配求下圖最大匹配匈亞利算法：匈亞利算法：00*00*11*23*00*11*23*22200*1123*2220*44044*23044*235.5 最優(yōu)匹配及算法最優(yōu)匹配及算法 基于上述定理，基于上述定理，Kuhn(1955)Kuhn(1955)和和Munkres(1957)Munkres(1957)提出一個(gè)在提出一個(gè)在加權(quán)完全二部圖中求

7、加權(quán)完全二部圖中求最優(yōu)匹配的算法，最優(yōu)匹配的算法，簡(jiǎn)稱為簡(jiǎn)稱為K-MK-M算法算法。其其主要思想主要思想如下：如下： Kuhn-Munkres算法算法Kuhn-Munkres算法也可以用來(lái)求加權(quán)完全二部圖中總權(quán)算法也可以用來(lái)求加權(quán)完全二部圖中總權(quán)最小的完美匹配。它需要將原來(lái)的權(quán)重矩陣做相應(yīng)的變最小的完美匹配。它需要將原來(lái)的權(quán)重矩陣做相應(yīng)的變化，即化，即將權(quán)重最大問題將權(quán)重最大問題，轉(zhuǎn)化為，轉(zhuǎn)化為權(quán)重最小問題權(quán)重最小問題。 x1 x2 x3 x4 x5y1 y2 y3 y4 y52243455445541133353341002*AaJA5.6 Ramsey數(shù)數(shù) 1928 1928年年, , 年僅年僅2424歲的英國(guó)杰出數(shù)學(xué)家歲的英國(guó)杰出數(shù)學(xué)家RamseyRamsey發(fā)表了著發(fā)表了著名論文名論文論形式邏輯中的一個(gè)問題論形式邏輯中的一個(gè)問題, , 他在這篇論文他在這篇論文中中, , 提出并證明了關(guān)于集合論的一個(gè)重大研究成果提出并證明了關(guān)于集合論的一個(gè)重大研究成果, , 現(xiàn)現(xiàn)稱為稱為RamseyRamsey定理定理。 盡管兩年后他不幸去世，但是他開拓的這一新領(lǐng)域至盡管兩年后他不幸去世，但是他開拓的這一新領(lǐng)域至今仍十分活躍，而且近年來(lái)在科技領(lǐng)域獲得了成功的今仍十分活躍，而且近年來(lái)在科技領(lǐng)域獲得了成功的應(yīng)用。在介紹應(yīng)用。在介紹RamseyRamsey數(shù)概念之前，先看數(shù)概念之前，先