続(4) - 最大クリーク問題
多分4じゃないかと思う。ナンバリングは適当
グラフが非連結でk個のグラフに分割できるとして、n(頂点数),m(辺数),w(補グラフの辺数)と分割後の各n,m,wをとすると下記が成り立つ
補グラフが非連結も同様
すげぇコンパクトになるんですけどって感じだ。
これが何につながるかというと最大クリーク問題なわけで、例えば頂点数100で、補グラフがのような非連結のグラフのとき、元のグラフではサイズ50のクリークが個あるわけだけど、補グラフで考えると一気に頂点2 * 連結成分50の問題になる。
とはいえ、きっとよく知られた内容だとおもうんだけど、自分的にはこれは結構すごいなと感動した。