如何通过删除回路来最小化有向图的顶点数量？有没有可以在这里改编的算法？ 已经有一个关于删除图中的圈的问题，但我特别询问通过删除图中的圈来最小化顶点的数量。
浏览 20提问于2021-08-08得票数 0
1回答
我必须解决以下问题:编写一个程序，给出一个有向图和两个顶点，在给定的顶点之间找到最低的代价，或者如果图中有负的代价循环，就打印一条消息。程序采用矩阵乘法算法。我实现了矩阵乘法算法的定义:一个伪矩阵乘法，其中加法被最小化和加法代替。但是通过这样做，我最终得到了弗洛伊德-沃尔算法，我也很难用这种方式来确定负成本周期的存在。我假设我的算法和实际的矩阵相
浏览 4提问于2017-05-01得票数 2
回答已采纳
1回答
给定一个有向赋权循环图，并且m(x，y)给出的顶点之间的最小路径距离，找到最小化m(a，v) + m(b，v) + m(c，v) +…的顶点v。对于n个顶点a，b，c...例如，如果图是无向的，并且我们想要具有到顶点a和b的最小路径的顶点v，那么v就是从a到b的最小路径中心的顶点</e
浏览 11提问于2018-09-04得票数 2
2回答
以下是一个完整的问题：
首先，运行强连接组件算法。现在我们有了强连通的成分。现在转到每个强连接组件，在这个SCC中创建一个简单的循环；也就是说，一个循环
浏览 1提问于2013-02-19得票数 3
2回答
我想把一个连通图划分成两个顶点集，这样每个顶点之间的边权和的差值就被最小化了。例如，如果一个图由顶点1,2,3,4,5组成，那么考虑这个分区：集合B- {4,5}和B={w(4.5)}那么，我如何找到一个分区，以使差异最小化？
浏览 4提问于2014-12-02得票数 2
回答已采纳
1回答
循环图
、、
我有一个关于循环图的问题。我是否正确地认为，这意味着在完成一个循环时，没有超过一次访问边缘/顶点？与之相反的是一个非简单的图？我也想知道，是否有一个只有两个顶点的图可以循环通过？还是不需要
浏览 4提问于2015-11-20得票数 2
回答已采纳
2回答
用0)替换E1:E4列中的所有元素。，其值等于它的顶点数即2，同样，顶点4的E2被0替换为0，因为它等于4。显然，我可以通过迭代来解决这个问题。但是解决这个问题的方法是什么呢？Vertex E1 E2 E33 4 4我是
浏览 4提问于2016-11-30得票数 0
回答已采纳
2回答
它类似于k-最小生成树和steiner树问题，但它有一个图。
我们的目标是选择U中的n个顶点，使U中每个顶点到每个其他顶点的边之和最
浏览 0提问于2017-08-24得票数 3
回答已采纳
运算符理论的一个分支研究移位运算符S。基本上，给定一个图，将权重分配给该图的每个顶点，移位运算符通过采用相同的图(A)并将每个顶点的权重替换为该顶点的相邻顶点的权重之和来生成新的图。例如，图(A)中的3被替换为5+5+2+ 0。
浏览 1提问于2017-06-22得票数 1
1回答
具有特定约束的图的最优嵌入
、、、、
我有一个基于网格的图，其中节点和边占据单元。边可以交叉，但不能在同一方向上彼此重叠。
我的直觉告诉我，这是NP-完全的，并且有必要进行详尽的搜索，随着图的大
浏览 3提问于2014-05-31得票数 6
4回答
给定一组顶点V，一组边E，以及E中每一条边的权重，我如何有效地构造一个图G，以便：
边的权重之和被最小化。E中的边是有向的，当E中的所有边都存在时，可以有圈。
浏览 3提问于2009-08-17得票数 2
回答已采纳
1回答
具有n个顶点的图G的路径矩阵是布尔n*n矩阵，其元素可定义为： p[i][j]=0(otherwise)如果我们自己乘一个邻接矩阵A，则得到A^2(例如AM2)，它的每个顶点Ai基本上表示从i到j的路径长度2的路径数。同样地，如果我们将一个邻接矩阵乘以3次，即得到A^3(例如AM3)，它的每个顶点
浏览 10提问于2013-07-25得票数 5
回答已采纳
图是连通的，无向的，没有自环，也没有平行的边(一个循环是由至少3个节点形成的)。我把图通过点划分成子组件，然后在最初分离的每个子组件中加倍。这来自于以下观察:3给定的<
浏览 1提问于2017-06-18得票数 2
degree_zero_list=g.vs(_degree_eq=0).indices #删除g.delete_vertices(degree_zero_list)返回g
我得到了一个像上面这样的函数G表示由igraph创建的图。但我不知道g.simplify()和g.vs(_degree_eq=0).indices的意思。我在哪里能找到更多关于照片的资料？我在找不到这两个函数。
浏览 0提问于2019-05-19得票数 1
1回答
是仙人掌吗？
、、
在图论中，仙人掌是一个连通图，使得图中任意两个不同的简单圈最多共享一个顶点。下图与上图相似，但不是仙人掌，因为红色标记的两个顶点由两个简单的循环共享。事情可能会变得更加棘手，例如，下面的图表：可能看起来像仙人掌，但事实并非如此。这可以通过突出显示以下周期来显示：这个循环与图中许多更明显的
浏览 0提问于2017-05-14得票数 27
1回答
在(g,s)上运行dijkstra以获得我们需要与之不同的参考图r
对于r中的每个顶点v，运行一个bfs，并对每个到达顶点v(从u到v的路径上最长的边)进行注释。遍历g中的所有边缘g：并找到不存在于r中的e'=(a',b')并最小化newchange := weight(e')
浏览 2提问于2015-12-27得票数 1
给定一个有向加权图G和n，其中n是用于覆盖图G中所有顶点的路径数，如何使最长路径的最大成本最小化？(假设此图中始终存在解决方案)
浏览 0提问于2018-04-10得票数 0
2回答
寻找不含负圈的强连通子图
、、、、
是否有解决以下决策问题的算法：G的强连通生成子图是G的一个强连通子图，它与G具有相同的顶点。您可以在此中查找强连通生成子图的定义。本文给出了最小强连通子图问题的一个近似解。解决这个问题的一种天真的方法是
浏览 5提问于2019-12-31得票数 5
2回答
我正在使用对JS中的图执行拓扑排序。问题是，在极少数情况下，图中会包含圈。这些都是结构的次要部分，因此丢弃一些边缘不会对最终结果产生太大影响。然而，当它们出现时，算法就会中断。更新它的最有效方法是什么，这样如果有一两个周期，它就不会崩溃？
浏览 3提问于2013-08-17得票数 1
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
云直播活动推荐
腾讯云开发者
