dominating_set#

dominating_set(G, start_with=None)[source]#

找到图 G 的一个支配集。

对于节点集为 V 的图，其 支配集 是 V 的一个子集 D，使得每个不在 D 中的节点都邻接到 D 中的至少一个成员 [1]。

参数:

GNetworkX 图
start_with节点 (默认=None): 用作算法起点的节点。

返回:

D集合: 图 G 的一个支配集。

另请参阅

is_dominating_set

注释

此函数实现了 [2] 中的算法 7，它找到一个支配集，但不一定是最小支配集。

参考资料

[1]

https://en.wikipedia.org/wiki/Dominating_set

[2]

Abdol-Hossein Esfahanian. 连通性算法。 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf