1回答
需要一些关于如何定义图是对偶欧拉的指导吗？这意味着有两个电路，如果组合在一起，我们会访问图中的所有边。我可以假设图包含一个欧拉电路。
编辑
@ Evgeny Kluev答复
如果该图包含至少一个具有4个或多个边的顶点，则该图具有2个Euler圈。
浏览 2提问于2012-04-03得票数 2
2回答
来自
有向图被称为弱连通图，如果用无向边替换它的所有有向边产生一个连通(无向)图
这个准确吗？
上面的图是连通的，当所有有向边都被无向edges.But替换时，B到D或D到B之间没有路径，这违反了弱类型的property..Am I，对吗？
浏览 2提问于2013-09-06得票数 4
回答已采纳
1回答
这听起来可能很傻，但是否有可能出现这样的情况，即图的边连通分量的数目大于图中的顶点数？
我认为这是不可能的，而且可以用小图快速验证。
这是一个基本的逻辑尝试，为什么这是不可能从直觉，如果我们继续添加边，一个图，希望它将增加比内连接组件的数量，相反，它将减少组件的数量，因为它将连接更多的组件，以前没有连接。这样，就可以从像结构化图这样的树(因为它有最小值)中获得最大的连通分量数。保持连接时的边数)(假设每条边都被计算为两个连接的部件)。在一棵树中，最大的边数可以是n-1，其中n是顶点数，这导致了这样的结果：
“任何图的最大缩元数为n-1”
有人能帮我验证一下这个提议吗？
浏览 2提问于2019-11-06得票数 0
我有一个邻接矩阵格式的图，这个图有断开连接的树。我需要找到每个断开的树的MST。所以，我应该先为每棵树找到子图，然后在树上使用MST，还是有更好的方法/算法？
浏览 4提问于2016-05-03得票数 2
回答已采纳
我试图更好地理解Tarjan的算法，寻找SCC，连接点和桥梁。我正在考虑一个特殊情况，图中只包含两个边为0->1和1->0的节点。下面的代码将输出0,1作为桥。
class Solution(object):
def criticalConnections(self, n, connections):
"""
:type n: int
:type connections: List[List[int]]
:rtype: List[List[int]]
""
浏览 2提问于2022-04-03得票数 0
1回答
给出一个二部图G = (U，V，E)，求出V<code>E 29</code>E29</code>的所有(极大)子集，它们是<code>E 110</code>G<代码>E 211</code>的连通分量的一个“边”.
例如，对于关联矩阵
0 1 0 0 0 1
1 0 0 0 0 1
0 0 0 0 0 0
A = 0 0 0 0 1 0
0 0 1 0 1 0
0 1 0 0 0 0
0 0 0 1 0 0
如果行索引表示U，列索引表示V，则输出应该是集合{0
浏览 1提问于2012-11-06得票数 2
回答已采纳
1回答
任意无向加权图的反馈集是边的子集，在去除子集中的边后，剩下的图是无圈的。
给定G= (V，E)，一个无向加权图和一个整数k，我如何确定是否有一个总权重不超过k的反馈集？
谢谢!
浏览 5提问于2020-03-17得票数 0
回答已采纳
1回答
寻找满足给定约束条件的极小顶点集
、、、、
注：不需要正式的证明或任何东西，只是算法的一般思想，我会深入研究。
给定一个有向图：G(V,E)，我希望找到最小顶点集T，这样对于T中的每个顶点t，都不存在以下边：{(t,v) | for every v outside t} in O(V+E)
换句话说，允许t从T以外的顶点获取边，但不允许发送。
(你可以把它演示为电话，它允许我从外面打电话，它是免费的，但它不允许从我身边打电话给他们)
我认为这个问题非常接近或类似于在有向图中找到所有强连通分量(scc)，它的时间复杂度是O(V+E)，我正在考虑构建一个新的图并运行这个算法，但不完全确定。
浏览 7提问于2021-05-08得票数 0
我想在无向图中找到一个强连通的组件，也就是说，如果我从一个节点A开始，那么我将返回到节点A，并且每条边都被访问一次。
对于有向图，可以使用Tarjan的算法求强连通分量，但如何处理无向图。
浏览 5提问于2017-06-16得票数 3
1回答
问题描述
给定的顶点V，它可以被称为“命题”。
给定的权重：
data W
= Requires -- ^ Denotes that a "proposition" depends on another.
| Invalidates -- ^ Denotes that a "proposition" invalidates another.
在线性序中，如果A要求B，则B必须在A之前，反之，如果A使B无效，则B必须在A之后。
给出了一个加权有向多图(多重图)，它最多有2条平行边.其中一个顶点只能要求包含另一个顶点一次，并且只
浏览 5提问于2017-06-02得票数 3
我正在与大约300个不同大小的断开网络一起工作。我使用R中的STATNET和iGraph包为这些网络计算了不同的图级集中化度量。
然而，我发现N=2的子图中的节点在iGraph的特征向量中心性测度中得到了1的最高值。因此，具有大量孤立的dyads的网络获得了很高的图级特征向量集中度分数。
在我的网络中，这不是一个有效的结果，因为这些网络连接得很差，因此理论上应该有一个很低的集中度分数。
有人知道这些度量是如何处理不连通图的吗？有什么办法处理这件事吗？此外，是否还有其他方法来评估这些网络的结构？
欢迎任何帮助。谢谢!
浏览 8提问于2014-10-29得票数 0
回答已采纳
我自己无法回答这个问题，因为在我尝试的所有示例中，我都没有看到任何类似的行为。再问一次:有n个顶点且有k个连通分支的无向图的最大边数？谢谢。
浏览 2提问于2014-06-03得票数 6
回答已采纳
1回答
从均数中高效地生成排名
、、、、
我有一系列约束，每个约束由两个符号和一个比较运算符组成：<、<=、!=、==、>=或>。因此，例如：
A <= B
C >= B
A != C
C == D
D > E
我想做三件事：
首先，我要检查是否有任何不一致之处。因此，例如，如果我有A > B、B > C和A == C，就会出现不一致性，因为A必须等于C，并且大于C。
我希望能够查询任意两个符号，并得到它们之间可行的相对排序。例如，query(A, C)应该返回{<} (一个由单个元素组成的集合:小于)，query(B, E)应该返回{<, =, >}。
浏览 0提问于2014-03-26得票数 3
回答已采纳
如何处理这个问题:为创建k个连接组件而删除的最小边数？这个图可能已经是一个森林，尽管不一定是有k个连接的组件，而且可能有循环。它是不加权的和没有方向的。
浏览 12提问于2022-04-27得票数 3
我有一个很大的图(顶点的数目可以在5万到10万之间，邻接矩阵不需要稀疏)。图中的边可以删除/添加，并且在这些更改之后，我想更新生成的连接组件结构。我以一种简单的方式实现了这一点，我在C++中使用BFS搜索自己(跟踪连接组件if的unordered_map的顶点并更新它们)，但我想知道是否有更有效的方法使用Boost的图形库来完成这一任务。
我在Stackoverflow中找到了一些类似于此的问题，并且了解了filtered_graph (和connected_components函数)，但我担心每次添加或删除边缘时创建这样的过滤实例所涉及的开销。(这是否值得关注？！)
浏览 0提问于2014-07-25得票数 4
回答已采纳
我试图创建一个algo，它将得到一个具有根节点的生成树，这样，生成树将从原始图G中移除最少的边数。
提前感谢
浏览 3提问于2015-05-14得票数 1
回答已采纳
给定一个图，是否有一个有效的算法来给它的顶点着色，使得任意两个相邻的顶点都是不同的颜色，而任何两个不相邻的顶点都是相同的颜色，并且用最少的颜色来这样做呢？
我意识到，除了图没有边的琐碎情况外，它必须是连通的，否则这样的着色是不可能的:取任何现有的边u-v，很明显，任何其他顶点x必须连接到它的一个端点，否则颜色(X)=u和颜色(X)= v，相矛盾的颜色(U) !=颜色(V)。
对于如何解决这个问题，还有其他的想法吗？
浏览 0提问于2019-09-13得票数 0
回答已采纳
问题：
给出N个节点和M个边的有向图(M，<=，2.N)。查找从所有其他节点可以到达的所有节点。
示例：
下图有4个节点和4个边：
答案：节点(2)和(3)可以从所有其他节点到达。
P/S:
我想出的唯一解决方案是还原图、BFS所有节点并检查它们是否到达所有其他节点。但它需要O(n^2)。
还有其他的方法需要O(n.logn)或更少吗？
下面是我对O(n^2)方法的看法：
void init(){
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v; cin >
浏览 5提问于2021-11-11得票数 2
回答已采纳
我有一个boost adjacency_list，这是我的主要图表。在此图中，我使用create_subgraph函数添加了一些子图。
我的问题是，如何才能在不存储Graph对象的情况下获得刚刚创建的子图列表？
例如：
Graph g; // typedef for a adj. list
Graph sub_graph1 = g.create_subgraph()
Graph sub_graph2 = g.create_subgraph()
//Do some processing here
//Find all subgraphs of g - iterator/array
Graph
浏览 2提问于2013-06-21得票数 0
2回答
我们知道：
如果我们有N个顶点来构造一个连通的无向图，你至少需要N个边。设M是具有N-1边的可能连通无向图的集合.
我们能否证明或证明，如果有一个无向连通图有超过N1边，那么它必须包含M中的一个图？换句话说，我们可以用M中的一个图来添加边来创建这个新的图吗？
(所谓“包含”，我的意思是它有另一个图的所有边，再加上一些。)
浏览 4提问于2016-12-09得票数 1
回答已采纳
2回答
强连通有向图是一个有向图，其中每个顶点都有一个有向路径，其中有一个从to到to的有向路径和一个从to到的直接路径。设= (，)是强连通有向图，设= (，)∈是图中的边。设计了一种有效的算法，它决定了没有边的图是否是强连通的。解释其正确性并分析其运行时间。
所以我所做的就是运行BFS，对标签进行求和，一次在原始图from上，然后在G‘中，再一次在G’中，没有边(同样从)，然后:如果第二次和(在G') <原始和(在G中)，那么这个图就不是强连通的。
这是我考试中的一个问题，我只拿到了3/13分，我想知道我是否应该上诉。
浏览 6提问于2019-02-11得票数 5
回答已采纳
1回答
如果一个简单的图有3个分量，并且这些分量有4，5，6个顶点，那么图中存在的最大边数.
(a) 26
(b) 76
(c) 30
(d) 42
如果我应用‘n个顶点和k个连通分量的图有最大边(n-k)(n-k+1)/2’的公式，为什么我会得到错误的答案？
我们不能用n作为4+5+6=15和组件数= 3吗？
浏览 0提问于2017-03-13得票数 0
1回答
考虑一个任意有向图G (可以包含自循环)和A它各自的邻接矩阵。是否有一种方法(一种算法)来计算图G在一个O(n^4)时间内传递自反闭包的邻接矩阵？有办法在O(log(n)n^3)中计算它吗？传递自反闭包定义如下：
Gt(V，E)是G：(u，v)的传递自反闭包，仅当u=v或者是G中从u到v的一条路时，G：(U，V)是E中的传递自反闭包。
浏览 3提问于2019-12-16得票数 2
1回答
单连通图的特例
、、
我正在尝试编写一个算法来确定一个给定的图是否是单连通的。作业定义说，单连接图意味着在两个节点之间，至多有一条简单路径。 我在这里看到很多答案说，对每个节点使用DFS- are，如果有一个黑色节点被访问，这意味着有两个简单的路径。因此，给定的图不是简单连接的。 我重写了DFS算法来实现这一点，但问题是除了一个特殊情况外，它可以解决所有给定的图。我已经考虑了两个节点之间有多条边的情况，但它不起作用。 所以我的问题是，有没有什么特殊情况是不能通过对每个节点使用DFS- any来解决的？ def dsf(self, source):
source.color = 'g'
浏览 7提问于2019-05-28得票数 0
1回答
一种检测弓形非流形几何的算法
、、、、
有不同类型的非流形几何，其中之一是弓型。在这种情况下，多个曲面在一个点连接，不共享一个边缘。
您可以在下面看到这种特定类型的示例：
我试图想出一个有效的算法来检查一个点是否与多个曲面相连。为了做到这一点，我创建了一个快速python原型，用于处理构建网格邻接信息的位置，这样您基本上可以进行典型的拓扑查询，例如{顶点->faces}、{edges>faces}、{顶点->faces}。
class Triangle:
def __init__(self, a, b, c, label):
self.a = a
self.b =
浏览 2提问于2021-10-23得票数 1
2回答
我知道如何使用DFS变体找到无向图的交点。但它似乎是对无向图和只寻找后缘。但是，如果我的图有前向边或交叉边，我知道我总是可以为每个节点运行dfs，并且计算出它，但是有更好的算法吗？
浏览 3提问于2017-05-14得票数 0
3回答
单连通图是一个有向图，它最多有1条路从u到v∀u，v。
我想出了以下解决办法：
从任何顶点运行DFS。
现在再次运行DFS，但这次从顶点开始，以减少完成时间。只对某些以前的DFS中未访问的顶点运行此DFS。如果我们在同一分量中找到一个交叉边或一个前向边，那么它就不是单连通的。
如果所有顶点都已完成，且没有这样的前向边交叉，则单连通。
O(V+E)
是这样的吗？或者有没有更好的解决方案。
更新:最简单的1条路径。
浏览 3提问于2013-11-12得票数 2
我希望能够将我的图分成子组件，这样删除任何单个节点都不会创建更多的子组件(不包括单个节点)。作为示例，请参见下面的两个图像。
第一个图像显示了完整的图形。第二幅图显示了将图形拆分为尽可能小的子组件时的子组件。从第二幅图中可以看出，顶点名称已被保留。我不需要新的结构是一个单独的图，它可以是一个图的列表，甚至是每个组件中的节点的列表。
节点4-5-6的组件仍然存在，因为移除这三个节点中的任何一个都不会创建新的组件，因为被断开的节点将只是单个节点。
目前，我正在尝试组合一个迭代过程，以升序顺序删除节点，并递归到生成的新组件中。然而，这是困难的，我想以前有人做得更好。
浏览 13提问于2019-03-27得票数 0
回答已采纳
1回答
设G= (V，E)是一个加权连通无向图，E是e中的任意一条边。给出一个线性时间算法，它决定是否存在包含边e的最小生成树。
我设法找到了问题1的一个奇怪的“解决方案”，它似乎是有效的，但我不认为它是线性的：
他们建议对每条边(u，v)使用联合查找和联合(u，v)，使得W(u，v) < W(e)。现在，假设e= (x，y)。现在如果find(x) != find(y)，那么x和y是不相连的，而W( e )肯定是Kruskal算法要检查的下一个权重，所以肯定存在一个包含边e的MST。
另一方面，如果find(x) = find(y)，那么如果我们运行Kruskal算法到这一点，x和y肯定是相连
浏览 1提问于2013-03-02得票数 2
回答已采纳
假设我们有一个有向图，它不是一个完整的图，并且有多个SCC。我想知道，如果我们转换图并使用Kosaraju算法，强连通组件的模式是否会发生变化？说“转图”，我指的是翻转边的方向。如果我们试图在转置/反置图中而不是原来的图中找到SCC，我们发现的SCC会有所不同吗？
我提出了这个问题，因为我误解了SCC的算法，并在我的转置/反转图上运行它。我得到的是相同的SCC正确的答案/运行Kosaraju的算法。它普遍适用于所有的图表吗？
浏览 2提问于2013-11-20得票数 0
回答已采纳
4回答
我试图将一个有向(无圈)图分裂成方向连通的路径，依赖于连通性：
当我测试弱连通子图和强连通子图时，我得到了以下内容：
Weak connectivity :
['16', '17'], ['3', '41', '39', '42']
Strong connectivity :
['17'], ['16'], ['39'], ['41'], ['3'], ['42']
我理解弱连通性的结果，但不理
浏览 0提问于2019-04-16得票数 2
回答已采纳
1回答
寻找一些定义澄清一个简单的问题。考虑图a-B，其中A和B是顶点，它们之间有一条边。它们之间的边会被认为是“切边”，因为它的删除断开了图形的连接吗？还是“边缘”需要增加连接组件的数量，而不仅仅是组件？
浏览 10提问于2016-05-02得票数 1
回答已采纳
2回答
我们能在多项式时间内用3种颜色给图着色吗？我读到用2给图着色
颜色是容易的，但是用3种不同的颜色来着色一个图(没有两个顶点有
相同的颜色)是np-硬的。但是，我想知道是否有一个魔盒表示“是”表示“A”。
图在多项式时间内是3-可着色的？“。如果它说”是“，它将如何在
多项式时间？有什么想法吗？
浏览 2提问于2014-11-10得票数 1
回答已采纳
1回答
对连通图进行计数
、、、、
我正在尝试计算具有确切K条边和N个明显标记的顶点的简单连通图的数量。我已经在下面写了这段代码，但它似乎不起作用。
我们的想法是，这种图不会有孤立的顶点，所以我对N个顶点和K条边这样做。
Connected(N,K):
1) Total = all possible graphs, including disconnected ones.
2) Disconnected = Sum from i=1 to i=N-1 [(Connected(i,K)*(number of ways to
choose i vertices from all N vertices)]
3) return
浏览 2提问于2015-06-29得票数 3
1回答
我目前正在研究一种算法，该算法计算多重图中至少有两条边不相交路径的顶点对的数量。该算法通过找到双连接图工作得很好，但当一个顶点连接两个不同的双连接图时，我遇到了一个问题，就像在沙漏图中一样。此外，两个顶点之间可以有尽可能多的不同边。
浏览 0提问于2018-05-11得票数 0
1回答
顶点度计数子图中的边数
、、、、
我有一个子图，它只被识别为一组已知度的顶点。
我想知道这个子图中有多少条边。有什么方法来计算这个吗？
请注意，不是每个边都在子图中。在子图中有连接顶点的边，在它的外部有连接顶点的边，所以它不能简单地算作顶点的度之和除以2。
如果这有什么帮助的话，我正在使用JGraphT。
浏览 1提问于2015-02-28得票数 0
回答已采纳
首先，我不太清楚如何解释这个问题，因此不知道如何寻找。其内容如下：
我有很多方程。该方程可以求解任意给定变量，给定其他未知数，也可以同时求解多个未知数。例如，给定a和b，方程f(x, y) = a和g(x, y) = b，我们可以同时求解得到x和y。
我需要一种算法，以已知的值和方程，并返回的顺序，解决它们将得到期望的值。
例子方程：
f(a，b) = 0f(b，c) = 0
找c给定一个->用eq1找出b给a，然后用eq2找出c给定b
示例2：
f(x，y，a) = 0f(x，y，b) = 0
求x给定的a，b ->解x和y同时使用eq1和eq2
我尝试用一个图来简化这个问题，其
浏览 5提问于2022-04-21得票数 1
一个完全连通的有向图，其中每个节点最多有一个入站边是一棵树。每个节点最多有一个出站边的全连通有向图是否有一个名称？反树？！
浏览 0提问于2015-11-14得票数 1
回答已采纳
我正在做一个任务，其中一个问题要求导出一个算法来检查有向图G=( V，E)是否是单连通的(对于V的所有不同的顶点u，v，至多有一条从u到v的简单路径)。
当然你可以暴力检查它，这就是我现在正在做的，但我想知道是否有更有效的方法。有谁能给我指个方向吗？
浏览 0提问于2010-03-25得票数 13
回答已采纳
1回答
我对图像处理很陌生。我有一个bmp格式的图像和扫描仪输出的.bin文件。bin文件具有hex值或原始数据。
首先，我将解释这个过程。我们用13位数。每个数字都有一个以点格式表示的模式。比如说，一个13位数就会有20个点。每个点的位置取决于数字。这是encryption部分。现在这些点被反复打印出来。这些文件是使用扫描仪扫描的，扫描仪将上述文件作为输出。
下一步是处理这些输出以返回13位数。我正在使用openCV和C。有人能给我一些关于怎么做的想法吗。我不能发回收站文件。但是bin文件的内容采用这种格式：
10 78 84 88 84 8c 88 88 8c 8c 90 88 8c 8c 90
浏览 5提问于2012-10-26得票数 2
我期待着计算USairports图对于一组顶点: ATL，JFK，ORD，LAS的闭中心度度量。
我的代码如下：
closeness(USairports,vids=c("ATL","JFK","ORD","LAS"),mode="all")
这给了我警告信息
在密语中(USairports，vids = c("ATL"，"JFK"，"ORD"，"LAS")，mode = "all")：At centrality.c:2784 :对于
浏览 0提问于2019-04-27得票数 2
1回答
我试图改进我的解决方案，使用快速查找算法在有向图中找到所有弱连通的组件。
问题陈述
给定一个DirectedGraphNode列表，查找所有岛屿(即弱连接组件)。
public class DirectedGraphNode {
String val;
List<DirectedGraphNode> neighbors;
}
因此，给出了以下有向图：
A —> B —> <— C
^
|
E <— F —> D —> G
X -> <- Y
node : neighbors
A
浏览 0提问于2016-08-17得票数 3
回答已采纳
2回答
我想把有向图中的一个单连通分支定义为一个子图，其中对于每一对节点u和v，存在一条从u到v或从v到u的路径。它还应该具有这样的性质，即它不是另一个单连通分支的子图。
我知道如何找到弱连接组件和强连接组件。如何找到单连接的组件？
一种非常低效的方法可能会从每个节点进行广度搜索，以查看可以从每个节点到达哪些节点，并尝试从这些节点集以某种方式计算组件。
浏览 2提问于2013-07-21得票数 0
回答已采纳
2回答
问题详细信息：
拉什夫是EMLand的市长。EMLand由交叉口和街道组成。从每个交叉口到其他任何一个交叉口都有一条路径。交叉口用正整数1.n表示。一家建筑公司提供拉什夫来重建EMLand的所有街道，但拉什夫可以选择at most k of them to be rebuilt.。建筑公司为每条街道提供了一个新的长度，这意味着在重建街道后，街道的长度发生了变化。现在，拉什夫作为这座城市的市长，必须做出明智的选择，以便将所有交叉路口之间的路径长度之和降到最低。救救拉什夫！
算法：
标注：旧边长度为L，新长度为L'，边集为E。
长度将减少的edges(E')的计数(edges(
浏览 0提问于2014-12-22得票数 1
回答已采纳
2回答
为什么我们需要转换图形来获得它的SCCs (强连接组件)？我知道它给出了正确的答案，但我没有得到logic.Please可以帮助我的人。
浏览 3提问于2014-07-08得票数 0
回答已采纳
1回答
二部图的连通分支
、、、、
我想使用networkx从二部图中提取连通部分(作为二部图)。但networkx中的连通分支不是用于二部图，而是一般的无向图和有向图。有没有二部图的例子？谢谢。
浏览 21提问于2020-04-18得票数 0
回答已采纳
我了解到，Donald B.Johnson在1975年发布的算法是一种寻找有向图中所有圈的有效方法。但现在我有了一个非常大的图，但只需要找到长度有限的环。如何修改它才能做到这一点呢？
浏览 0提问于2020-04-10得票数 0
1回答
在R中切割一个图
、、
我有以下简单的问题。对于多个节点，我有一个距离矩阵，我希望得到这个节点的子集列表，这样在每个子集中，每两个节点都处于最小距离dmin。也就是说，最初，每两个节点都由具有关联值的边缘连接。我希望删除值小于dmin的每一条边，并列出所有由此产生的断续图。
本质上，我希望得到彼此非常接近的数据点簇，而不是使用聚类算法，而是使用距离的阈值。
我的问题是，自然地，我如何在R中完成它，考虑下面的矩阵m：
a b c d
a 1.0 0.9 0.2 0.3
b 0.9 1.0 0.4 0.1
c 0.2 0.4 1.0 0.7
d 0.3 0.1 0.7 1.0
有四个节点(a，b，c，
浏览 0提问于2013-08-07得票数 2
回答已采纳
1回答
我有一个图表和一个起始节点。当我使用DFS为所有节点删除图中的每个节点时，我想知道有多少节点变得孤立了。
例如，如果我从固定节点1开始，并删除节点2，那么我将拥有多少个孤立节点？如果我删除节点3呢？
我知道我可以对所有节点执行DFS (每次删除一个不同的节点)，但是这样做，我将不得不为每个节点导航一次图，我希望只运行一次就可以解决这个问题。
据我所知，它有O({##*$}A~(-1))，是边的|V|=number，和|A|=的节点数。
我一直在玩婚前协议和研究生，但没有成功。
浏览 0提问于2016-09-24得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
