关于图论的一个有关问题
关于图论的一个问题
给出一个图 ，连接关系如下：1-3，1-4，2-5，3-4，3-7，4-5，5-6，5-8；示意图：
图中有一些点需要染红，要求 图中所有的点，要么自己是红色的，要么与自己K相邻的点中有红色的点（存在一个红色的点与自己的距离为K），求至少有几个红色的点。对于上述例子，K=1时，红色的点为两个，3，5
请教大家一个算法，输入是 节点之间关系，以及K ，求最少的红色点
------解决方案--------------------
minimum dominating set
给出一个图 ，连接关系如下：1-3，1-4，2-5，3-4，3-7，4-5，5-6，5-8；示意图：
图中有一些点需要染红，要求 图中所有的点，要么自己是红色的，要么与自己K相邻的点中有红色的点（存在一个红色的点与自己的距离为K），求至少有几个红色的点。对于上述例子，K=1时，红色的点为两个，3，5
请教大家一个算法，输入是 节点之间关系，以及K ，求最少的红色点
------解决方案--------------------
minimum dominating set