5

这可能是一个愚蠢的问题，但是什么是规范问题，它要求从图中获取最小的顶点集，以便从这些顶点中，通过“旅行”不超过一条边可以到达所有其他顶点？现实生活中的应用是：我需要认识哪些人，才能与地球上的其他人只有一个度数？谢谢！

4

1 回答 1

3

我认为这是Domination Set Problem，与正常的 set cover 问题密切相关

于 2012-10-24T11:26:44.083 回答