请问这个关于全排列的图论结论如何证明？ 第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+1~2n最大奇因子之和等于n²？
这是一个主客观赋权模型，但我不理解数学意义，有没有帮忙解释一下的？
数学论文的作者会意识到自己发表的结果实际上已经有人做出来过吗？
这个数学分析的问题该如何求解？
下面这个组合恒等式如何证明？
如果让一个大学数学系的顶尖学霸去解一道高中极其困难的数学题，他还能解出来吗？
模糊层次分析法的三角模糊值含意？
是否存在将中国大陆部分一分为二的铁路路线？
如何证明下面这个图论问题？
前一个讨论
覆叠空间理论中的“纤维”有什么直观解释么？
下一个讨论
怎么形象清晰地解释「周期 3 意味着混沌」?
相关的话题
一根 1m 长的玻璃棒，摔倒地上断成 3 段，最短一段的平均值是多少？【组合数学】这个魔术有什么策略吗？
如何证明f(A∩B) ⊆ f(A)∩f(B) 而不是f(A∩B) = f(A)∩f(B) ？
如何在理论上解释「四色定理」？
如何看待中国数学竞赛落败引网民狂欢？
学高中数学竞赛要不要学一下大学数学（比如数论、图论、高代）？
数学家和物理学家思考方式是什么？
自然数和非负整数有什么区别？
包含所有各项不大于n的n元正整数列且长度最小的序列有多少个？
为什么规定空集是任何集合的子集，这样在数学上有什么意义？
我好像证明了四色猜想，各位怎么看？
零测集的子集是否可测？
如何求解这个偏序集的问题？
为什么规定空集是任何集合的子集，这样在数学上有什么意义？
为什么集合的本身还可以是一个集合的元素？
这道函数问题怎么解决？
竞赛组合题的成绩可以通过训练得到显著提高吗？
数学中有哪些巧合让人眼前一亮？
如何统计拓扑排序的个数？
这道竞赛高数题咋写?
如何评价2020年的全国高中数学联赛？
n! 和 n²，哪个更大呢？
哪些看似与图论无关的问题可用图论模型解决？
如何看待 2020 奥数国家队名单：时隔十年再有女生入选，5 位选手来自南方高中？
取消了自主招生，那每一科高考试卷添加上一道竞赛附加题可行吗，作为对竞赛生的补偿？
包含所有各项不大于n的n元正整数列且长度最小的序列有多少个？
偏序集与完备格？
算法竞赛如何训练数论这一块？
如何证明树的树叶个数比度数不少于3的顶点数多？
如何扩充相交族？