最大團學習

定義:1. 無向圖的最大獨立數: 從v個頂點中選出k個頂，使得這k個頂互不相鄰。那麼最大的k就是這個圖的最大獨立數.

2. 無向圖的最大團: given a graph g(v, e), a clique is a sub-graph g(v, e), so that for all vertex pairs v1, v2 in v, there exists an edge (v1, v2) in e.

maximum clique is the clique that has maximum number of vertex. （就是從v個頂點擊出k個頂，使得這k個頂構成乙個完全圖，即該子圖任意兩個頂都有直接的邊）

兩者的關係:

1. 原來在圖論課上，就學了圖論中這些有用的數字: 最小覆蓋數，最大獨立數，最大匹配數，最大團的數等等。由上面兩者的定義可知:

最大團的個數 = 補圖的最大獨立數

ps: 原來學二分匹配時就整理過這些數字，他們之間關係是很多。如:

最小覆蓋數+最大獨立數 = 頂點數。雖然求出他們都是np問題。但對於特殊的圖還是有好的演算法的，如:

在二分圖中，最小覆蓋數等於最大匹配數，而最大獨立數又等於頂點數減去最小覆蓋數，所以可以利用匈牙利求出最大獨立數等等。所以pku1419其實也可以轉化成最大團，取圖g的補圖，然後呼叫最大團模板(恩，用這種方法ac的更快)

2. zxr今天也說了一下無向圖中的最大團與有向圖中的強連同分量的對比，贊~

實現的演算法:

對於這兩個np問題，自己都是用dfs+剪枝實現的。特別是對於最大團的實現，還用到了dp的思想(下面會提到最大團的實現演算法). 呵呵，不錯的一句話:

無向圖的最大團和最大獨立集問題都可以看作是圖g的頂點集v的子集選取問題, 可以用回溯法在o(n*(2^n))時間內解決。

pku1419-graph coloring

題目大意:

zju1002 - fire net

題目大意:

zju1492-maximum clique

題目大意: 輸入乙個無向圖g，輸出它的最大團個數.

分析首先很讚今天學習到的方法，算起來用了4個剪枝。

1. 剪枝1：常用的指定順序, 即列舉第i個頂後, 以後再列舉時枝考慮下標比大它的, 避免重複。

2. 剪枝2：自己開始從前往後的列舉頂點, tle兩次.

後來從後往前列舉頂點，發現可以利用頂點之間的承襲性.我用num[i] 記錄的可選頂點集合為 v[i, i+1, ... , n] 中的最大團數目，目標是求num[1].

分析易知, num[i] = num[i+1] 或者 num[i]+1 (num[1...n] 具有非降的單調性,從後往前求)

由這個式子以及num資訊的記錄，使得我們可以增加兩處剪枝:

3.上/下剪枝：假設當前列舉的是頂點x, 它的第乙個鄰接頂是i (標號一定比x大，即num[i]已經求出) 我們可以知道，若 1 + num[i] <= best, 那麼是沒沒要往下列舉這個頂點x了，因為包含它的團是不可能超過我們目前的最優值的。

4. 立即返回剪枝: 由於num[i]最大可能為num[i+1]+1, 所以在列舉頂點i時，只要一更新best，可知此時的num[i]就為num[i+1]+1了，不需要再去嘗試找其他的方案了，所以應立即返回.

// 剛整理的最大團模板, 所需要提供的就是: 頂點個數n, 以及無向圖的鄰接矩陣g.

int best;

int num[maxn];

//int x[maxn]; // 取決於是否需要最優解.若需要，還要增加乙個path[maxn]陣列

int maximumclique()

bool dfs(int *adj, int total, int cnt)

for (i=0; i

return false;}