请问这个关于全排列的图论结论如何证明？ 第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年第三届阿里巴巴全球数学竞赛？
这道组合难题怎么解?
下列数字方块移动得到一定排列顺序的问题有解吗？
学高中数学竞赛要不要学一下大学数学（比如数论、图论、高代）？
如何证明这个图的染色问题？
如何看待上海一城管为全球数学竞赛出题？你身边有哪些隐藏的「数学大神」？
为什么规定 0 的阶乘为 1？
前一个讨论
覆叠空间理论中的“纤维”有什么直观解释么？
下一个讨论
怎么形象清晰地解释「周期 3 意味着混沌」?
相关的话题
一道难题求助大佬?中国的数物信奥赛一等奖得主总之来自什么样的社会阶层？
参加今年（2020）的丘成桐大学生数学竞赛是怎样一种体验？
如何证明f(A∩B) ⊆ f(A)∩f(B) 而不是f(A∩B) = f(A)∩f(B) ？
竞赛退役是种怎样的体验？
在离散数学中偏序关系和偏序集是什么意思？
哪个高中竞赛性价比最高？
如何解决这个图的特征值问题？
如何扩充相交族？
如何评价中国队在2020年IMO中获得团体第一名，领先第二名多达30分？
这是一个主客观赋权模型，但我不理解数学意义，有没有帮忙解释一下的？
已知映射f：N→N（其中N是正整数集），问以下三条是否可以相容？
图论里的图用什么软件画比较好？
这道竞赛高数题咋写?
竞赛生真的都很聪明吗？
宁波大学的陈计教授是一个什么样的人？
参加 2021 年丘成桐大学生数学竞赛是什么体验？如何评价今年的竞赛？
请问这个集合不是零测集有什么具体例子吗？
老哥们，这个题咋做吖，谢谢啦？
哪些看似与图论无关的问题可用图论模型解决？
请问这个关于全排列的图论结论如何证明？
下面这道数竞平面几何题求好的解题思路和方法？
如何评价中青报「多数奥赛金牌得主难成大器」一说？
宁波大学的陈计教授是一个什么样的人？
有哪些指标可以描述两个图（graph）的相似度？
一个积分不等式，该怎么处理？
为什么规定 0 的阶乘为 1？
对于 3 和 4 之间的整数 Bleem，你怎么看？
对 n × n 网格图，从左下角走到右上角的边不重复路径（即左下角到右上角的迹）有多少种？
如何评价 2019 年第 35 届中国数学奥林匹克（CMO）试题？