是否有可能实现具有相邻交换的顶点的所需值排列？
Is it possible to achieve desired permutation of values for vertices with adjacent swaps?
考虑任意 connected (acyclic/cyclic) undirected graph with N个顶点，顶点编号从1到N。每个顶点都有一些分配给它的值。让值表示为 A1, A2, A3, ... AN，其中 A[i] 表示 的值第 i 个顶点。设 P 是 A 的排列。每次操作，我们可以交换两个 相邻 顶点的值。是否有可能实现 A = P，即在所有 的所有交换操作 A[i] = P[i] 之后1 <= 我 <= N。换句话说，每个顶点 i 在操作后应该具有值 P[i] 。
P.S - 我不知道在哪里问这个 - 堆栈溢出或 math.stack 交换。提前致歉。
编辑1：我认为答案应该是肯定的。但我只是在对不同类型的 5 个顶点图进行案例分析的基础上这样说。我试图将排列修改为 Q，其中 Q1 < Q2 < .. 这稍微改变了一个问题，现在最终状态应该是 A1 < A2 < A3 ... AN。那么可以说图可以排序吗？如果我的假设有误，请指正。
确实有可能。因为我们有一个连通图，所以我们可以删除边，直到你得到一棵树。在这种情况下，删除一条边意味着我们不会用它来做相邻的交换。 “删除节点”只是意味着我们永远不会交换节点的值。
现在我们可以使用以下算法来生成排列：
- 选择一片叶子并确定排列后要放置在那里的值的位置。重复将值与到叶子的路径上的下一个值交换，直到该值到达叶子。
- 从树上取下叶子；结果图仍然是一棵树
- 继续1.，如果还有剩余节点。
在每次迭代中，我们通过进行多次交换来将图的大小减少 1，这些交换可以从上面的节点数限制，因此通过有限数量的交换，我们能够产生预突变.该算法可能无法使用最佳交换次数得出解决方案，但它表明可以做到。
考虑任意 connected (acyclic/cyclic) undirected graph with N个顶点，顶点编号从1到N。每个顶点都有一些分配给它的值。让值表示为 A1, A2, A3, ... AN，其中 A[i] 表示 的值第 i 个顶点。设 P 是 A 的排列。每次操作，我们可以交换两个 相邻 顶点的值。是否有可能实现 A = P，即在所有 的所有交换操作 A[i] = P[i] 之后1 <= 我 <= N。换句话说，每个顶点 i 在操作后应该具有值 P[i] 。 P.S - 我不知道在哪里问这个 - 堆栈溢出或 math.stack 交换。提前致歉。
编辑1：我认为答案应该是肯定的。但我只是在对不同类型的 5 个顶点图进行案例分析的基础上这样说。我试图将排列修改为 Q，其中 Q1 < Q2 < .. 这稍微改变了一个问题，现在最终状态应该是 A1 < A2 < A3 ... AN。那么可以说图可以排序吗？如果我的假设有误，请指正。
确实有可能。因为我们有一个连通图，所以我们可以删除边，直到你得到一棵树。在这种情况下，删除一条边意味着我们不会用它来做相邻的交换。 “删除节点”只是意味着我们永远不会交换节点的值。
现在我们可以使用以下算法来生成排列：
- 选择一片叶子并确定排列后要放置在那里的值的位置。重复将值与到叶子的路径上的下一个值交换，直到该值到达叶子。
- 从树上取下叶子；结果图仍然是一棵树
- 继续1.，如果还有剩余节点。
在每次迭代中，我们通过进行多次交换来将图的大小减少 1，这些交换可以从上面的节点数限制，因此通过有限数量的交换，我们能够产生预突变.该算法可能无法使用最佳交换次数得出解决方案，但它表明可以做到。