问题标签 [undirected-graph]

我正在尝试实现一个 for 循环来初始化网格形状的图形，包括对角线。基本上，我有一个数组，它使用我想在图中复制的值进行初始化。所以我有一个嵌套的 for 循环，它有几个 if 语句。if 语句用于处理特殊情况，即索引 1,1 处的元素只有 3 个邻居。

我知道我的图形函数有效，因为如果我手动初始化它，它不会出现段错误并打印正确的 BFS，但是我的循环段错误。请看一下：

图表类：

在主程序中：

注意：我希望我的图形顶点从 1 开始，而不是从 0 开始。这就是为什么我的矩阵中有一个额外的行和列的原因。此外，我的图表需要在两个方向上添加一条边，因此它将是 1--->0 和 0--->1。

我们知道：

如果我们有 N 个顶点要构建一个连通的无向图，您至少需要 N-1 条边。令 M 为具有 N-1 条边的可能连通无向图的集合。

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

我们能否证明或反证，如果有一个具有 N-1 条以上边的无向连通图，它必须包含 M 中的一个图？换句话说，我们可以取 M 中的一个图并添加边来创建这个新图吗？

（通过“包含”，我的意思是它具有另一个图的所有边缘以及更多边缘。）

我在二维平面（xy）中有一组点，比如 n 个点。

(x1, y1), (x2, y2), (x3, y3), ......................., (xn, yn)

我的目标是绘制图表。图中的两个节点（点）将连接 iff abs(difference in x coordinate) + abs(difference in y coordinate) = L(given)。

可以做到O(n*n)的。是否有可能有效地做到这一点。

顺便说一句，我正在尝试解决这个问题

我有五个元素A, B,C和。DE

每个元素之间的距离由下面的矩阵给出：

我想选择元素的所有组合，使得距离之和小于10.

它可以通过以下方式递归完成：

• 首先找到符合条件的 2 项组合的集合。
• 然后，通过在先前找到的符合条件的 2 项组合中添加另一个项来查找符合 3 项的组合的集合。
• 等等。

对于上面的示例，手动执行此操作，我得到以下组合：

如果元素的数量很大（比如 250），我将如何在 Octave 中系统地执行此操作？

我有一个无向加权图 G=(V,E)，其中 V 代表节点，E 代表边。通过 Dijkstra 算法，我得到了一个最短路径树 Ts=(s,V)，它以源节点 s 为根，跨越图 G 中的所有节点 V。然后我选择了一个子树 Tm=(s,K)，（其中 K是最短路径树Ts=(s,V)的V)的子集，将s连接到所有V个节点中的K个节点，即子树Tm是最短路径树Ts的子集。

我的问题是现在我如何通过论证或引理/定理证明最短路径树 Ts 的这个子树 Tm 也是最短树？先感谢您。

我有一组房间，每个房间都通过基本方向（北、南、东、西）连接到一个或多个其他房间。房间的连接方式是，如果 A 在 B 的西边，那么 B 在 A 的东边；因此无向图。现在我需要收集这些房间并在坐标平面上绘制它们。所有边必须平行于 X 或 Y 轴。

我尝试了一些不同的方法，但我认为迄今为止最有效的方法如下：

1. 找到“中心”并将其分配（0,0）（到其他房间的最短路径的长度总和最小的房间）。我不知道这是否真的有必要，但它使输出居中变得更容易。
2. 从中心 C 走出来，对于遇到的每个房间 R，分配一个坐标 (X, Y)，其中 P 是连接 C=>R 的路径，导致坐标平面上的最大位移，X 是沿 P 的净水平移动, Y 是沿 P 的净垂直运动。

假设方向向量如下： 北 = [0,1] 南 = [0,-1] 东 = [1,0] 西 = [-1,0]

我需要你的帮助来证明以下几点： G=(V,E)是一个边上权重为非负的无向连通图。让我们T成为一个 MSTG并且T'是一个（不是最小的）的生成树，G所以它持有Weight(T') > Weight(T). 证明 inT'中最重边的权重不小于 中最重边的权重T。

我不知道如何处理这个问题，如果我们让e(u,v) - heaviest edge on T，e'(u',v') - heaviest edge on T'然后如果我们查看定义的切割，(u,u')我们可以使用 Kruskal 算法并显示e'没有选择T在这个方向或其他东西......

谢谢，

问题

我有一个关于这个问题的问题：

给定一个包含 N 个顶点和 M 个边的有向图，请确定“所有的顶点 i 到顶点 j 都有一条路径1 <= i, j <= N”。

我想解决N <= 500, M <= 250000.
我用 dfs 找到了简单的寻路算法，但时间复杂度是O(N^2 M)，所以速度很慢。
请告诉我解决它的有效算法。

例子

例如，如果给出此图：

答案是否定的，因为没有从 4 到 1 的路径。

我有一个无向加权图，我需要正式描述它。似乎没有为无向图定义通过自动机或标记转换系统进行的抽象，仅涵盖有向图。图中的状态相互依赖，但方向本身并不相关。

你知道什么数学模型可以用来正式描述这样的图吗？

给定一个无向图 G=V,E, 2 个顶点：x, y 和边 e，

我想检查是否有一条从 x 到 y 的路径包含给定的边 e。

我的想法：通过定义一个网络流来解决这个问题，其中 x 和 y 是源和汇，并检查 e 中的流是否大于 0，这意味着存在路径。但是有两个问题：

1. 我不知道如何指向边缘
2. 每个边缘的容量是多少？

所以我猜这不是正确的方法......如果有人能给出一个想法，那就太好了。