请问这个关于全排列的图论结论如何证明？ 第1页
1
bao-jia-qi-75-1 网友的相关建议:
以下原答案有误。评论区提到了 SJT算法（Steinhaus–Johnson–Trotter algorithm），可以直接搜索这个算法。大致就是说，将以下原答案中方法调换步骤，原来是 1 每换一次位置，将 2 到 n+1 进行一次 n 的情形的操作，现在是每进行一次 2 到 n+1 的操作，就将 1 通过换位从头到尾遍历一次。
假设 n 成立，考虑 n+1 的情况
将图分为 n+1 个两两不交的子图 G1, G2, … , Gn，分别为 1 在排列中位置为 1, 2, … , n+1，每一个子图都是 n 的情况，故有一个回路，接下来只要接起来即可。那很显然，任取 Gi 中一点 g，它通过交换在 i 这个位置的 1 到 i+1 位置，就可以得到 G(i+1) 中一点，故我们可以把这些回路连接起来得到一个大回路。
1
相关话题
如何用最短的距离走过北京所有线路的地铁？如何把微信群/QQ群构造成一个阿贝尔群？
如何证明子集族上界？
请问数学里组合数的对称性不用公式推导应怎样理解？
从 1~100 这 100 个数，按照怎样的顺序排列是最混乱的？
为什么离 n!/e 最近的整数是 n-1 的倍数？
从一副麻将（136 张）中任取 n 张，总能用其中 14 张组成和牌形，那么 n 至少是多少？
n 座桥，连通 n+1 个岛，有多少种连法？
有没有哪些数学题的某一步处理堪称神来之笔？
零测集的子集是否可测？
前一个讨论
覆叠空间理论中的“纤维”有什么直观解释么？
下一个讨论
怎么形象清晰地解释「周期 3 意味着混沌」?
相关的话题
n*n的棋盘填上1，2，...，n^2，使任意相邻（有公共边）格子里的数字之和不大于S，求S最小值?老哥们，这个题咋做吖，谢谢啦？
这两个极限是怎么处理的？
竞赛组合题的成绩可以通过训练得到显著提高吗？
如何用最短的距离走过北京所有线路的地铁？
这道组合难题怎么解?
如何解决这个图的特征值问题？
N为自然数集，（N×N）×（N×N）是不是可数集？如果是，它到N的双射函数是什么？如果不是，它和什么等势？
数学论文的作者会意识到自己发表的结果实际上已经有人做出来过吗？
单位圆上n等分点按不同顺序顺次连接，能连接出多少种图形？
如何解决下列的数列问题?
算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？
为什么IMO的国家队成员很少有女生？
整數分拆中的分拆函數能否延拓至非整數？
为什么理化生的竞赛统统都是大学知识，而数学竞赛可以仍然在中学甚至小学的一些知识里？
考完第十三届全国大学生数学竞赛后你有什么想说的吗？
竞赛难度，这道数列题应该如何解决？
这道组合难题怎么解?
为什么正方体有十一种展开图？
怎样普适地求此特殊非线性矩阵方程的解？
数学论文的作者会意识到自己发表的结果实际上已经有人做出来过吗？
负数有没有阶乘，0 的阶乘为什么是 1？
如何计算如下极限？本人高三刚毕业，正在预习大学知识，希望得到简易的解法。？
逆拓扑排序是拓扑排序的逆序嘛？
强基计划下的奥赛该不该学？
负数有没有阶乘，0 的阶乘为什么是 1？
请问这个关于全排列的图论结论如何证明？
一个有n条边的简单图最多有几个三角形?
如何看待阿里巴巴全球数学竞赛？对其他学科有哪些实际影响和意义？
高三生只对数学感兴趣，其他科都不喜欢，未来该怎么做？