Consider an arbitrary connected (acyclic/cyclic) undirected graph with N Vertices, with vertex numbered from 1 to N. Each vertex has some value assigned to it. Let the values be denoted by A1, A2, A3, ... AN, where A[i] denotes value of ith vertex. Let P be a permutation of A. Each operation, we can swap values of two adjacent vertices. Is it possible to achieve A = P, i.e. after all swapping operation A[i] = P[i] for all 1 <= i <= N. In other words, each vertex i should have value P[i] after the operations. P.S - I was confused about where to ask this - stack overflow or math.stack exchange. Apologies in advance.
Edit 1: I think the answer should be Yes. But I am only saying this on basis of case analysis of different types of graphs of 5 vertices. I tried to modify the permutation to Q where Q1 < Q2 < .. This changes a problem a bit that now final state should be A1 < A2 < A3... AN. So it can be said can the graph be sorted? Please correct me if my assumption is wrong.
Indeed this is possible. Since we've got a connected graph, we can remove edges until you've got a tree. Removing an edge simply means we won't use it to do adjacent swaps in this case. "Removing a node" simply means we'll never swap the value of the node.
Now we can use the following algorithm to produce the permutation:
In each iteration we reduce the size of the graph by 1 by doing a number of swaps that can be bounded from above by the number of nodes, so with a finite number of swaps we're able to produce the premutation. The algorithm may not yield a solution using the optimum number of swaps, but it shows that it can be done.