Algorithms/RandomAlgorithm - tmura's note - atwiki（アットウィキ）

Algorithms > RandomAlgorithm

乱択アルゴリズム

代表的な問題

グラフの塗り分け問題

完全グラフの全ての枝を２色で塗り分ける場合に同色のクリークが現れる確率に関する定理: $n$ を $n \leq 2^{2^{k/2}}$ を満たす整数とする。; このとき、 $n$ 頂点の完全グラフの各枝を青と赤でランダムに塗り分けると、; 高い確率で $k$ 頂点の同色のクリークは現れない。

グラフの支配集合

グラフ $G = (V,E)$ の頂点部分集合 $U \subseteq V$ を考える。
このとき、グラフの全ての頂点 $u$ に対して、 $u$ が $U$ に入っているか $U$ の頂点に隣接している
という条件を満たしているとき、 $U$ は''支配集合 (dominating set)''であるという。