求图论的生成子图算法,要求生成尽可能多的子图有n个人,其中每个人都认识其中的k个人或者一个都不认识,将他们4人一组进行分组,每组中的4个人必须两两相互认识,要求分组数量最多或者尽
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/27 19:48:26
求图论的生成子图算法,要求生成尽可能多的子图有n个人,其中每个人都认识其中的k个人或者一个都不认识,将他们4人一组进行分组,每组中的4个人必须两两相互认识,要求分组数量最多或者尽
求图论的生成子图算法,要求生成尽可能多的子图
有n个人,其中每个人都认识其中的k个人或者一个都不认识,将他们4人一组进行分组,每组中的4个人必须两两相互认识,要求分组数量最多或者尽可能的多.
感觉应该就是图论的问题：把人看做节点,相互认识的两人就是联通的两点,问题就是尽可能多的找出包含4个节点的完全生成子图.
哪位高手能够给出应该用什么算法解决,或者给出思路也可,谢过!
求图论的生成子图算法,要求生成尽可能多的子图有n个人,其中每个人都认识其中的k个人或者一个都不认识,将他们4人一组进行分组,每组中的4个人必须两两相互认识,要求分组数量最多或者尽
连通图的特点是图中任意两点都是连通的,也就是说只要从任意一点出发能够到达所有的点就能够证明是连通图,否则就是不连通图
因为不知道你准备采用什么,具体算法我就不写语言了,只是解释一下原理：
1 采用数组、链表或数组,先将所有顶点定义在数组POINT中.
2 采用二维数组,将所有边（线段）定义在二维数组LINE中,记录两遍,边的两个顶点分别作为第一项如（v0,v3）(v3,v0).
3 取出一个顶点v0加入到新数组CONPOINT中,并在顶点数组POINT中删除.
4 while循环,停止条件是CONPOINT中都标记着已读
{
从CONPOINT中取出一个有未读标记的顶点X,并作已读标记.
从二维数组LINE中查找第一项中包含X的边,将选出边的第二个顶点（1个或多个）取出,并加入到新数组CONPOINT中,并作未读标记（如果已有该点则不作插入）
将选出的边从二维数组LINE中删除.
}
比较CONPOINT和POINT数量,如果少了则不是连通图