2006-11-08から1日間の記事一覧

支配集合

グラフG=(V,E)がある。今、Vの部分集合Wを考える。Vの要素のすべてがWの要素であるか、もしくは、Wの要素のどれかひとつに隣接しているとき、WをGの支配集合と言う。 グラフGの頂点の数をnとする。n個の頂点の次数(接続する辺の数)の最小数(Gの最低次数)をp …