2012-10-02から1日間の記事一覧
問題リンク Dominating Set 概要 グラフG = (V, E)の支配集合Dとは、D ⊆ V で、V-Dの全ての頂点が、少なくとも1つのDと隣接しているようなもののことを言う。 与えられるグラフの支配集合のうち、最小の要素数を答えよ。 解法 この問題、おっそろしいことに…
問題リンク Dominating Set 概要 グラフG = (V, E)の支配集合Dとは、D ⊆ V で、V-Dの全ての頂点が、少なくとも1つのDと隣接しているようなもののことを言う。 与えられるグラフの支配集合のうち、最小の要素数を答えよ。 解法 この問題、おっそろしいことに…