支配集合



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

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

とするとき、n¥times ¥frac{1+¥ln(p+1)}{p+1}個以下の支配集合が存在する:定理

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

掲載図の原図はこちら

描図用エクセルはこちら