请问这个关于全排列的图论结论如何证明？ 第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
相关话题
P是任意数域，如何证明P^n*n对于普通加法和乘法构成的环没有非平凡理想？如何估计这个级数？
n 座桥，连通 n+1 个岛，有多少种连法？
离散数学色里的哈斯图怎么画？
这道函数问题怎么解决？
竞赛生和普通学生有哪些区别？
如何在理论上解释「四色定理」？
1^k+2^k+3^k+…+n^k 的公式是什么（n，k 均为自然数）？
深夜刷数学题是一种怎样的体验？
各位大佬19题怎么做啊?
前一个讨论
覆叠空间理论中的“纤维”有什么直观解释么？
下一个讨论
怎么形象清晰地解释「周期 3 意味着混沌」?
相关的话题
如何证明子集族上界？为什么正方体有十一种展开图？
有哪些数学竞赛生才听得懂的笑话?
能解释下怎么从这个有向图生成如图的集合链？（数字电路并行全入度拓扑排序优化算法）？
我好像证明了四色猜想，各位怎么看？
非常硬核的数学题，大家能否解出？
自然数和非负整数有什么区别？
哪些看似与图论无关的问题可用图论模型解决？
如何看待 2020 奥数国家队名单：时隔十年再有女生入选，5 位选手来自南方高中？
竞赛组合题的成绩可以通过训练得到显著提高吗？
数学竞赛和数学研究有什么区别？
为什么理化生的竞赛统统都是大学知识，而数学竞赛可以仍然在中学甚至小学的一些知识里？
如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？
这道函数问题怎么解决？
如何估计这个级数？
如何估计Ramsey数的上界？
如何评价《人物》杂志的《奥数天才坠落之后》一文，以及付云皓本人对此作出的回应？
图论里的图用什么软件画比较好？
高三休学，去参加高二数学竞赛可以吗？
如何计算如下极限？本人高三刚毕业，正在预习大学知识，希望得到简易的解法。？
强基计划下的奥赛该不该学？
如何看待 2014 IPHO 金牌得主胥晓宇加入对冲基金 Citadel？
如何评价 2020 年阿里巴巴数学竞赛决赛试题？
如何看待 2014 IPHO 金牌得主胥晓宇加入对冲基金 Citadel？
如何证明哈代不等式?
阿贝尔变换强大在哪里？
为什么规定空集是任何集合的子集，这样在数学上有什么意义？
环中任何一个非空子集都可以生成理想吗？
已知映射f：N→N（其中N是正整数集），问以下三条是否可以相容？
离散数学色里的哈斯图怎么画？