题目
求图论的生成子图算法,要求生成尽可能多的子图
有n个人,其中每个人都认识其中的k个人或者一个都不认识,将他们4人一组进行分组,每组中的4个人必须两两相互认识,要求分组数量最多或者尽可能的多.
感觉应该就是图论的问题:把人看做节点,相互认识的两人就是联通的两点,问题就是尽可能多的找出包含4个节点的完全生成子图.
哪位高手能够给出应该用什么算法解决,或者给出思路也可,谢过!
有n个人,其中每个人都认识其中的k个人或者一个都不认识,将他们4人一组进行分组,每组中的4个人必须两两相互认识,要求分组数量最多或者尽可能的多.
感觉应该就是图论的问题:把人看做节点,相互认识的两人就是联通的两点,问题就是尽可能多的找出包含4个节点的完全生成子图.
哪位高手能够给出应该用什么算法解决,或者给出思路也可,谢过!
提问时间:2021-02-02
答案
连通图的特点是图中任意两点都是连通的,也就是说只要从任意一点出发能够到达所有的点就能够证明是连通图,否则就是不连通图
因为不知道你准备采用什么,具体算法我就不写语言了,只是解释一下原理:
1 采用数组、链表或数组,先将所有顶点定义在数组POINT中.
2 采用二维数组,将所有边(线段)定义在二维数组LINE中,记录两遍,边的两个顶点分别作为第一项如(v0,v3)(v3,v0).
3 取出一个顶点v0加入到新数组CONPOINT中,并在顶点数组POINT中删除.
4 while循环,停止条件是CONPOINT中都标记着已读
{
从CONPOINT中取出一个有未读标记的顶点X,并作已读标记.
从二维数组LINE中查找第一项中包含X的边,将选出边的第二个顶点(1个或多个)取出,并加入到新数组CONPOINT中,并作未读标记(如果已有该点则不作插入)
将选出的边从二维数组LINE中删除.
}
比较CONPOINT和POINT数量,如果少了则不是连通图
因为不知道你准备采用什么,具体算法我就不写语言了,只是解释一下原理:
1 采用数组、链表或数组,先将所有顶点定义在数组POINT中.
2 采用二维数组,将所有边(线段)定义在二维数组LINE中,记录两遍,边的两个顶点分别作为第一项如(v0,v3)(v3,v0).
3 取出一个顶点v0加入到新数组CONPOINT中,并在顶点数组POINT中删除.
4 while循环,停止条件是CONPOINT中都标记着已读
{
从CONPOINT中取出一个有未读标记的顶点X,并作已读标记.
从二维数组LINE中查找第一项中包含X的边,将选出边的第二个顶点(1个或多个)取出,并加入到新数组CONPOINT中,并作未读标记(如果已有该点则不作插入)
将选出的边从二维数组LINE中删除.
}
比较CONPOINT和POINT数量,如果少了则不是连通图
举一反三
已知函数f(x)=x,g(x)=alnx,a∈R.若曲线y=f(x)与曲线y=g(x)相交,且在交点处有相同的切线,求a的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
最新试题
- 1look at these presents.Are thes e her presents.
- 2明矾溶液和Ba(OH)2的反应式
- 3求y=x的平方+x的平方分之一+2006的最小值
- 4一堆煤160吨,4辆卡车3次运96吨.照这样计算,4辆卡车几次才能运完这堆煤?
- 5小学六年级下册美术书目录
- 6化简1.√ 1200
- 7甲乙两人同时从A地出发去B地甲以1m/s的速度走完了前一半路程后又以1.5m/s的速度走完了后一半路程乙则是在他所用前一半时间内以1m/s的速度行走,后一半时间内以1.5m/s的速度行走,问甲乙两人谁
- 8九宫图(在线等)
- 9一个长方形的周长是72厘米,长和宽的比是5:4,这个长方形的面积是多少平方厘米?
- 10some she noodles is making连词成句
热门考点
- 1瑞利-金斯线是什么
- 2JAVA编程 输入两个正整数m和n,输出它们的最小公倍数和最大公约数
- 3英语:penpal是一个单词还是两个?音标怎么写?
- 4如图所示,已知AB为⊙O的直径,C、D是直径AB同侧圆周上两点,且弧CD=弧BD,过D作DE⊥AC于点E,求证:DE是⊙O的切线.
- 5世上为什么会有人类的出现
- 6X ,Y 为有理数,设X*Y=AX+BY+C,若1*2=9,(-3)*(3)=6,求2*(-7)?
- 7一个圆形餐桌面的半径是2米,它的周长是多少米?面积是多少平方米?如果一个人需要0.4米的位置就餐,这张
- 8Mr.Gao is eighty yeas old,but he has some m____ ideas.
- 9为什么今天晚上月亮周围有很大一个圈?
- 10铁勺的质量是210克 的物理意义是什么