UC知道有向图的算法
来源：百度知道 编辑：UC知道 时间：2024/05/01 03:28:51
问题：已知G是有向图，且G的每个顶点都在一个回路中。在G中选择n个顶点作为已知状态，然后在这n个顶点的基础上计算其他所有顶点的状态，现在要设计使n最小的算法。
注释：一个顶点能被“计算”出来指与这个顶点入边相连的顶点的状态都知道，就可计算出这个顶点，可看图片，图片中的图若选择顶点2作为已知状态，那么顶点3可以被计算处理，因为与顶点3的入边相连的顶点2的状态已知，同理顶点4也可被计算处理，所以说选择2顶点作为已知，可以计算出其他所有顶点，另一种选法是选择顶点1和顶点4作为已知顶点，但这不是最优的。
问题总结一下：G中选n个顶点作为已知来计算其他所有的顶点，设计算法求出使n最小的顶点选择方法。
哪位如果给出高效的算法（因为图的顶点较多，算法的效率显得很重要），我再给分。
一个回路中已知一个顶点有时还无法求出回路中其他的顶点，看图中的2-3-4回路，只知道顶点3或4，都无法计算顶点2。只有在知道2顶点时，才能计算出其他顶点，如果图中还有从顶点3到顶点3的边，那么回路2-3-4即使以顶点2作为已知，也无法计算3和4顶点。最小的n应该不等于图G中的极大连通子图的个数。感谢 绝__影 朋友的回答。
注释：一个顶点能被“计算”出来指与这个顶点入边相连的顶点的状态都知道，就可计算出这个顶点，可看图片，图片中的图若选择顶点2作为已知状态，那么顶点3可以被计算处理，因为与顶点3的入边相连的顶点2的状态已知，同理顶点4也可被计算处理，所以说选择2顶点作为已知，可以计算出其他所有顶点，另一种选法是选择顶点1和顶点4作为已知顶点，但这不是最优的。
问题总结一下：G中选n个顶点作为已知来计算其他所有的顶点，设计算法求出使n最小的顶点选择方法。
哪位如果给出高效的算法（因为图的顶点较多，算法的效率显得很重要），我再给分。
一个回路中已知一个顶点有时还无法求出回路中其他的顶点，看图中的2-3-4回路，只知道顶点3或4，都无法计算顶点2。只有在知道2顶点时，才能计算出其他顶点，如果图中还有从顶点3到顶点3的边，那么回路2-3-4即使以顶点2作为已知，也无法计算3和4顶点。最小的n应该不等于图G中的极大连通子图的个数。感谢 绝__影 朋友的回答。
楼上的真是，估计没明白楼主意思吧。。。明显可以证明这个图是完全强连通的，这个也不难看出来。
但是这个问题本身比较怪异，开始怀疑是不是 NP。
初步感觉，应该归约成某种网络流吧。。
我再想想吧。。想到了再贴上来吧，楼主放这么重本，不想出来也不好意思收啊。。
我来试试。
既然每个顶点都在一个回路中，那么，一个回路只要有一个顶点已知，那么，这个回路里面所有的顶点都已知了。
因此，最小的n就等于图G中的极大连通分量的个数。然后根据每个顶点继续寻找下一顶点，直到所有顶点都遍历完成。
这是算法的基本思想。