请问这个关于全排列的图论结论如何证明？ 第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 年丘成桐大学生数学竞赛是什么体验？如何评价今年的竞赛？不可列个数的集合交集并集怎么定义？
下面这个题该如何做？
如何证明子集族上界？
阶乘的概念能否推广到全体实数，甚至是全体复数？
如何评价中青报「多数奥赛金牌得主难成大器」一说？
算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？
如何解决下列的数列问题?
学习函数方程有什么实际的意义？
整數分拆中的分拆函數能否延拓至非整數？
前一个讨论
覆叠空间理论中的“纤维”有什么直观解释么？
下一个讨论
怎么形象清晰地解释「周期 3 意味着混沌」?
相关的话题
质数集P与自然数集N等势吗?从0,2 中选一个数字,从1,3,5中选两个数字,组成无重复数字的三位数,构成奇数的概率是多少？
中国的数物信奥赛一等奖得主总之来自什么样的社会阶层？
下面这道数竞平面几何题求好的解题思路和方法？
为什么正方体有十一种展开图？
这道极限怎么求呢?
如果让过去的顶级数学家参加IMO，会是什么成绩？
这个结论是对的吗？能否初等证明？
为什么IMO的国家队成员很少有女生？
博弈论+图论，博士有哪些方向可以选择？
下列数字方块移动得到一定排列顺序的问题有解吗？
不用计算机程序，如何求1，2，…，n中所有与n互素的数的平方和？
有哪些看起来很简单但做起来很难的数学题？
为什么IMO的国家队成员很少有女生？
【组合数学】这个魔术有什么策略吗？
如何理解（证明）不存在与自己的真子集等势的自然数?
离散数学求帮忙？
为什么离 n!/e 最近的整数是 n-1 的倍数？
如何看待阿里巴巴全球数学竞赛第一轮题目?
离散数学求帮忙？
如何分配砝码使天平尽可能平衡？
在五大基础学科竞赛中你有哪些笑话和梗？
如何看待阿里巴巴全球数学竞赛第一轮题目?
如何评价 2019 年第 35 届中国数学奥林匹克（CMO）试题？
参加 2018 年丘成桐大学生数学竞赛是什么体验？
如何解决这个图的特征值问题？
请问这个关于全排列的图论结论如何证明？
这个数学分析的问题该如何求解？
在离散数学中偏序关系和偏序集是什么意思？
如何评价网传数学家丘成桐批评清华大学在2020年大学生数学竞赛中惨败？