具有n个顶点的无向图必须有多少条边才能始终连接？
我知道，对于一个有n个顶点的无向图，它必须有n-1条边。然而，我的问题是，它可以有多少条边来保持连接。例如，一个有n个顶点和n2条边的图必须总是连通的吗？如果没有，它必须有多少条边才能始终连接？
共有2个答案
n个顶点图可以不连接的最大边数是n-2。对于一个有3个顶点的图，你至少需要2条边来使它连接起来，这是n-1，所以比这少一条边会给你图将断开连接的最大边。
一个有n个顶点和n 2条边的图必须总是连接在一起吗：取决于是否允许自循环，例如，考虑一个有3个顶点和5条边的情况，所以它将由2条边和3条自循环连接，但是对于4个顶点和6条边的情况，这也是可能的，也是不可能的。
如果允许重复连接，则没有最大连接数。（例如，有3个顶点a、b、c，边（a、b）多次无限次出现，但没有与c连接的边）。所以为了让这个有趣，我们假设你不能有重复的连接。
对于你的n 2边的情况，考虑一下如果你有一个有10个顶点的图，它的边形成了k5的两个不相交的副本。k5有10条边，所以我们有一个有10个顶点和20条边的图，这是你要求的反例。然而，如果你注意到在我的例子中，如果我们没有断开任何边，你就不能在没有连接图的情况下添加一个。
我们可以考虑的另一个例子（同样是10个顶点）是k9和一个顶点。k9有36条边（比我上一个例子多），单个顶点使图不相交。一般来说，最大的例子是k（n-1）和一个顶点。
km有m（m-1）/2条边，所以不相交图的最大边数是（n-1）（n-2）/2。这意味着保证n顶点图（没有自循环或多个连接）的最小边数是（n-1）（n-2）/2 1。
-
我确实有一个图(~250个节点）。要连接到一个节点，我必须用points->加权图购买它。有些节点总是被占用（“声明的节点”），我可以从这些节点开始连接到其他节点。此外，我的点数有限。所有节点都可以连接在一起。 有什么方法可以得到一个图，其中所有的节点都必须连接在一起，点最少？如果可能的话，以给定的最大点数。 第二）有没有一种方法可以使它不需要一个完全连通的图？例如：一个“必须有节点”的节点直接连
-
一个简单的背景：我正在构建一个语义图，使用带有邻接表的BGL有向图： 我需要做的事情之一，是处理一个较小的图（子图）到我的主图。 暗示我的lambda捕获参数应该是一对（我猜是一个实际的边？）。 所以，我的问题是：我怎样才能发现在顶点的外边中是否存在类似的边呢？
-
所以我正在研究这个问题： 这是我目前所掌握的 首先，我想对我的答案再作核实。我对有向图不是那么熟悉，对算法的效率/复杂度也不是特别熟练。我想我做得对，但如果我需要的话，我想要一些帮助。我也在寻找任何想法，使它更有效率。这些是我脑海中最先出现的算法，所以我觉得可能有更好的方法来实现它。 谢谢
-
给定：有权边的有向无环图，其中一个节点可以有多个父节点。 问题：对于根节点的每个子节点，找到一条从该子节点到某个叶的最小代价（权重之和）路径。一个节点只能存在于一个这样的最小开销路径中。 图表示例： > 这个逻辑有道理吗？我担心这种消除冲突的迭代方式可能对某些图不收敛。例如，在重新计算节点2的最小路径时，如果现在发现2->5是最小路径，并且假设在第一次迭代期间，节点5在其他节点的最小路径中使用，那
-
我怎样才能找到一个有向图中的所有顶点，这样每一个顶点都可以从这个顶点到达呢？现在我只能“发明”O(v^3)ALGO--从每个顶点得到一个DFS/BFS，但我确信，有一个更快的方法来解决这个问题。 谢谢你！
-
我有一个算法来寻找有向图从一个顶点u到任何其他顶点的边，它具有O(V+E)的时间复杂度（基于DFS）。我必须开发一个算法来找到O(VE)中任意两个顶点u和v之间的边。 你有什么建议或暗示来实现这一点吗？ 如果我对每个顶点重复dfs-visite，那么只有第一次顶点是白色的，接下来的调用将不起作用。如果我在做之前重置颜色，那么算法将是O(v^2+VE)。 提前谢谢你！