请问这个关于全排列的图论结论如何证明？ 第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
相关话题
哪些数学定理在直觉上是对的，但证明起来很困难？能否求出n次对称群中置换的最大阶？
在一个小城市怎么在没有接受过竞赛培训的前提下竞赛数学〔已解决〕？
n*n的棋盘填上1，2，...，n^2，使任意相邻（有公共边）格子里的数字之和不大于S，求S最小值?
对 n × n 网格图，从左下角走到右上角的边不重复路径（即左下角到右上角的迹）有多少种？
无限大的围棋盘上某个子的存活概率是多少？
n 座桥，连通 n+1 个岛，有多少种连法？
n 座桥，连通 n+1 个岛，有多少种连法？
如何评价 2021 阿里巴巴数学竞赛决赛试题？
所有集合的势都可比较大小吗？为什么？
前一个讨论
覆叠空间理论中的“纤维”有什么直观解释么？
下一个讨论
怎么形象清晰地解释「周期 3 意味着混沌」?
相关的话题
这个结论是对的吗？能否初等证明？一根 1m 长的玻璃棒，摔倒地上断成 3 段，最短一段的平均值是多少？
请问如何把所有自然数均分成三类？
单位圆上n等分点按不同顺序顺次连接，能连接出多少种图形？
“黎曼猜想在公元2030年之前（含2030年）被证明的概率大于等于60%”这个陈述是不是命题？
如何在理论上解释「四色定理」？
如何把微信群/QQ群构造成一个阿贝尔群？
竞赛生和普通学生有哪些区别？
如何证明下面这个图论问题？
是否存在连续函数，使得每个数都被取到n次？
如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？
考完第十三届全国大学生数学竞赛后你有什么想说的吗？
如何理解「梅涅劳斯定理」和「塞瓦定理」，这两个定理在实际中有什么应用？
如何看待阿里巴巴全球数学竞赛？对其他学科有哪些实际影响和意义？
这是一个主客观赋权模型，但我不理解数学意义，有没有帮忙解释一下的？
如何看待 2014 IPHO 金牌得主胥晓宇加入对冲基金 Citadel？
如何通俗地理解「韦达跳跃」，如何证明？
如何直观地理解群论？
如何扩充相交族？
一根 1m 长的玻璃棒，摔倒地上断成 3 段，最短一段的平均值是多少？
在集合的势的意义下，是否存在比实数集更大的全序集？
如何直观地理解群论？
如何评价《人物》杂志的《奥数天才坠落之后》一文，以及付云皓本人对此作出的回应？
数学竞赛和物理竞赛的强度差距有多大？
如何评价2020年的全国高中数学联赛？
单位圆上n等分点按不同顺序顺次连接，能连接出多少种图形？
如何理解「梅涅劳斯定理」和「塞瓦定理」，这两个定理在实际中有什么应用？
如何评价中青报「多数奥赛金牌得主难成大器」一说？
请问这道数竞题怎么做？请大神不吝赐教？
有哪些指标可以描述两个图（graph）的相似度？