這兩個(gè)東西其實(shí)是互斥的關(guān)系垂攘，而這兩個(gè)東西的應(yīng)用也是十分有趣的维雇。
Vertex Cover
先來說說什么是 Vertex Cover，其實(shí)就是節(jié)點(diǎn)的集合晒他，這些節(jié)點(diǎn)將最大地包含圖里的所有邊谆沃，更恰當(dāng)?shù)拿謶?yīng)該是 Minmum Vertex Cover，以選最少的節(jié)點(diǎn)來囊括所有的邊仪芒。以下圖為例
其中紅色圈出來的節(jié)點(diǎn)就是 Vertex Cover唁影。
Independent Set
再來說說 Independent Set，這也是節(jié)點(diǎn)的集合掂名，一般是指 Maximum Independent Set据沈，是說找到最多的節(jié)點(diǎn)，這些節(jié)點(diǎn)都不是相鄰的饺蔑。
再以上圖為例锌介，沒有紅色圈出來的節(jié)點(diǎn)都是 Maximum Independent Set。
由此我們可以得出一個(gè)結(jié)論
二分圖里找 VC 和 IS
在如下二分圖中怎么才能找到 Minimum Vertex Cover 和 Maximum Independent Set 呢猾警？其實(shí)只要解決一個(gè)就可以了孔祸，剩下的那個(gè)就是所有節(jié)點(diǎn)減去前者節(jié)點(diǎn)即可。
要解決這個(gè)問題发皿，我們要用到最大流和最小割的知識崔慧。首先添加 S 和 T，并將它們與各自兩邊連接起來穴墅。
其中每條邊的權(quán)重都為 1惶室。找到這個(gè)圖的最大流和最小割如下
原來屬于 S 那邊如果被分到了 T 這邊就是 Vertex Cover 的一員，反之亦然玄货，所以我們可以得到 Vertex Cover 的集合是右上角的節(jié)點(diǎn)和左下角的節(jié)點(diǎn)皇钞，而剩下的節(jié)點(diǎn)就屬于 Independent Set。
上面就是如何在二分圖里找 Vertex Cover 和 Independent Set 的過程松捉。
應(yīng)用
現(xiàn)在來真正地就用 Vertex Cover 和 Independent Set夹界。假如現(xiàn)在有如下圖形
要求：怎么切割才能使得切出來的長方形數(shù)量最少呢？
首先我們只切割“有兩個(gè)角”的部位隘世。
用這些切割后的邊畫成二分圖可柿，將切邊看成節(jié)點(diǎn)也拜，只要兩條切邊相交就畫一條邊將兩個(gè)切邊連起來。
然后在這個(gè)二分圖里找 Vertex Cover 和 Independent Set趾痘，找出來的 Independent Set 數(shù)目再加 1 就是切割最少的數(shù)目慢哈。為什么要加 1 呢，因?yàn)槿绻?Independent Set 數(shù)量去切還會剩下一個(gè) "L" 形結(jié)構(gòu)永票，所以還需要額外的一刀才能保證切出來的是長方形卵贱。
