bipartite

1热度

1回答

我刚刚创建了一个检测二分图的算法，但我想到了一些我不确定算作二分图的图，尽管我的算法是这样说的。该图是这样 (A)--(B) (C) 因此，这有3个节点，但是仅存在A和B之间1个边缘。这实际上是双方吗？

1热度

1回答

我想我正在寻找一种算法，可以在二分图中找到“最小”“选择”。每个顶点都有相关的（整数）成本来选择它。我只能找到最小化所选集合中的顶点数的数的算法，而不是成本。我以前认为我需要一个“匹配”，但实际上我只需要覆盖每条边的顶点的子集... 我不认为贪婪的解决方案可以工作。假设我们的集合是A，B：顶点1,2,3是在A和花费1. 顶点4是在B和已经花费2. 的解决方案是，以除去最昂贵的顶点4.根据成本选择

0热度

2回答

当尝试双色一个有向图时，顶点顺序应该如何处理？

在The Algorithm Design Manual中，作者提供了一种为图着色的算法。它类似于计数元件数量的算法，因为它遍历所有可用的顶点，然后颜色，只有在没有发现它是顶点执行BFS： for(i = 1; i <= (g->nvertices); i++) { if(discovered[i] == FALSE) { color[i] = WHITE; bf

0热度

1回答

边缘双分区，没有三角形：复杂性？

我必须找到一种算法来解决教师的问题。我没有要求解决方案（请不要发布任何内容），只需阅读更多内容。问题的那句话： ** Given a graph G = (V, E) find 2 sets S1 and S2 of edges of G such that: 1. S1 ∪ S2 = E 2. S1 ∩ S2 = ∅ 3. The 2 subgraphs of

3热度

1回答

是否有可能在graphviz中进一步拆分子图

我在graphviz中绘制了一个二部图，我希望它有两列由直线连接的节点（以匹配其他地方使用的样式）。我基本上可以得到我想要的东西（见图），但是柱子太靠近了，这使得边缘不必要地难以遵循。我试图在顶端两个节点之间添加一个非常低权重的连接，希望它能够将两个子图分开，但这不起作用（并且经常会弄乱布局的其余部分）。有没有一种方法可以将右侧的节点列向右移动？在这里是表示我看到和这里的问题的例子我用于生成

3热度

1回答

组合，形成促销

我重新开发一个篮子用户选择零售产品匹配到一个或多个有效促销遗留系统。这些促销活动是行业标准的BOGOF（买一送一），买二送三，购买产品X和Y并获得10％折扣等等，但都要求您可以将潜在物品列表过滤为那些满足这些促销活动。我想解决方案采取整个购物篮零售项目和分析他们在一个操作，而不是现行的方法匹配单个产品，当它是订购。（目前的解决方案导致不受欢迎的限制）每个促销都有一系列必须存在的合格产品才能触

3热度

3回答

双边最小边缘

我正在寻找一种简单的算法，可以在双边图的边缘之间获得最小加权边缘。我搜索，我都可以知道它的意思，换句话说二部的盖边缘，如果我们有二分图和每条边有许多的重量如何让其中

1热度

1回答

为什么以下最大二部匹配实现O（m * n^2）的时间复杂度？

这个库有许多算法的实现，其中一个是最大的二分匹配。这里是链接到源代码：http://shygypsy.com/tools/bpm.cpp 我会在这里将它包括在内（不评论） #include <string.h> #define M 128 #define N 128 bool graph[M][N]; bool seen[N]; int matchL[M], matchR[N];

0热度

1回答

如何在使用BFS的无向双向图中找到最短周期？

如何使用广度优先搜索在简单（未定向）的二分图中找到最短周期？

5热度

1回答

从给定的二分图中查找所有最大完整二部分子图

给定是一个二部图，我们想要列出所有最大完整二部子图。例如，顶点集L = {A，B，C，d} 顶点集R = {A，B，C，d，E} 边缘：了Aa ，AB，BA，BB，CC，镉，DC，DD，德的最大完全二部是： {A，b} - {A，b} {C，d} - {C，d} {d} - {C，d，E} 我已经发现一个蛮力算法，O（2^N）。我不知道是否有一些近似算法或随机算法。