mathematica求解图的所有最大匹配,总是内存不够啊
mathematica吧
全部回复
仅看楼主
level 1
小白一个
求各位大神帮看看这个代码,求给定的一个图的所有最大匹配,总是出现:“No more memory available.Mathematica kernel has shut down.Try quitting other applications and then retry”,可是我的内存已经是32G了,是实验室的最大的了。
各位大神看这段代码可以优化吗,谢谢
g=Graph[{4<->7,4<->8,4<->25,4<->30,4<->23,4<->24,5<->26,5<->11,5<->12,
5<->13,5<->14,5<->27,6<->28,6<->17,6<->18,6<->19,6<->20,6<->29,7<->8,
8<->9,10<->11,11<->12,13<->14,14<->15,16<->17,17<->18,20<->19,20<->21,
22<->23,23<->24,31<->32,32<->33,34<->35,35<->36,37<->38,38<->39}]
esl=Select[Subsets[EdgeList[g],{12}],IndependentEdgeSetQ[g,#]&]
Length[esl]
2018年09月18日 04点09分 1
吧务
level 7
Subsets[EdgeList[g], {12}]的列表长度为Binomial[36, 12]=1251677700,内存肯定不够的
2018年09月18日 07点09分 2
那怎么优化呢,我想的是把这个大的子集分成100份,对每一份做比较,这样可行吗?谢谢
2018年09月18日 08点09分
@wangxiaojie100 FindIndependentEdgeSet[g]
2018年09月18日 08点09分
没明白啊,我是想找到该图中的所有最大匹配,FindIndependentEdgeSet[g]这个函数只是能找到其中的一个呀。不胜感谢!!
2018年09月18日 08点09分
Subsets[EdgeList[g], {12}]中的12就是用FindIndependentEdgeSet[g]这个函数找到的,即从图形的边集的所有子集中找到边数为12的集合,然后再判断此集合是否是边独立集合
2018年09月18日 08点09分
吧务
level 7
Flatten /@
Tuples[Table[
Select[Subsets[EdgeList[h], {Length@FindIndependentEdgeSet[h]}],
IndependentEdgeSetQ[h, #] &], {h, ConnectedGraphComponents[g]}]]
2018年09月19日 00点09分 3
1