请问这个关于全排列的图论结论如何证明？ 第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
相关话题
阿贝尔变换强大在哪里？“黎曼猜想在公元2030年之前（含2030年）被证明的概率大于等于60%”这个陈述是不是命题？
如何评价2021年第37届全国中学生数学竞赛决赛（CMO）？
如何用数学知识解答「在进行社区大规模核酸检测时，分成几人一组进行混检效率最高」？
有n级台阶，每次可以走1～(n-1)的任意阶数，那么一共有多少种走法？
能解释下怎么从这个有向图生成如图的集合链？（数字电路并行全入度拓扑排序优化算法）？
如何用最短的距离走过北京所有线路的地铁？
这个结论是对的吗？能否初等证明？
为什么规定 0 的阶乘为 1？
如何用数学知识解答「在进行社区大规模核酸检测时，分成几人一组进行混检效率最高」？
前一个讨论
覆叠空间理论中的“纤维”有什么直观解释么？
下一个讨论
怎么形象清晰地解释「周期 3 意味着混沌」?
相关的话题
取消了自主招生，那每一科高考试卷添加上一道竞赛附加题可行吗，作为对竞赛生的补偿？为什么集合的本身还可以是一个集合的元素？
如何证明以下的这个组合恒等式？
请问这个关于全排列的图论结论如何证明？
能否求出n次对称群中置换的最大阶？
我好像证明了四色猜想，各位怎么看？
如何评价组合数学（combinatorics）这个学科？
如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？
学习数论图论有必要先学抽代和高代吗？
请问这个集合不是零测集有什么具体例子吗？
数学竞赛和数学研究有什么区别？
这道函数问题怎么解决？
母函数都是用幂级数吗？三角级数可以构造母函数吗？
非常硬核的数学题，大家能否解出？
学高中数学竞赛要不要学一下大学数学（比如数论、图论、高代）？
这道排列组合该如何思考？
高中想选一门竞赛该怎么选？
包含所有各项不大于n的n元正整数列且长度最小的序列有多少个？
n 座桥，连通 n+1 个岛，有多少种连法？
有n级台阶，每次可以走1～(n-1)的任意阶数，那么一共有多少种走法？
如何在理论上解释「四色定理」？
这道极限怎么求呢?
如何理解「梅涅劳斯定理」和「塞瓦定理」，这两个定理在实际中有什么应用？
数竞零基础还有九个月可以进省队吗？
n! 和 n²，哪个更大呢？
下列数字方块移动得到一定排列顺序的问题有解吗？
算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？
对于数学，你是否真的认为自己有天赋？
已知映射f：N→N（其中N是正整数集），问以下三条是否可以相容？
一道数列题竞赛的感jio，但明明白白出现在考卷上，请问咋做?