【算法小總結】二分圖的最大獨立集

如果一個圖是二分圖，那麼它的最大獨立集就是多項式時間可以解決的問題了 |最大獨立集| = |v|-|最大比對數|

證明：

設最大獨立集數為u，最大比對數為m，m覆寫的頂點集合為em。

為了證明|u|=|v|-|m|，我們分兩步證明|u|<=|v|-|m|和|u|>=|v|-|m|

1 .先證明 |u|<=|v|-|m|

m中的兩個端點是連接配接的，所有m中必有一個點不在|u|集合中，是以|m|<=|v|-|u|

2. 再證明|u|>=|v|-|m|

假設(x,y)屬于m

首先我們知道一定有|u|>=|v|-|em|，那麼我們将m集合中的一個端點放入u中可以嗎？

假設存在(a,x)，(b,y)，(a,b)不在em集合中

如果(a,b)連接配接，則有一個更大的比對存在，沖突

如果(a,b)不連接配接，a->x->y->b有一個新的增廣路，是以有一個更大的比對，沖突

是以我們可以了解到取m中的一個端點放入u中肯定不會和u中的任何一個點相連，是以|u|>=|v|-|em|+|m|=|v|-|m|

是以，|u|=|v|-|m|

例題：

http://blog.csdn.net/acmman/article/details/38564159