dominating_set#

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

找到图 G 的一个支配集。

图的 支配集 是指节点集合 V 的一个子集 D，使得 D 外的每个节点都至少与 D 中的一个成员相邻 [1]。

Parameters:

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

Returns:

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

See also

is_dominating_set

Notes

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

References

[1]

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

[2]

Abdol-Hossein Esfahanian. Connectivity Algorithms. http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf