最大独立集合問題

ウィキペディア

最大独立集合問題

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

最大独立集合問題（さいだいどくりつしゅうごうもんだい）は、グラフ理論において、与えられたグラフ G(V,E) に対して、頂点集合 V'⊆V のうち V' 内の頂点間に枝が存在しないようなもの（独立集合）で大きさが最大のものを求める問題。最大安定集合問題とも言う。この問題は、NP困難であることが知られている。