排列图的度数与连通分量计算：求y+10z的值

嘿，这个问题挺有意思的，我们一步步来拆解，先搞定每个顶点的度数y，再分析连通分量数z，最后就能算出y+10z的值了。

1. 计算顶点度数y #

每个顶点对应1到100的一个唯一排列。两个顶点之间有边的条件是：其中一个排列可以通过交换另一个排列里的一对相邻数字得到。

我们随便拿一个排列举例，比如标准排列1,2,3,...,100——它有多少组相邻的数字对呢？100个元素的有序序列里，相邻位置的数量永远是100-1=99组（比如位置1&2、2&3……一直到99&100）。每交换一组相邻数字，都会得到一个全新的排列，也就是当前顶点的一个邻居。

关键是，不管你选哪个排列，相邻数字对的数量都是99组——因为所有排列都是100个元素的有序序列，相邻位置的数量不会变。所以每个顶点的度数y=99。

2. 计算连通分量数z #

这里要用到排列的奇偶性概念：

• 一个排列如果能表示为偶数次相邻交换的乘积，就是偶排列；
• 如果能表示为奇数次相邻交换的乘积，就是奇排列。

再看图里的边：每条边对应一次相邻交换（这是个奇置换），也就是说，从一个顶点走到它的相邻顶点，排列的奇偶性会直接翻转。

基于这个特性，我们可以得出：

• 所有偶排列构成一个连通分量：任意两个偶排列之间，都能通过偶数次相邻交换互相到达（比如先把第一个排列转换成标准排列，再转换成第二个排列，总交换次数是偶数，路径必然存在）；
• 所有奇排列构成另一个连通分量：同理，任意两个奇排列之间也能通过一系列相邻交换连通（从奇排列到奇排列，总交换次数是偶数，奇偶性翻转偶数次后回到奇排列）。

而偶排列和奇排列之间完全没有路径——因为任何路径的长度是k，k次交换会让奇偶性翻转k次，要从偶到奇需要k是奇数，但不管怎么走，都没法跨越这两类排列的边界。

1到100的所有排列里，偶排列和奇排列的数量正好各占一半，所以整个图的连通分量数z=2。

3. 最终计算结果 #

把y=99和z=2代入公式：
y + 10z = 99 + 10*2 = 119

内容的提问来源于stack exchange，提问作者laura