【每日算法】【圖論】【最小邊覆寫 & 最小路徑覆寫 & 最小頂點覆寫 & 最大獨立集 & 最大團】

最小邊覆寫 = 最大獨立集 = |V| - 最大比對數

這個是在原圖是二分圖上進行的

最小路徑覆寫和最小邊覆寫不同，不要求給的圖是二分圖，而是要求是N x N的有向圖，不能有環，然後根據原圖構造二分圖，構造方法是将點一分為二，如，i分為i1和i2然後如果i和j有邊，那麼就在i1和j2之間連一條邊。由此構成二分圖

然後最小路徑覆寫 = n-m，n為原圖的點的個數，m為新造二分圖的最大比對。證明也是特别簡單的，根據定義最小路徑覆寫裡要求同一個點隻可以屬于一條路徑，即路徑時不可以開叉的，如果在二分圖裡選兩條有公共點的邊那麼反應在原圖上就是路徑有岔路了，是以二分圖裡選的邊必須是無公共交點的，這就是轉化到最大比對了。

總結：

【無向圖的最大獨立數】: 從V個頂點中選出k個頂，使得這k個頂互不相鄰。 那麼最大的k就是這個圖的最大獨立數。

【無向圖的最大團】:  從V個頂點選出k個頂，使得這k個頂構成一個完全圖，即該子圖任意兩個頂都有直接的邊。

【最小路徑覆寫(原圖不一定是二分圖，但必須是有向圖，拆點構造二分圖)】：在圖中找一些路徑，使之覆寫了圖中的所有頂點，且任何一個頂點有且隻有一條路徑與之關聯。最小路徑覆寫 = |V| - 最大比對數

【最小邊覆寫(原圖是二分圖)】：在圖中找一些邊，使之覆寫了圖中所有頂點，且任何一個頂點有且隻有一條邊與之關聯。最小邊覆寫 = 最大獨立集 = |V| - 最大比對數

【最小頂點覆寫】：用最少的點（左右兩邊集合的點）讓每條邊都至少和其中一個點關聯。

PS: 原來學二分比對時就整理過這些數字，他們之間關系是很多。如: 最小覆寫數+最大獨立數 = 頂點數。 雖然求出他們都是np問題。但對于特殊的圖還是有好的算法的，如:

在二分圖中，最小覆寫數 等于 最大比對數，而最大獨立數又等于頂點數減去最小覆寫數(=最大比對數)，是以可以利用匈牙利求出最大獨立數等等。

a.點覆寫集：無向圖G的一個點集，使得該圖中所有邊都至少有一點端點在該集合内。

b.點獨立集：無向圖G的一個點集，使得任兩個在該集合中的點在原圖中不相鄰。

c.最小點覆寫集：無向圖G中點數最少的點覆寫集

d.最大點獨立集：無向圖G中，點數最多的點獨立集

e.最小點權覆寫集：帶點權的無向圖中，點權之和最小的點覆寫集

f.最大點權獨立集：實在帶點權無向圖中，點權之和最大的點獨立集

性質：

最大團 = 補圖的最大獨立集

最小邊覆寫 = 二分圖最大獨立集 = |V| - 最小路徑覆寫

最小路徑覆寫 = |V| - 最大比對數

最小頂點覆寫 = 最大比對數

最小頂點覆寫 + 最大獨立數 = |V|