圖論二分圖的最大匹配

1、二分圖的最大匹配AngelClover二分圖二分圖是一種特殊的圖對于無向圖G=(V,E)，如果V可以分為兩個互不相交的子集，并且圖中的每條邊所依附的兩點都屬于不同的子集，則圖G則稱為一個二分圖544332211最大匹配給定一個二分圖G，在G的一個子圖的邊集中的任意兩條邊都不依附于同一個頂點，則稱此子圖是一個匹配。選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問題(maximal matching problem)如果一個匹配中，圖中的每個頂點都和圖中某條邊相關聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配。增廣路對于右圖的邊，如果我們一開始僅有已經(jīng)完成的匹配1-1，4-3。那么當我們對于2，可以讓已經(jīng)有的

2、匹配做下修改，即4-4，1-3，空出來1和2進行匹配，這樣沿著已有匹配去尋找到的新匹配叫增廣路。544332211匈牙利算法1.對于左邊的每個點，看看右邊有沒有增廣路，如果有，那么進行增廣，沒有就不添加新的匹配。2.當對最后一個點做完增廣路以后，整個圖就形成了一個最大匹配。二分圖的最小覆蓋數(shù)棋盤上有N個點，每次可以拿走一行或者一列。問最少多少次可以把棋盤上的所有點都拿走poj3041將行作為左邊的點，列作為右邊的點，原圖中的每個點形成一條邊，將代表其行和列的點連接起來。對已經(jīng)建好的圖求最大匹配Konig定理最大匹配數(shù)=最小覆蓋數(shù)二分圖的最大獨立數(shù)一張殘缺的棋盤，用1*2的矩形去覆蓋它，要求矩形

3、不互相重疊。求矩形最多可以放多少個。將棋盤染成黑白相間，黑色方格作為左邊的點，白色方格作為右邊的點，相鄰的黑白方格中間連一條邊。對已經(jīng)建好的圖求最大匹配最大獨立數(shù)=最大匹配數(shù)最小路徑覆蓋一張圖n個點，給定某些點之間可以用線連起來。問最少畫多少筆才能將所有的點全部蓋住poj1422將n個點拆成2n個點，如1號變?yōu)?和1，1代表出邊，1代表進邊。對于每個結點，將與其相臨的邊連出來。對已經(jīng)連好的圖求最大匹配數(shù)最小路徑覆蓋數(shù)=頂點數(shù)n-最大匹配數(shù)Nkoj 1684 courses1465 Taxi Cab Scheme1681 Girls and boys1070 信和信封的問題poj2239 Selecting Courses1422 Air Raid 最小路徑覆蓋1325 Machine Schedule1719 Shooting Contest2594 Treasure Exploration2195 Going Home帶權二分圖(km算法)2446 Chessboard1904 Kings Quest3342 Party at Hal