続(4) - 最大クリーク問題

多分4じゃないかと思う。ナンバリングは適当



グラフが非連結でk個のグラフに分割できるとして、n(頂点数),m(辺数),w(補グラフの辺数)と分割後の各n,m,wを n_i, m_i, w_iとすると下記が成り立つ
 n = \sum_{i=1}^k n_i \\
m = \sum_{i=1}^k m_i \\
w = \sum_{i=1}^k w_i + \sum_{i \ne j} n_i  n_j

補グラフが非連結も同様
 n = \sum_{i=1}^k n_i\\
m = \sum_{i=1}^k m_i + \sum_{i \ne j} n_i n_j\\
w = \sum_{i=1}^k w_i

すげぇコンパクトになるんですけどって感じだ。

これが何につながるかというと最大クリーク問題なわけで、例えば頂点数100で、補グラフが K_2 * 50のような非連結のグラフのとき、元のグラフではサイズ50のクリークが 2^{50}個あるわけだけど、補グラフで考えると一気に頂点2 * 連結成分50の問題になる。

とはいえ、きっとよく知られた内容だとおもうんだけど、自分的にはこれは結構すごいなと感動した。