请问这个关于全排列的图论结论如何证明？ 第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
相关话题
各位大佬19题怎么做啊?在五大基础学科竞赛中你有哪些笑话和梗？
能解释下怎么从这个有向图生成如图的集合链？（数字电路并行全入度拓扑排序优化算法）？
如何解决这个图的特征值问题？
如何估计Ramsey数的上界？
是否存在将中国大陆部分一分为二的铁路路线？
零测集的子集是否可测？
哪些看似与图论无关的问题可用图论模型解决？
下面这个组合恒等式如何证明？
下面这个组合恒等式如何证明？
前一个讨论
覆叠空间理论中的“纤维”有什么直观解释么？
下一个讨论
怎么形象清晰地解释「周期 3 意味着混沌」?
相关的话题
如何通俗地理解「韦达跳跃」，如何证明？从报名参加竞赛到成功保送的流程是什么？
参加 2018 年丘成桐大学生数学竞赛是什么体验？
请问这个一阶逻辑等值式如何理解，请举一个现实的例子?
我想证明自然数有穷可行吗？
请问这个关于全排列的图论结论如何证明？
“黎曼猜想在公元2030年之前（含2030年）被证明的概率大于等于60%”这个陈述是不是命题？
在三角形abc中，∠B=90°，点D在边BC上，∠BAD=2∠C，AC=12,DC=8求AB？
如何评价微信朋友圈文章：记者调查：疯狂的学而思，疯狂的校外培训！？
能否把数学竞赛变得更有观赏性？
任取两个大于 2 的整数，其互质的概率是多少？
阿贝尔变换强大在哪里？
到底是奇数多还是偶数多？
这道排列组合该如何思考？
该n元不等式如何解？（张端阳的题）?
图论和拓扑有什么区别？
这是一个主客观赋权模型，但我不理解数学意义，有没有帮忙解释一下的？
请问这个集合不是零测集有什么具体例子吗？
考虑一个半径为 1 的圆，若「随机」选择圆上的弦，求弦长的概率分布？
过反比例函数上任意三点连成的三条线段的中点的圆过定点吗？为什么？
我好像证明了四色猜想，各位怎么看？
如何看待 2014 IPHO 金牌得主胥晓宇加入对冲基金 Citadel？
为什么正方体有十一种展开图？
如何在理论上解释「四色定理」？
如何在理论上解释「四色定理」？
为什么IMO的国家队成员很少有女生？
竞赛党们，你们最喜欢的科学家是谁？
有哪些看起来很简单但做起来很难的数学题？
深夜刷数学题是一种怎样的体验？
数学竞赛和物理竞赛的强度差距有多大？