求图论的生成子图算法，要求生成尽可能多的子图

显示全部楼层 · 2010-12-26 23:29:15

有n个人，其中每个人都认识其中的k个人或者一个都不认识，将他们4人一组进行分组，每组中的4个人必须两两相互认识，要求分组数量最多或者尽可能的多。
感觉应该就是图论的问题：把人看做节点，相互认识的两人就是联通的两点，问题就是尽可能多的找出包含4个节点的完全生成子图。
哪位高手能够给出应该用什么算法解决，或者给出思路也可，谢过！

千问 · 2010-12-26 23:29:15

在图论的历史中，还有一个最著名的问题－－四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。20世纪80-90年代曾邦哲的综合系统论（结构论）观将“四色猜想”命题转换等价为“互邻面最大的多面体是四面体”。四色猜想有一段有趣的历史。每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接。所以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。（下图是在上下对折再左右对折以后形成一个轮胎形状，有7个区域两两相连，就是说在一个环