提问人：Exodus 提问时间：11/16/2023 最后编辑：TimelessExodus 更新时间：11/16/2023 访问量：62
满足给定边数的最小节点集 [closed]
Minium set of nodes that satisfy the given number of edges [closed]
问：
例如，我们有如下所示的邻接列表。如果所需的边数为 2，则足够的节点集为 （1,2）、（1,3）、（1,4）、（2,3） 和 （3,4）。如果所需的边数为 3，则足够多的节点集为无。如果所需的边数为 4，则足够的节点集为 （1， 2， 4） 和 （2， 3， 4）。
# Sample adjacency list
adjacency_list = {
1: [2, 3, 4],
2: [1, 3],
3: [1, 2, 4],
4: [1, 3]
}
我对图论相当陌生，我用谷歌或聊天 GPT 搜索没有成功。我觉得这可能是一个 DP 问题，但真的不知道什么是有效的方法。任何建议将不胜感激。
答：
1赞
Timeless
11/16/2023
#1
IIUC，这是一个有向图问题。 如果是这样，并且您很想使用 networkx，请尝试以下方法：
import networkx as nx
from itertools import chain, combinations
G = nx.DiGraph(adjacency_list)
def combs(lst):
return chain(*map(lambda x: combinations(lst, x), range(1, len(lst)+1)))
def get_nodes(G, nb_edges):
for c in combs(G.nodes):
if G.subgraph(c).number_of_edges() == nb_edges:
yield c
测试/输出 ：
op_vals = [2, 3, 4]
for v in op_vals:
print(f"for {v} edges, {list(get_nodes(G, v))} suffice!")
# for 2 edges, [(1, 2), (1, 3), (1, 4), (2, 3), (3, 4)] suffice!
# for 3 edges, [] suffice!
# for 4 edges, [(1, 2, 4), (2, 3, 4)] suffice!
边（蓝色）所需的节点集（黄色）的可视化：4
评论
1赞
Exodus
11/16/2023
哇 - 非常感谢！你最棒！！
评论