698
【算法小總結】二分圖的最大獨立集
如果一個圖是二分圖，那麼它的最大獨立集就是多項式時間可以解決的問題了 |最大獨立集| = |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|
例題：
https://blog.csdn.net/acmman/article/details/38564159
最後更新：2017-04-03 05:39:54