丢弃R中的有向图的二部边
有向图是一种图结构，其中每条边都有一个方向，表示从一个顶点到另一个顶点的有向关系。二部边是指连接两个不同的顶点，且这两个顶点分别属于两个不相交的顶点集合的边。
在R语言中，可以使用igraph包来处理有向图。要丢弃有向图中的二部边，可以使用igraph包中的delete_edges函数。该函数可以删除指定的边或一组边。
以下是一个示例代码，展示如何丢弃有向图中的二部边：
# 安装和加载igraph包
install.packages("igraph")
library(igraph)
# 创建一个有向图
g <- make_empty_graph(directed = TRUE)
# 添加顶点
g <- add_vertices(g, 5)
# 添加边
g <- add_edges(g, c(1, 2, 2, 3, 3, 4, 4, 5, 5, 1, 1, 3))
# 打印原始有向图
print(g)
# 删除二部边
g <- delete_edges(g, c(1, 3, 3, 4, 4, 5, 5, 1))
# 打印删除二部边后的有向图
print(g)在上述代码中，首先安装并加载igraph包。然后，创建一个有向图并添加顶点和边。接下来，使用delete_edges函数删除指定的二部边。最后，打印删除二部边后的有向图。
相关·内容
1回答
我有如下所示的数据 GPS -> accurate, lost, quality
Battery -> draining, hog, drain
Screen -> flickering, off
Signal -> lost, quality 现在，我想生成一个图，如果两个节点共享一些公共信息，则连接两个节点；如果节点不共享任何内容，则不连接节点。上述数据的图表表示如下： ? 你知道如何在R中实现这一点吗？
浏览 6提问于2019-03-11得票数 0
回答已采纳
1回答
我们将罗马子集定义为以下问题：
输入:有向图G=(V，E)和正整数k
输出:如果有一个V的子集R，这样的子集R\ <= k，并且G中的每一个有向电路至少包含一个从R到R的顶点，那么输出应该是"TRUE"，否则它应该是"FALSE“。
假设顶点覆盖(VC)问题是NP-完全的，我必须证明ROMAN-子集也是NP-完全的.据我所知，这意味着接受VC输入，修改它，然后显示将它插入罗马子集算法将得到VC问题的结果。
我正在经历一段艰难的转变。我知道VC输入是一个图G和一个整数k，问题是是否存在一个覆盖G中每个边的V子集R，例如R\ <= k。很明显，R和k从ROM到
浏览 0提问于2011-12-05得票数 2
回答已采纳
2回答
基于BFS的图最小生成树
、、、
这是我正在努力解决的练习考试中的一个问题：
设G= (V，E)是一个带正权的加权无向连通图(你可以假定权重是不同的)。给定一个实数r，定义子图Gr = (V，{e in E= w(e) <= r})。例如，G0没有边(显然是不连通的)，并且Ginfinity =G(假设它是连通的)。问题是找到最小的r，这样Gr是连通的。
描述一个O(mlogn)-time算法，它通过重复应用BFS或DFS来解决这个问题。
真正的问题是在O(mlogn)中这样做。我要说的是：
r = min( w(e) ) => O(m)
while true
浏览 1提问于2011-12-15得票数 4
回答已采纳
如何找到一个确定有向图的无圈最大子图问题的2-近似解？子图是“最大的”，如果它包含具有相同属性的其他图中的最大边数。
2-近似意味着我们可以构建比最优图形小2倍的图形。这是一个相当大的约束减少，应该导致一个相当愚蠢的算法--哇！--结果只比确切的解决方案差两倍。
这是我最近通过的考试中的一个问题。不再是家庭作业了。
浏览 0提问于2009-12-22得票数 5
回答已采纳
给定一个二部图，我们想要列出所有极大完全二部子图。
例如,
顶点集L= {A，B，C，D}
顶点集R= {a，b，c，d，e}
边: A-a，A-b，B-a，B-b，C-c，C-d，D-c，D-d，D-e
最大完全二部图是：
{A，B}-{a，b}
{C，D}-{c，d}
{D} - {c，d，e}
我找到了一个强力算法，O(2^n)。我不知道是某种近似算法还是随机化算法。
浏览 2提问于2013-03-29得票数 6
回答已采纳
1回答
我只是在创建一个检测二部图的算法，但我想到了一些我不确定是否属于二部图的图，尽管我的算法说它是二部图。
该图如下所示
(A)--(B)
(C)
因此，这里有3个节点，但只有A和B之间有1条边。这真的是二分的吗？
浏览 1提问于2013-03-31得票数 1
1回答
我搜索生成具有特定节点和边计数的随机有向图$G(V，E)$，该图在度分布中和分布中指定，没有循环且完全连通。我在的R中找到了一个函数。
我在networkx中搜索，但只找到了，在这里，图形通过优先附加生长，因此边的数目是不可控制的。
在Python中是否存在与R函数等价的函数？
浏览 0提问于2015-05-21得票数 0
1回答
是否可以基于R igraph中的边属性指定边方向 假设我有一个下面的边缘表。我可以使用graph_from_data_frame()创建有向图或无向图。但正如这里所看到的，一些是有向边，而另一些是无向边。可以创建它吗？ Node1 Node2 Directional
Node2 Node3 Undirected
Node1 Node3 Directional
Node1 Node4 Undirected
Node4 Node2 Directional 一种方法是分离有向边和无向边，分别创建一个图，然后将它们合并。还有其他有效的方法吗？
浏览 12提问于2021-09-15得票数 1
1回答
在其他帖子中，Networkx被建议为“我的朋友”。但是对于TSP问题的某个解决方案，似乎还没有一个现成的函数。即
我有一个无向图，建议的解决方案都与有向图相关，我想知道一个使用可用边访问所有节点的简短之旅。
(还有，带有有向图的tsp，我在networkx的文档中找不到)
有没有人对无向图做过这样的事情，或者我是否应该修改有向图的解决方案，使未连接的节点具有无限的成本？
编辑:我正在学习:实际上，由于图是未加权的(或“所有权重”都相同)，并且不是每个节点都连接到所有其他节点，所以我只需要在包含所有节点的图中找到一个圈。当该循环不存在时，节点可能会重复(因此，它不再是一个循环...)。没有孤立
浏览 0提问于2012-07-16得票数 3
4回答
最小路径-所有边至少一次
、、、、
我有很多圈的有向图，可能是强连通的，我需要从它得到一个最小的圈。我的意思是我需要得到循环，这是图中最短的循环，每条边至少被覆盖一次。
我一直在寻找一些算法或一些理论背景，但我唯一找到的是中国邮递员算法。但这种解决方案不适用于有向图。
有人能帮我吗？谢谢
Edit>>该图的所有边都具有相同的成本-例如1
浏览 2提问于2010-03-02得票数 5
回答已采纳
1回答
如何计算循环图的密度？
、、、、
我在寻找有向循环图的密度。
据称，
对于无向简单图，图密度定义为：
2 *\x{e76f}\x{e76f}
对于有向简单图，图密度定义为：
但我接着阅读了的定义：
一个简单的图，而不是多个图，是一个无向图，其中多个边和循环都是不允许的。
我很困惑，因为另一篇文章提到了“有向”和“无向”简单图。现在简单的图只能是无向的？它还指出简单的图不能有循环，所以我不确定我是否能够在循环图上使用这些公式。
我接着读了关于多图的文章，但是没有提到计算它们的密度。
对于有圈的图，密度不是人们所关心的问题吗？
关于第一条，它指出：
“最大密度为1(对于完全图)”
看起来完全图是多重图的一个专
浏览 11提问于2016-11-30得票数 0
回答已采纳
1回答
二部图的双匹配
、、
我在学习算法测试时遇到了以下问题，但没有给出答案：
最大双匹配问题--给定一个二分图G=(V=(LUR)，E)，描述了一种算法，该算法对v中的每个顶点v返回一组边M.
定义：“强双匹配”是V中每个顶点v的双匹配s.t，M中至少有一条边，其中包含v.给定二部图G=(V=(LUR)，E)和强双匹配M，描述了返回最大大小的强双匹配M‘的算法.证明你的答案。
所以我已经解决了
1)对最大流进行约简:将顶点的s、t和边从s增加到L，边从R增加到t，每个边的容量为2，并用无限容量定义L与R之间各边的容量。利用Dinic算法求出最大流，并返回L与R之间正流的所有边。
( 2)我考虑过以某种方
浏览 0提问于2018-07-05得票数 1
回答已采纳
1回答
? 我想知道这个图是不是二部图。因为我发现B-C-J是一个奇数长度的循环，然而，当我绘制BFS时，没有边加入samen层。谢谢
浏览 20提问于2020-04-24得票数 0
回答已采纳
2回答
我知道一些算法能够找到有向图的最低成本路径(就像Dijkstra和Floyd一样)。有没有适用于无向图的算法？
我的问题是:我需要找到从a到b通过所有顶点的最低成本路径(无向图)。
浏览 4提问于2015-07-16得票数 0
1回答
我有一个连接的正方形区域(img在左边)，并想找出最大数量的“双”方块，可以装进这个区域(img到右边)。
我的方法是将原始区域表示为一个图，其中每个方块表示一个顶点，该顶点由边连接到下面、上面、左边和/或右边的方块。
我认为这可以通过使用BFS算法，检查每个顶点并应用颜色来完成。但我也有一种感觉，它可以用动态编程来完成...我在路上需要帮助！
浏览 3提问于2013-01-04得票数 3
回答已采纳
2回答
匹配和完美数学
、、、
在Skiena的书中，这不是HW，只是我为面试做的准备。
考虑到这个问题，
无向图G= (V，E)的匹配是指没有两个边有公共顶点的边的集合。完美匹配是指所有顶点都匹配的匹配。
(a)构造一个具有2n个顶点和n^2条边的图G，使得G有一个指数数的完美匹配。
(b)构造一个具有2n个顶点和n^2条边的图G，使得G恰好有一个唯一的完美匹配。
我只是不知道如何开始。对于a，我选择n= 3，所以我现在知道我有6个顶点和9条边，并尝试连接它们，但我不知道这是否是完美匹配。
浏览 1提问于2013-04-21得票数 0
回答已采纳
1回答
我需要解决有向图和无向图的最长路径问题(这两种情况都是未加权的)。对于有向图，很容易找到动态规划算法，这些算法能够在伪多项式时间内解决问题，从某个节点开始，计算子问题的最长路径，直到每个问题都被解决。 我可以为无向图做类似的事情吗？我似乎找不到任何关于它的文字？
浏览 20提问于2020-11-07得票数 0
回答已采纳
我有一个有向图(G)，它由65个强连通分量和8个弱连通分量组成。我知道，我可以添加不存在的边，以连接整个图使用k边增强，但这是可能的，只有在一个无向图。
有没有任何方式，在NetworkX中，或以其他方式连接DiGraph，以产生一个强连接的组件？
浏览 9提问于2022-04-09得票数 0
回答已采纳
2回答
最大独立集算法
、、、、
我不相信在二部图中找到最大独立顶点集的算法，除了在所有可能的独立集中寻找最大值的蛮力方法之外。
我想知道找到所有可能的顶点集的伪代码。
假设给定一个有4个蓝色顶点和4个红色顶点的二部图。目前，我将
Start with an arbitrary blue,
find all red that don't match this blue
put all these red in Independent Set
find all blue that dont match these red
put these blue in Independent Set
Repeat
浏览 6提问于2011-12-22得票数 7
回答已采纳
2回答
我们知道：
如果我们有N个顶点来构造一个连通的无向图，你至少需要N个边。设M是具有N-1边的可能连通无向图的集合.
我们能否证明或证明，如果有一个无向连通图有超过N1边，那么它必须包含M中的一个图？换句话说，我们可以用M中的一个图来添加边来创建这个新的图吗？
(所谓“包含”，我的意思是它有另一个图的所有边，再加上一些。)
浏览 4提问于2016-12-09得票数 1
回答已采纳
1回答
二部图是一个图，它的顶点可以被分成两个不相交的集合U和V，使得每条边都将U中的一个顶点连接到V中的一个顶点，即U和V都是独立的集合。等价地，二部图是不包含任何奇数长度圈的图。
我还可以说，如果图G中的所有圈的长度都是偶数，那么它是二部的吗？
我想到了一个偶数长度圈的图，结果发现它是非二部图。
1----------2
| |
| |
| |
| |
3----------4
浏览 0提问于2013-06-15得票数 1
回答已采纳
2回答
是否有已知的检查图是否为的算法？
理想情况下，我希望从中找到一种现成的方法。
或者，我已经找到了关于无向图的完整性检查的。为了检查有向图的完备性，下面的修改是否有效？
检查图中有向边的数目是否为n(n-1)
检查每个顶点是否直接连接到完全不同的n-1顶点。
如果我没有遗漏任何东西，而且这些条件足够，我可以自己实现这些检查，但如果可能的话，我更愿意使用库中的现有实现。
浏览 0提问于2019-07-22得票数 2
回答已采纳
我有一个有向循环图，在边上有值，但在节点上没有值。
该图有一个开始节点和一个结束节点，我希望保留通过该图的路径集，但我不关心路径上的节点，只关心边值。下面是一个例子。
有没有什么算法可以生成一个较小的图来保留这一属性？
图中可能有上千个节点中的10个，但不是数百万个。每个节点的边数很小，w.r.t.节点数。
保守的启发式是受欢迎的。
例如，其中O是节点，数字是相邻边的值：
O --------> O -------> O
2 3
^ |4
|1 v
1
浏览 2提问于2012-01-07得票数 0
回答已采纳
我创建了一个运行pagerank的图表。我测试过有向和无向图，但我很难理解我所看到的。
我有如下代码块：
G= nx.DiGraph() #option 1
#G= nx.Graph() #option 2
[inside a for loop]
G.add_edge(node, another_node)
print("Graph size {} {}".format(len(G.nodes()), len(G.edges())))
[then code to run pagerank...]
正如您所看到的，我尝试了有向图(DiGraph)和无向图(图)。对于这两种
浏览 4提问于2017-04-05得票数 0
回答已采纳
1回答
我在思考给我的一个家庭作业问题，它是这样的:如果给你一个BFS和DFS遍历有向图(或无向图)，你如何找到原始图？这两种情况都有可能吗？
谢谢你
浏览 5提问于2014-02-15得票数 0
回答已采纳
3回答
我想知道一种快速算法来确定一个有向图或无向图是一棵树。
post似乎可以处理它，但它不是很清楚；根据这个链接，如果图是非循环的，那么它就是一棵树。但是如果你考虑下面的有向图和无向图:在我看来，只有图1和图4是树。我想3既不是循环的，也不是树。
要以有效的方式查看有向图或无向图是否为树，需要检查什么？再往前走一步:如果树存在，那么它是不是二叉树？
浏览 0提问于2013-12-13得票数 18
回答已采纳
1回答
无向赋权图的s-t割
、、、、
我最近对图论产生了兴趣。我遇到了有向图的s-t图。我在网上了解到，最小割集等于最大流，并且有一些标准算法可以求解有向图的s-t最小割集。 但我似乎找不到太多关于无向图的s-t割的材料，我看到人们提到我可以用相反方向的两条有向边替换无向边，以将无向图转换为有向图。然而，当我找到新的有向图的最大流量或最小切割时，为什么它与原始的无向图有任何关系？我设想新的有向图的最小割线通常应该只包含uv和vu边中的一条，而不是两条边都包含。 我只是不明白转换后的有向图与原始的无向图有什么关系。
浏览 38提问于2019-03-02得票数 2
2回答
无向图抽象
、、
我有一个无向加权图，我需要正式地描述它。通过自动机或标记转换系统的抽象似乎没有为无向图定义，只覆盖了有向图。图中的状态相互依赖，但是方向本身并不相关。
你知道什么数学模型可以用来形式化地描述这样的图吗？
浏览 0提问于2017-01-29得票数 1
如何找到遍历顶点和边的图中所有边的路径，其中一些边是有向的，而另一些则不是？我想要覆盖图的最小路径数。 我知道Heirholtz的算法，我知道如何将它应用于只有有向边或只有无向边的图。但我不知道如何在同时具有这两种边的图上做到这一点。
浏览 17提问于2019-02-05得票数 0
1回答
我将CLRS第三版ch.22练习22.3-13中的算法简介中的单连通图定义称为A directed graph G = (V,E) is singly connected if G contains at most one simple path from u to v for all vertices u, v belongs to V。我注意到，图中的圈并不一定意味着图不是单连接的，因为涉及圈的路径不被视为简单路径。有向图中的一个简单圈可以由一组对应的边唯一地表示。让我们考虑一个满足以下两个性质的有向图：
(1)它在其DFS森林中只有树和背边，以及(2)表示图中每个简单循环的所有集合都是不
浏览 1提问于2020-09-05得票数 1
1回答
我试图理解如何基于Erdős-Rényi模型正确生成有向随机图。我看过erdos_renyi_graph函数在上。我将实际网络的节点数(5317)设为n个参数，然后对p计算：
p = (< k_in > + < k_out >)/(n-1) = (78,302 )/(5317-1) = 0, 014729496
我将平均度计算为in_degree和out_degree之和。
应用该概率，生成了一个具有5317个节点和415.727个边的随机图。比我的真实网络(207.167边缘)更多的边缘。
我做错什么了吗？
浏览 2提问于2016-04-26得票数 0
回答已采纳
3回答
给定一个由有向边和无向边组成的混合无环图，我想将此图分解为链组件(链组件中的每个节点将仅通过无向边相互连接)及其排序的有向图。
我感到困惑的是，我是应该首先对所有有向边进行拓扑排序，然后寻找作为链组件的无向边，还是应该首先遍历所有无向边并为它们提供组id，然后找到一些有向边来连接这些组件。
由于该图是非循环的，我认为可以将它们从低编号的组件排序到高编号的组件，但无法得出可靠的答案。
浏览 1提问于2013-01-25得票数 2
回答已采纳
1回答
在我的代码中，绘制整个二部图比单独绘制其中一个投影所需的时间要少得多(当然，它的节点比二部图少，因为它只是二部图的一部分)。怎么会这样呢？ 代码如下： rm(list=ls())
library(igraph)
library(tictoc)
nodes <- read.csv("./ma_nodes.csv", header=T, as.is=T)
links <- read.csv("./ma_edges.csv", header=T, as.is=T)
nodes$type <- as.logical(nodes$IsInvestor)
浏览 19提问于2019-03-03得票数 0
回答已采纳
1回答
我注意到，degree函数在iGraph中不允许直接计算有向图的无向骨架图的程度，只要涉及双向边。例如,
g <-graph_from_literal( a-+b,a++c,d-+a,a-+e,a-+f )
d1 <- degree(g,v='a',mode="all")
# 6
nn <- unique(neighbors(g,'a',mode='all'))
d2 <- length(nn)
# 5
正如我想要的d2，而不是d1，我使用了一种不同的路径，基于查找所考虑的顶点的邻居。我的问题是:是否有更
浏览 2提问于2016-06-24得票数 1
回答已采纳
1回答
给出了一个有向加权图，它是强连通的。我需要从这个图中找到一个强连通子图，使得最大和最小权边之间的差是最小。
更清楚地说，我需要去除边，这样在去除它们之后，图仍然是强连通的，而最大边和最小权边之间的差是最小。
这里有一个例子：
第一行是图的N个节点数和M个边。下一条M线表示这个图的边。
3 6
1 2 8
2 3 32
3 1 16
1 3 81
3 2 243
2 1 27
选定的N节点子图将包含以下边：
1 2 8
2 3 32
3 1 16
最大边和最小边的差值是:32-8= 24.在所有选择中都是最少的。
我在寻找一个最优的解决方案。最多有3000个节点和5000条边。
浏览 9提问于2021-07-24得票数 2
回答已采纳
1回答
我不明白这是什么意思
没有出现在广度优先搜索树中的图边也具有特殊的属性。对于无向图，非树边只能指向与父顶点相同级别上的顶点，也可以指向父级以下的顶点。这些属性很容易遵循这样的事实:树中的每条路径都必须是图中的最短路径。对于有向图，只要v比u更接近根，就可以存在反指向边(u，v)。
我理解‘没有出现在宽度优先搜索树中的图边也有特殊的属性。但是，从树中的每条路径必须是图中的最短路径这一事实出发，我如何才能很容易地知道这些属性呢？另外，对于有向图，对于有向图，当v比u更接近根时，如何证明反向边(u，v)可以存在？
浏览 1提问于2021-04-14得票数 0
回答已采纳
1回答
我在做一个在图表上测试的cs项目。我遇到了一个问题，我需要计算一般图中的边数(图可以是有向的，也可以是无向的)。如果图是有向或无向的，谁能就如何编写返回的方法提出一些建议呢？
谢谢。
浏览 7提问于2013-11-24得票数 1
1回答
使无向图有向
、、
我有一个无向图，完全图，并希望将它转换成一个有向无圈图，在每个节点之间有一个(单向)路径。为了开始，我想添加随机边和停止一旦所有节点连接。需要研究的是一个算法(使用Python，但任何语言都可以)。
因此，例如，这个图不再被进一步连接：
A ---- B A ---> B
\ / => /
\ / v
C C
，但在这种情况下，所有无向边都会变成有向边。
A ---- B A ---> B
\
浏览 5提问于2014-10-08得票数 1
1回答
我正在为R做一个有向图，我试图将它转换成一个无向图，其中只有前者的倒数边存在。应该很简单，但我得到了奇怪的结果。
一开始我是这样做的
library(igraph)
load("dmNet.Rdata")
#http://www.unet.univie.ac.at/~a0406222/dmNet.Rdata
recNet <- as.undirected(net, mode = "mutual",edge.attr.comb="sum")
当我检查E(recNet)$weight时，有很多权值为1的边，这应
浏览 0提问于2012-10-22得票数 1
回答已采纳
1回答
来自
最短有向圈。给出了有向图，设计了一种算法来寻找边数最小的有向圈(或报告图是无圈的)。在最坏的情况下，算法的运行时间应该与E V成正比。
在这里可以找到解决方案：
public ShortestDirectedCycle(Digraph G) {
Digraph R = G.reverse();
length = G.V() + 1;
for (int v = 0; v < G.V(); v++) {
BreadthFirstDirectedPaths bfs = new BreadthFirstDirectedPaths(
浏览 1提问于2018-06-24得票数 4
回答已采纳
1回答
作为一个初学文本挖掘的人，我真的很想请教关于图挖掘的建议/指导方针，基于我的一个实际需求:从一个初始输入关键字构建一个与关键字相关的图。
我知道这个话题相对较大，所以我想先为Twitter做一次:我已经收获了一个包含关键字“调查”和“市场”的推文语料库。我想从这个语料库中挖掘出与“调查”或“市场”相关的关键字的图表。
我尝试过使用NodeXL和NLTK，但是我不能做我想做的事情。
浏览 0提问于2012-10-05得票数 0
2回答
来自
有向图被称为弱连通图，如果用无向边替换它的所有有向边产生一个连通(无向)图
这个准确吗？
上面的图是连通的，当所有有向边都被无向edges.But替换时，B到D或D到B之间没有路径，这违反了弱类型的property..Am I，对吗？
浏览 2提问于2013-09-06得票数 4
回答已采纳
1回答
我的意思是有向图可以有一个自循环，所以我不明白为什么一个无向图不能有它(CLRS说如果没有一个有效的理由它是被禁止的)。
Example:
G_directed = (V,E) is a directed graph
Say this graph has the vertex set V = {1,2,3,4,5,6}
With edges E = {(1,2),(2,2),(2,4),(2,5),(4,1),(4,5),(5,4),(6,3)}
-----------------------------------------------------------------
Say
浏览 3提问于2017-10-07得票数 0
2回答
我有一个简单的无向图G，如果某个条件为真，我想要反转一条边。下面的代码显示EdgeElement构造函数无法访问的错误：
if(dfsNum[source->index()]>dfsNum[target->index()]){
EdgeElement ee(target, source, target->firstAdj(), source->firstAdj(), e->index());
e = ee.theEdge();
}
这是我正在做的事情的正确方式吗？
重要的编辑:我的错。我不需要反转边缘，我必须引导它。
浏览 0提问于2013-05-04得票数 2
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储活动推荐
腾讯云开发者
