支配集合

グラフG=(V,E)がある。今、Vの部分集合Wを考える。Vの要素のすべてがWの要素であるか、もしくは、Wの要素のどれかひとつに隣接しているとき、WをGの支配集合と言う。

グラフGの頂点の数をnとする。n個の頂点の次数(接続する辺の数)の最小数(Gの最低次数)をp

とするとき、個以下の支配集合が存在する：定理

アルゴリズム・サイエンス:出口からの超入門 (アルゴリズム・サイエンスシリーズ―超入門編)

の第５章 乱数を利用する から。

掲載図の原図はこちら

描図用エクセルはこちら