基于边权重的节点分离算法

Question

我需要一种算法，将无向图中的所有节点分成两个子图，以便具有重权重边的节点位于不同的子图中。

输入示例：

A - B (Weight = 3)
A - C (Weight = 2)
A - D (Weight = 3)
B - C (Weight = 1)
B - D (Weight = 1)
C - D (Weight = 1)

两组

AB CD = 3 + 1 = 4
BC AD = 1 + 3 = 4
AC BD = 2 + 1 = 3

选择

AC BD是因为它最小化了同一组内节点之间的边权重之和。这是一个简单的示例，但如果我要添加更多节点和边，输出将是表示子图的两个节点列表。生成的子图没有任何具体要求，除了它们必须具有相同数量的节点并且每个节点只能出现在两个子图之一中之外。

我进行了研究，但找不到与此类似的内容。即使没有现有的算法，我也在寻找类似的资源来创建一个

Answer 1

IIUC，你想要一个

min_weight_matching

。使用 python，你可以做到：

import networkx as nx

edges = [
    ("A", "B", {"weight": 3}),
    ("A", "C", {"weight": 2}),
    ("A", "D", {"weight": 3}),
    ("B", "C", {"weight": 1}),
    ("B", "D", {"weight": 1}),
    ("C", "D", {"weight": 1}),
]

G = nx.Graph()
G.add_edges_from(edges)

nx.min_weight_matching(G) # {("A", "C"), ("D", "B")}