dominating_set

dominating_set(G, start_with=None)

找到图G的控制集。

A 支配集 对于具有节点集的图 V 是一个子集 D 的 V 使得不在中的每个节点 D 与至少一个成员相邻 D [1].

参数

G网络X图表

start_with节点(默认=无)

节点用作算法的起始点。

返回

D设置

G的一个控制集。

参见

is_dominating_set

笔记

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

工具书类

1

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

2

Abdol Hossein Esfahanian。连接算法。http://www.cse.msu.edu/~cse835/papers/graph_connectivity_revised.pdf