1回答
我知道计算加权无向二分图(即赋值问题)的最大加权匹配的各种算法：我希望能找到具有多项复杂性的算法的指针或先前的转换，从而使图无向，这样我就可以应用上述任何算法。编辑：注意到匹配应该使边的权重<
浏览 5提问于2013-02-12得票数 2
回答已采纳
1回答
我读过很多文章，指出用最大流算法可以找到二部图的最大匹配。但是，我们从最大流得到的匹配可能不是最大的，或者匹配没有最大的边。来自Anti Laaksonen的竞争性方案编制手册的例子：
但是，如果我以不同的方式呈现这个图，那么现在的图形是：
然后，随着最大流量算法的推进，匹配结果为1-5，2-7。因为1简单地擦除了通向水槽的路径，但是
浏览 3提问于2021-06-24得票数 1
回答已采纳
3回答
不连通图的最大二部匹配
、、、、
当您的图有多个组成部分时，如何找到最大二部匹配？每个组件都可以用两种方式着色。为了运行最大匹配例程，您如何确定两个集合X和Y？
浏览 1提问于2011-04-19得票数 3
2回答
迭代最大匹配
、、、
在中是一组两两顶点不相交的边，如果它覆盖了图中最大的顶点数，则它是最大的。有一些有效的算法来查找这样的匹配，以及实现(例如，在C++中的一个例子)。但是，在一个任意图中可以有几个最大匹配；是否有任何算法实现允许您列出所有这些算法？我更喜欢C++实现，但其他语言也不错。
浏览 10提问于2011-10-27得票数 4
1回答
我想得到图的最大匹配度。现在，我使用Networkx中的算法：nx.algorithms.bipartite.matching.hopcroft_karp_matching(G) 然而，我在SNAPenter link descriptionhere中没有找到类似的算法。如何使用NetworKit/SNAP来获得图的最大匹配？
浏览 31提问于2021-03-29得票数 0
回答已采纳
1回答
二部图的双匹配
、、
我在学习算法测试时遇到了以下问题，但没有给出答案：
最大双匹配问题--给定一个二分图G=(V=(LUR)，E)，描述了一种算法，该算法对v中的每个顶点v返回一组边M.定义：“强双匹配”是V中每个顶点v的双匹配s.t，M中至少有一条边，其中包含v.给定二部图G=(V=(LUR)，E)和强双匹配M，描述了返回最大大小的强双匹配M‘的算法.证明你的答案。所以我已经解
浏览 0提问于2018-07-05得票数 1
回答已采纳
3回答
二部图的快速最大匹配算法
、、、、
我试图解决下面的，但我的算法太慢。这是因为我使用来寻找最大流，当应用于二分图时，也会给出最大匹配。它的运行时间是n^5，我想知道更快的算法来解决这个问题(特别是二分图)。我目前正在研究的一个算法是，它是n^3。
浏览 7提问于2014-04-14得票数 4
回答已采纳
2回答
列表中元素的对称二部匹配
、、、、
从整数的随机列表开始，例如：目标:最大限度地将列表中的每个条目与列表中的另一个条目配对。当log_base_2((m + n) / gcd(m，n))不是整数时，可以匹配(m，n)的值项。即(7,3)是有效匹配，(1,3)不是。我很确定这样做的一种方法是生成两个列表，A和B，相当于初始列表：然后将其看作是一个具有附加约束的二分匹配问题，即如果Am匹配Bn，则必须匹配Bm (同样，除了上面的<em
浏览 3提问于2017-03-14得票数 1
回答已采纳
1回答
我有一个连接的正方形区域(img在左边)，并想找出最大数量的“双”方块，可以装进这个区域(img到右边)。我的方法是将原始区域表示为一个图，其中每个方块表示一个顶点，该顶点由边连接到下面、上面、左边和/或右边的方块。
我认为这可以通过使用BFS算法，检查每个顶点并应用颜色来完成。
浏览 3提问于2013-01-04得票数 3
回答已采纳
2回答
求最大产量的算法
、、
B2 = S1，S2你可以从每一个插槽中取一个街区来制作一个产品-需要一个函数/算法将这些块放置在每个插槽中，以使产品的数量达到最大。
浏览 9提问于2018-06-05得票数 0
1回答
一个满足以下条件的高效图算法？
、、、、
给定一个有n个顶点的无向图，我们需要选择一些边，即边数=m{ m>=1 m<=floor(n/2)}，使得它们不共享任何公共顶点，并且所有选定边的权重和最大化。我们需要找出所有选定边数(1到n/2)的最大和。
浏览 1提问于2019-11-09得票数 0
1回答
假设有两个这样的图：我们的目标是找到两个graph.And之间的匹配对应，现在我们使用一种方法来计算两个图之间的两个节点的相似度。然后我们可以有这样的表：我们的目标是计算所有这些节点的最大权重匹配。我们可以使用Kuhn-Munkras算法来解决这个问题。但现在的问题是，如果我们添加两个图的边之间的相似度，我们如何计算最大权重匹配。这意味着这个表变成了这样：AA表示节点A，AB表示从A到B的边。约束是
浏览 0提问于2015-11-27得票数 3
1回答
给定一个赋权完全二部图G=(V，U，E)，最大赋权二部匹配问题，即指派问题，目的是在G中寻找一个边权和最大化的匹配。我知道有一些方法(例如匈牙利算法)可以解决这个问题。现在，我想解决一个稍微不同的问题：
给定一个加权完全二部图G=(V，U，E)，我想同时找到G中的最大加权二部匹配和第二大加权二部匹配。任何想法都将不胜感激。
浏览 7提问于2019-08-12得票数 1
1回答
最小化单个经理的最大旅行距离
这是一个已知的问题吗？有没有明显的算法来解决这个问题？这看上去像旅行推销员的问题，但不完全一样。
浏览 0提问于2021-01-23得票数 2
回答已采纳
1回答
求解最大权重二部b-匹配
、、、、
我的问题是关于最大重量B匹配问题。
二部匹配问题对二部图中的两组顶点。最大加权二部匹配 (MWM)被定义为匹配中边值之和有一个最大值的匹配。一种著名的MWM多项式时间算法是匈牙利算法。我感兴趣的是一个特殊的最大加权二部匹配问题，称为权值二部匹配问题。一个加权二分B匹配问题(WBM)寻求匹配顶点，使每个顶点与其容量b允许的顶点不<
浏览 0提问于2018-06-18得票数 5
1回答
图匹配算法
、、、
我一直在寻找用Python编写的图形匹配算法，但是我没有找到多少。我一直在使用graphsim包中的Blondel和Heyman，并且打算在同一个包中
浏览 1提问于2018-05-06得票数 0
1回答
DAG中的最小路径覆盖
、、、
我想知道是否存在一个有效的算法来计算有向无环图的最小路径覆盖。请不要将最小“路径覆盖”与“顶点不相交的路径覆盖”混淆。对于后者，我知道一个有效的算法，使用相应的二部图的最大匹配。当每个顶点可以被多次访问时，是否可以放松相同的算法以获得路径覆盖的答案？
浏览 4提问于2013-06-10得票数 3
回答已采纳
1回答
每天午夜，我都想为每个成员计算一个“匹配”。一般来说，我希望让每个人都尽可能地快乐。为了简单起见，让我们假设如果P1给P2一个5，P2给P1一个7，那么匹配的P1 - P2将具有5+7- (7-5)/2 = 11的权重(我减去差异是因为，对于相同的成绩总和，它们彼此接近会更好，也就是说因此，完成此操作后，我们就得到了一个无向图。从数学上讲，为了我的目的，我认为我需要找到一种算法，在所有具有此图的最大尺寸匹配中，找到具有最大权重和的算法
浏览 4提问于2019-06-17得票数 0
1回答
该信息以二部图G=(X+Y，E)的形式给出。
X:所有成员的集合y :所有图书集的边E=边集(x，y)，其中x是为y书请求的成员。将边从s引入到X中容量为2的所有成员，所有边E有容量1，新边Y到t有容量1，现在应用最大流算法寻找最大匹配。最大匹配是所需的解决方案。另一种方法是采用相同的算法，引入相同的边缘，但每条边的容量为1，现在寻找最大匹配。这种匹配将为最大的成员提供一本书。删除
浏览 0提问于2012-09-06得票数 0
1回答
初值二部图的快速最大匹配算法
、、、、
我正在处理一个二分匹配问题，在这个问题中，我需要求解一个初始图，然后求解多个不同节点被移除的图的变体。我们的目标是尽快解决所有的变体，所以我想使用从求解原始图中获得的信息来更快地解决这些变体。我有用单纯形法求解线性规划问题的经验，这得益于对解的初步猜测，但我对二分匹配算法还不熟悉。
是否有一种二部匹配算法，可以利用初始猜测来加快求解速度？
浏览 0提问于2019-07-26得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
云直播活动推荐
腾讯云开发者
