Простой способ найти минимальное количество узлов, которые соединяются с каждым узлом на графике

Question

У меня есть ненаправленная сеть узлов, соединенных друг с другом в виде сетки (то есть степень каждого узла> = 2). Я пытаюсь найти способ найти минимальное количество узлов, которые подключаются к другим узлам в сети.

Например, если у меня есть 10 узлов в моем графике, и один из узлов соединен со всеми другими узлами, то я могу прямо сказать, что узел - это тот, который соединяет весь мой граф и минимальное количество узлов с покрытие связности графа составляет 1.

Но обычно это не так, так как мне нужно найти другие узлы вручную. Я думаю, что я могу использовать узел наивысшей степени (например, x) в качестве источника, чтобы найти кратчайшие пути к другим узлам, используя nx.shortest_path(G, x). Затем я могу перебрать кратчайшие пути, чтобы найти другие узлы. Но этот метод утомителен, и мне интересно, есть ли у кого-нибудь другое предложение, использующее инструменты, доступные в networkx, для оптимального решения этой проблемы.

Answer 1

Как упомянуто здесь: https://networkx.github.io/documentation/stable/reference/algorithms/dominating.html

Доминирующим набором для графа с множеством узлов V является подмножество D в V, так что каждый узел, не входящий в D, смежен схотя бы один член D

 D= nx.dominating_set(G, x) # the node source here is optional
 print(D)