请问这个关于全排列的图论结论如何证明？ 第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
相关话题
参加 2021 年丘成桐大学生数学竞赛是什么体验？如何评价今年的竞赛？我好像证明了四色猜想，各位怎么看？
1×0＝0 是因为 0 乘以任何数字都等于 0，还是因为 1 乘任何数字都等于那个数？
这道组合难题怎么解?
这是一个主客观赋权模型，但我不理解数学意义，有没有帮忙解释一下的？
请问这个关于全排列的图论结论如何证明？
有没有详细介绍圆锥曲线的极点与极线以及交比的书（不用矩阵）？
“等价”就是重言等值，“推出”就是重言蕴涵吗？
如何评价组合数学（combinatorics）这个学科？
是否存在连续函数，使得每个数都被取到n次？
前一个讨论
覆叠空间理论中的“纤维”有什么直观解释么？
下一个讨论
怎么形象清晰地解释「周期 3 意味着混沌」?
相关的话题
在一个小城市怎么在没有接受过竞赛培训的前提下竞赛数学〔已解决〕？高三休学，去参加高二数学竞赛可以吗？
一个积分不等式，该怎么处理？
如何评价IMO（国际奥数） 2019中国队团体总分与美国并列第一，重新夺回团体桂冠？
交换环的子环是否一定是交换环？
如果让一个高考数学理综满分总分700+的选手经过两年系统训练做奥林匹克竞赛题会比保送生做的差吗？
学习数论图论有必要先学抽代和高代吗？
为什么IMO的国家队成员很少有女生？
如何证明树的树叶个数比度数不少于3的顶点数多？
为什么离 n!/e 最近的整数是 n-1 的倍数？
据说是北大某年大一高代的最后一题？虽然很难，但就是想知道解答过程，还请会的大佬可怜可怜我这弱渣吧 ？
【组合数学】这个魔术有什么策略吗？
单位圆上n等分点按不同顺序顺次连接，能连接出多少种图形？
这道组合难题怎么解?
学习数论图论有必要先学抽代和高代吗？
任给N个连续的整数，是否能从中找到一些数（至少一个），使得它们加起来是N(N+1)/2的倍数？
在一个小城市怎么在没有接受过竞赛培训的前提下竞赛数学〔已解决〕？
如何分配砝码使天平尽可能平衡？
如何证明以下的这个组合恒等式？
这道极限怎么求呢?
请问这个关于全排列的图论结论如何证明？
交换环的子环是否一定是交换环？
如何用最短的距离走过北京所有线路的地铁？
如何在理论上解释「四色定理」？
请问这个一阶逻辑等值式如何理解，请举一个现实的例子?
1×0＝0 是因为 0 乘以任何数字都等于 0，还是因为 1 乘任何数字都等于那个数？
如何评价中青报「多数奥赛金牌得主难成大器」一说？
如何解决这个图的特征值问题？
你更喜欢数学竞赛还是物理竞赛?
竞赛难度，这道数列题应该如何解决？