0回答
假设我们有一个图，你可以删除边(不超过(原始图的边)/2)，直到它是一个二部图。让我们假设我们得到了：和一组顶点：
V= { 1,2,3,4,5,6,7,8有没有什么算法可以做到这一
浏览 5提问于2017-12-04得票数 1
回答已采纳
1回答
二部图是一个图，它的顶点可以被分成两个不相交的集合U和V，使得每条边都将U中的一个顶点连接到V中的一个顶点，即U和V都是独立的集合。等价地，二部图是不包含任何奇数长度圈的图。我还可以说，如果图G中的所有圈的长度都是偶数，那么它是二部的吗？ |
浏览 0提问于2013-06-15得票数 1
回答已采纳
3回答
有人知道解决以下问题的算法吗？
我认为问题的一部分(我知道一种算法)是计算一条线可以被切成断开的方式的数目。然后计算如何将这些行与其他行分组，得到值(M-K)*K + K*(K-1)/2，M = no。边的K = no。一次切边。我不知道该怎么做的部分是找到切割2条线的其他方法的数量，例如，在只有循环1 - 2 - 3 - 1的图中，任何边<
浏览 2提问于2009-07-17得票数 2
回答已采纳
4回答
完全断开二部图的连接
、、、、
我有一个不连通的二部无向图。我想完全断开图表的连接。我唯一能执行的操作是删除一个节点。移除节点将自动删除其边。任务是最小化要删除的节点数量。图中的每个节点最多有4条边。通过完全断开一个图，我的意思是不应该通过链接连接两个节点。基本上是一个空的边集。
浏览 1提问于2012-08-07得票数 4
回答已采纳
实际上，这与算法分析并没有很强的关系，但是由于我无法从Google获得一个重要的结果，我想得到一些意见。因此，双连接无向图的定义是一个连通图，它不会通过删除任何一个顶点(来自Wikipedia)而被分割成不连通的部分。但是我有一个顶点，删除了它的任何边，破坏了图的双相关性。我试图证明这样的图最多可以有2n-3边(其中n是顶点的数目)。
但是，我无法想象这样一个图，
浏览 2提问于2011-11-16得票数 0
2回答
使用度序列创建图
、、、
我为图编写了数据结构，它可以正确地连接两个顶点(graph.addConnection)。但我无法找到一种方法从一个度序列构建一个图。
将第一个顶点连接到此列表中的下一个d1顶点，然后从列表中删除它。2 2 2 2 2 2 2的输出。{2<
浏览 3提问于2012-10-27得票数 1
回答已采纳
1回答
最大权重二部匹配
、、、
我有一个矩形网格形式的图，即N个节点和2N个边，所有相邻的节点都是连通的。这意味着它是双着色的，因此可以对其进行二部匹配。
每个(无向)边都有一个权重分配给它- 2，-1，0，1，1或2。理想情况下，我正在寻找一种在二次时间内运行的算法--在最坏的情况下可能是O(n^2 log n)。在您提出解决方案之前，我尝试使用权重2的边进行最大匹配，然后使用权重1(不超过重
浏览 4提问于2010-10-16得票数 2
回答已采纳
3回答
从图中消除循环流
、、、
我有一个有向图，沿边有流体量，我想通过删除所有循环流来简化它。这可以通过在任何给定的循环中找到沿每条边的最小流体量，并将循环中每条边的流量减少该最小体积，删除具有零流量的边来完成。当所有循环流都被移除时，该图将是非循环的。例如，如果我有一个具有顶点A、B和C的图，其中来自A→B的流为1，来自B→C的流为2，来自C→A的流为3，那么我可以在没有来自A→B的流、来自B→C的流和来自C→A的流的情况下重写
浏览 4提问于2011-03-21得票数 5
给定一个二部图，我们想要列出所有极大完全二部子图。例如,顶点集R= {a，b，c，d，e}最大完全二部图是：{C，D}-{c，d}我找到了一个强力算法，O(2^n)。我不知道是某种近似算法还是随机化算法。
浏览 2提问于2013-03-29得票数 6
回答已采纳
1回答
给定一个图中多个边的输入，例如(第一行是连接数)：1 25 6在每次输入图是否保持二部后，如果图是非二部图，我们就会中断。我认为这是一些图着色问题，但我无法实现它，请提供一些算法来帮助我这样做。
浏览 1提问于2018-07-19得票数 3
回答已采纳
2回答
对于图G中的任何边e，设G _e表示从G中删除e得到的图。(A)假设给出了一个边加权有向图G，其中从顶点s到顶点t的最短路径σ通过G的每个顶点，描述了计算G中从s到t的最短路径距离的算法，对于G的每一个边e，在O(VlogV)时间内计算最短路径距离。您的算法应该输出一组E最短路径距离，一个对应于输入图的每个边。您可能假设所有的边权都是非负的。[提
浏览 8提问于2019-12-20得票数 0
1回答
反向删除算法:从包含所有边的图开始。然后按权重的递减顺序重复通过边缘。对于每条边，检查删除该边是否会断开该图的连接；如果不会，则删除它。
如何证明此算法计算MST？
浏览 3提问于2020-03-27得票数 0
2回答
我正在寻找一种算法，它接受有限数量的集合S_1，...，S_n作为输入，并输出一个列表x_1，...，x_n，其中x_i属于i=1的S_i，..，n，并且所有的x_i都是成对不同的。我希望算法相当快，特别是在做出选择之前枚举所有列表被认为太慢了。
浏览 0提问于2015-11-18得票数 0
我在上一轮困难的面试中遇到了这个编程问题。List<Customer>, List<Products>int score(Customer, Product)，并返回一个分数。这似乎是一个NP完全的问题，不太可能由我在面试中解决，特别是在面试几天后我仍然不能解决的时候。现在我只是好奇地想知道解决方案。
浏览 0提问于2013-10-11得票数 0
1回答
设G = (V，E)是具有非负边权的连通有向图，S和t是G的顶点，H是通过删除某些边得到的G的子图。假设我们想要重新插入从G回到H的一条边，这样得到的图中从s到t的最短路径是尽可能短的。描述和分析一个算法，以选择最佳的边缘重新插入。
我认为它需要与bellman算法一起用于我们删除的每一个边，然后从所有的边中找到最短的路径。但是它的运行时间太长了。有人有更好的主意
浏览 2提问于2016-01-12得票数 1
回答已采纳
1回答
给出一个二部图G = (U，V，E)，求出V<code>E 29</code>E29</code>的所有(极大)子集，它们是<code>E 110</code>G<代码>E 211</code>的连通分量的一个“边”.0 0 0 1 0 1 0 0 0 0 1 0 0
如果行索引表示U，列索引表示V，则输出应该是集合{0、1、5}、{<em
浏览 1提问于2012-11-06得票数 2
回答已采纳
2回答
最大二部匹配方法中的误差
、、、
给出了一个具有源和汇的二部图，如下所示。每个边的容量为1单位：。c1 =在具有传出边的顶点列表中计数具有非零边数的顶点数。
c2 =在具有传入边的顶点列表中，计数具有非零边数的顶点数。最大流将是这两个数字的最小值，即min(c1，c2).Since
浏览 3提问于2016-01-24得票数 0
回答已采纳
1回答
给定一个图和一个数n，是否有算法通过删除n边来分割图，以最小化最长路径/直径的长度？例如，如果我有以下图表： \ E - F
EDIT1:由树/无环无向<e
浏览 1提问于2015-12-30得票数 2
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
腾讯会议
云直播
对象存储活动推荐
腾讯云开发者
