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

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

0 голосов
/ 11 ноября 2018

Было бы здорово, если бы кто-то мог мне помочь.

У меня есть неориентированный граф, где каждая вершина имеет вес, и где нет ребер, имеющих вес. Я хочу найти набор узлов с минимальным общим весом, для которого их удаление делает граф отключенным. Например, между удалением одного узла весом 10, который отключает граф, и удалением двух узлов общим весом 6, что отключает граф, набор результатов должен содержать эти 2 узла.

Есть ли какой-нибудь известный алгоритм для этой проблемы?

Вот что я сделал до сих пор. Я сделал свой код, используя networkx (python). Я уже изменил свой график, чтобы быть направленным. Например, для узла 1 я рассматриваю 1in и 1out узел. и я соединяю 1in к 1out весом узла 1. Я также добавляю s и t узлы (я не уверен, правильно это или нет). Я определил также емкость для каждого ребра в новом ориентированном графе.

При запуске кода я получаю эту ошибку: NetworkXUnbounded: Infinite capacity path, flow unbounded above.

deg_G = nx.degree(G)
max_weight = max([deg for i,deg in deg_G])+1

st_Weighted_Complement_G = nx.DiGraph()
r = np.arange(len(Complement_G.nodes))

nodes = ['s','t']
edges = []
for i in r:
    nIn = (str(i)+'in')
    nOut = (str(i)+'out')
    nodes.extend([nIn,nOut])
    edges.extend([(nIn,nOut,{'capacity':deg_G[i],'weight':deg_G[i]}),('s',nIn,{'capacity':math.inf,'weight':0}),
                  (nOut,'t',{'capacity':math.inf,'weight':0})])

for edge in Complement_G.edges:
    print(edge[0],edge[1])
    edges.extend([((str(edge[0]))+'out',(str(edge[1]))+'in',{'capacity':max_weight,'weight':0}),
                  ((str(edge[1]))+'out',(str(edge[0]))+'in',{'capacity':max_weight,'weight':0})])

print(edges)
st_Weighted_Complement_G.add_nodes_from(nodes)
st_Weighted_Complement_G.add_weighted_edges_from(edges)

mincostFlow = nx.max_flow_min_cost(st_Weighted_Complement_G, 's', 't',capacity='capacity',weight='weight')
print(mincostFlow)

Спасибо

...