rt，不是图论专家，所以只能白话描述一下：
有一个graph G = (V, E) 和 weight function f: E → [0, 1] 需要找到它的一个子图 G’ = (V’, E’): for E’{i}, E’{j} \in E’, E’{I} \cup E’{j} = \empty, s.t \sum_{I} f(E’_{I}) is maximized
有没有什么优雅的解决方法？
这么标准的问题，先问下chatGPT怎么说？
greedy is fast but wrong
有一个Blossom algo, probably works? 没有时间细看，要上飞机了
上班就够头疼了，为啥挂壁论坛会看到这个…
1 个赞
这不就是无向图最大权匹配吗，基础是Edmond’s的带花树，不过要按照Vazirani的paper大改，去看一下Duan, Pettie的有一篇paper，里面有张表总结了这个方向的各种算法。
多说一句，个人最喜欢的是Gabow, Tarjan的scaling algorithm，因为我很喜欢scaling这个idea。
14 个赞
曾经很认真的钻研过学术，但是实在是太笨了 学不会，做不来。
羡慕各位学术大神们
根据您的描述，给定一个图 ( G = (V, E) ) 和一个权重函数 ( f: E \rightarrow [0, 1] )。您需要找到一个子图 ( G’ = (V’, E’) )，满足以下条件：
- 边不相交：对于任意两条边 ( E’_i, E’_j \in E’ )，它们不共享任何顶点，即 ( E’_i \cap E’_j = \emptyset )。
- 权重和最大化：使得所选边的权重总和 ( \sum_{i} f(E’_i) ) 最大。
这实际上就是图的最大权匹配问题（Maximum Weight Matching Problem）。
什么是匹配？
在图论中，匹配是指图中的一组边，这些边两两不共享顶点。换句话说，没有任何两条边是相邻的。
解决方案
为了解决您的问题，需要在给定的图中找到一个最大权匹配。这可以通过以下算法实现：
-
Edmonds的花算法（Blossom Algorithm）：
- 适用范围：一般的非二分图。
- 时间复杂度：经典版本的时间复杂度为 ( O(n^3) )，其中 ( n ) 是顶点数量。改进的版本可以达到 ( O(nm \log n) ) 的复杂度。
- 原理：该算法能够处理图中的奇环，利用"花"的结构来递归地寻找增广路径，从而找到最大匹配。
-
匈牙利算法（Hungarian Algorithm）：
- 适用范围：二分图。
- 时间复杂度：( O(n^3) )。
- 原理：该算法通过构建一个代价矩阵，并在此基础上寻找零代价的完美匹配，从而达到最大权匹配。
实际步骤
-
确定图的类型：首先，判断您的图是否为二分图。如果是，匈牙利算法可能更高效。
-
实现算法：
-
编程语言和库：许多编程语言和图论库都实现了这些算法。例如，Python的NetworkX库提供了
max_weight_matching函数，可以直接用于求解。import networkx as nx G = nx.Graph() # 添加边和权重 G.add_edge(u, v, weight=f(u, v)) matching = nx.algorithms.matching.max_weight_matching(G, maxcardinality=False)
-
-
验证结果：确保得到的匹配满足不相交的条件，并且权重和最大。
注意事项
-
唯一性：最大权匹配不一定是唯一的，可能存在多个匹配具有相同的最大权重和。
-
复杂度：对于大型图，计算量可能较大，需要考虑算法的时间复杂度和空间复杂度。
参考资料
- Edmonds, J. (1965). Paths, trees, and flowers. Canadian Journal of Mathematics.
- NetworkX 文档：https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.matching.max_weight_matching.html
希望这些信息能帮助您解决问题。如有其他疑问，请随时提问！
It’s not all about academics tho. I’m using this to make money 
2 个赞
安慰～
不要灰心，只是天赋点没点在学术上罢了。
1 个赞
好家伙 所以是在做婚恋app的匹配？！
啊 it’s a good idea, I didn’t think about that but thanks
能不能写成线性优化，拿算力优秀的solver强解…
Size大吗？
（另外不知道泥潭还有这用途
1 个赞
不能，都是fractional解。当然可以加更多constraint但需要exponential number of constraints。
@YoumuChan 的答案就是正解。
哦对, 那找整数优化solver?
我以为Quant只写model，不涉及算法
再向大家请教一个问题：如果要对顶点施加额外限制，请问怎么做呢？
比方说，考虑一个完全图，我们需要找到它的max matching G’ = (V’, E’), subject to min \sum f(E(v_{i}, v_{j})), \forall v_{i}, v_{j} \in V', \{v_{I}, v_{j}\} \notin E'
也就是说，我们希望这些被选出来的边的权重和最大，同时顶点和不在这条边上的其他顶点之间在原图上的边权重和最小