-
给定无向图
，如果子集
且对于任意两个顶点
，有
，则称U是G的完全子图。G的最大团即G的最大完全子图。 -
G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中
-
G的最大团是指G中所含顶点数最多的团
- 例如，子集{1，2}是G的一个大小为2的完全子图，但不是一个团，因为它包含于G的更大的完全子图{1，2，5}中。{1，2，5}、{1，4，5}和{2，3，5}都是G的最大团。
-
问题空间（input）
-
解空间（output）
- 图G的顶点集V的子集选取问题，xi∈{0，1}
- 约束函数：团
- 目标函数：所含顶点数最多
-
解空间树（所有可能解的结构）
- 子集树
-
搜索空间（最优解的求解过程）
- 约束函数
- 顶点i到已选入的顶点集中每一个顶点都有边相连
- 限界函数
- 有足够多的可选择顶点使得算法有可能在右子树中找到更大的团
- 约束函数
学习课程链接：https://www.bilibili.com/video/BV1d7411X7JK?spm_id_from=333.1007.top_right_bar_window_custom_collection.content.click
