请问这个关于全排列的图论结论如何证明？ 第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
相关话题
逆拓扑排序是拓扑排序的逆序嘛？我想证明自然数有穷可行吗？
想问问数学大神们几个问题，学习数学的兴趣来源是什么？数学在生活中的具体应用？
【组合数学】这个魔术有什么策略吗？
考完了第十二届大学生数学竞赛，你有什么感受？
为什么多项数学杯赛被叫停？
博弈论+图论，博士有哪些方向可以选择？
如何证明树的树叶个数比度数不少于3的顶点数多？
请问这个关于全排列的图论结论如何证明？
为什么IMO的国家队成员很少有女生？
前一个讨论
覆叠空间理论中的“纤维”有什么直观解释么？
下一个讨论
怎么形象清晰地解释「周期 3 意味着混沌」?
相关的话题
中国的数物信奥赛一等奖得主总之来自什么样的社会阶层？算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？
数学论文的作者会意识到自己发表的结果实际上已经有人做出来过吗？
如何分配砝码使天平尽可能平衡？
高中想选一门竞赛该怎么选？
阿里数学竞赛到底难不难？高考142分能不能去试试看？
数学竞赛和数学研究有什么区别？
如何直观地理解群论？
一道难度较大的不等式问题，请问如何入手？
我好像证明了四色猜想，各位怎么看？
在三角形abc中，∠B=90°，点D在边BC上，∠BAD=2∠C，AC=12,DC=8求AB？
参加今年（2020）的丘成桐大学生数学竞赛是怎样一种体验？
这道排列组合该如何思考？
【组合数学】这个魔术有什么策略吗？
为什么规定 0 的阶乘为 1？
如何理解「梅涅劳斯定理」和「塞瓦定理」，这两个定理在实际中有什么应用？
在集合的势的意义下，是否存在比实数集更大的全序集？
如何分配砝码使天平尽可能平衡？
已知映射f：N→N（其中N是正整数集），问以下三条是否可以相容？
如何评价网传数学家丘成桐批评清华大学在2020年大学生数学竞赛中惨败？
能否求出n次对称群中置换的最大阶？
请问这道数竞题怎么做？请大神不吝赐教？
不用计算机程序，如何求1，2，…，n中所有与n互素的数的平方和？
如何看待清华大学举办丘成桐女子中学生数学竞赛？
如何评价组合数学（combinatorics）这个学科？
如何评价 2020 年阿里巴巴数学竞赛决赛试题？
这题怎做呢？
在一个球内任取n个点，则这n个点落在同一个半球内的概率是多少？
请问如何把所有自然数均分成三类？
x^11+x^7+1的因式分解是怎么想出来的？