对于具有相邻交换的顶点，是否有可能实现期望的值排列？

Question

考虑任意连接的(无圈/循环)无向图具有N顶点，顶点从1到E 110N<代码>E 211。每个顶点都有分配给它的值。让这些值由A1，A2，A3，.，其中Ai表示ith顶点的值。设P是A的置换。每次操作，我们都可以交换两个相邻顶点的值。是否有可能实现A = P，即在所有的1 <= i <= N中交换操作Ai = Pi。换句话说，每个顶点i在操作后都应该有值Pi。P.S-I不知道该在哪里询问堆栈溢出或math.stack交换。提前道歉。

编辑1:我认为答案应该是肯定的。但我只是在对5个顶点的不同类型的图进行案例分析的基础上这样说的。我试图将置换修改为q，其中Q1 < Q2 < ..这稍微改变了一个问题，即现在的最终状态应该是A1 < A2

Answer 1

事实上，这是有可能的。既然我们有一个连通的图，我们可以删除边，直到你有一棵树。删除边只意味着在这种情况下我们不会使用它来执行相邻的交换。“移除节点”仅仅意味着我们永远不会交换节点的值。

现在，我们可以使用以下算法来生成置换：

1. 选择一片叶子并确定置换后要位于那里的值的位置。在到达叶子的路径上与下一个值重复交换值，直到该值到达叶子为止。
2. 从树中移除叶；生成的图仍然是树
3. 继续1。如果还有任何节点。

在每一次迭代中，我们将图的大小缩小1，方法是执行一些交换，这些交换可以从上面被节点的数目限制，因此，有了有限的掉期，我们就能够产生预变异。该算法可能不会使用最优的交换数来求解，但它表明可以这样做。