请问这个关于全排列的图论结论如何证明？ 第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
相关话题
下列数字方块移动得到一定排列顺序的问题有解吗？竞赛党们，你们最喜欢的科学家是谁？
单位圆上n等分点按不同顺序顺次连接，能连接出多少种图形？
如何证明这个图的染色问题？
N为自然数集，（N×N）×（N×N）是不是可数集？如果是，它到N的双射函数是什么？如果不是，它和什么等势？
竞赛退役是种怎样的体验？
有哪些指标可以描述两个图（graph）的相似度？
如何证明f(A∩B) ⊆ f(A)∩f(B) 而不是f(A∩B) = f(A)∩f(B) ？
我好像证明了四色猜想，各位怎么看？
无限大的围棋盘上某个子的存活概率是多少？
前一个讨论
覆叠空间理论中的“纤维”有什么直观解释么？
下一个讨论
怎么形象清晰地解释「周期 3 意味着混沌」?
相关的话题
这道函数问题怎么解决？如何证明以下式子？
老哥们，这个题咋做吖，谢谢啦？
为什么集合的本身还可以是一个集合的元素？
有n级台阶，每次可以走1～(n-1)的任意阶数，那么一共有多少种走法？
这道竞赛高数题咋写?
在集合的势的意义下，是否存在比实数集更大的全序集？
如何评价37届全国中学生物理竞赛决赛？
如何评价《人物》杂志的《奥数天才坠落之后》一文，以及付云皓本人对此作出的回应？
N为自然数集，（N×N）×（N×N）是不是可数集？如果是，它到N的双射函数是什么？如果不是，它和什么等势？
一个有n条边的简单图最多有几个三角形?
图论里的图用什么软件画比较好？
请问这个集合不是零测集有什么具体例子吗？
n 座桥，连通 n+1 个岛，有多少种连法？
n 座桥，连通 n+1 个岛，有多少种连法？
如何通俗地理解「韦达跳跃」，如何证明？
如何用数学知识解答「在进行社区大规模核酸检测时，分成几人一组进行混检效率最高」？
如果让一个高考数学理综满分总分700+的选手经过两年系统训练做奥林匹克竞赛题会比保送生做的差吗？
如何通俗地理解「韦达跳跃」，如何证明？
如果让一个高考数学理综满分总分700+的选手经过两年系统训练做奥林匹克竞赛题会比保送生做的差吗？
数学中有哪些巧合让人眼前一亮？
数学上，「数」是怎么定义的？
请问这个关于全排列的图论结论如何证明？
竞赛党们，你们最喜欢的科学家是谁？
有哪些指标可以描述两个图（graph）的相似度？
“等价”就是重言等值，“推出”就是重言蕴涵吗？
n*n的棋盘填上1，2，...，n^2，使任意相邻（有公共边）格子里的数字之和不大于S，求S最小值?
单位圆上n等分点按不同顺序顺次连接，能连接出多少种图形？
数学建模竞赛要不要和喜欢的女生组队？
竞赛组合题的成绩可以通过训练得到显著提高吗？