支配集合問題

ウィキペディア

支配集合問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/04/20 13:42 UTC 版)

支配集合問題（しはいしゅうごうもんだい、英: dominating set）は、グラフ理論における有名なNP困難な問題の一つ。与えられたグラフ G(V, E) の頂点集合 V′ (⊆ V) で、V′ に属さない全ての頂点 v について、v の隣接頂点のいずれか一つが V′ に属するような V′ （支配集合）のうち、最小のものを求める問題。