请问这个关于全排列的图论结论如何证明？ 第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等分点按不同顺序顺次连接，能连接出多少种图形？
偏序集与完备格？
如何看待中国数学竞赛落败引网民狂欢？
图论里的图用什么软件画比较好？
请问数学里组合数的对称性不用公式推导应怎样理解？
如何看待 2020 奥数国家队名单：时隔十年再有女生入选，5 位选手来自南方高中？
非常硬核的数学题，大家能否解出？
如何证明树的树叶个数比度数不少于3的顶点数多？
前一个讨论
覆叠空间理论中的“纤维”有什么直观解释么？
下一个讨论
怎么形象清晰地解释「周期 3 意味着混沌」?
相关的话题
“黎曼猜想在公元2030年之前（含2030年）被证明的概率大于等于60%”这个陈述是不是命题？有哪些指标可以描述两个图（graph）的相似度？
各位大佬19题怎么做啊?
如图，这个二元函数的界怎么估算？
【组合数学】这个魔术有什么策略吗？
【组合数学】这个魔术有什么策略吗？
为什么俄罗斯人在通常被认为考验智力的领域大有作为？
如何统计拓扑排序的个数？
偏序集与完备格？
学习数论图论有必要先学抽代和高代吗？
这道竞赛高数题咋写?
怎样普适地求此特殊非线性矩阵方程的解？
阶乘的概念能否推广到全体实数，甚至是全体复数？
如何看待希望杯数学竞赛被取消？
阶乘的概念能否推广到全体实数，甚至是全体复数？
请问这道不定积分的题目怎么做？
竞赛党们，你们最喜欢的科学家是谁？
不可列个数的集合交集并集怎么定义？
考完了第十二届大学生数学竞赛，你有什么感受？
如何在理论上解释「四色定理」？
如何证明（0，1）不是可数集？
有哪些指标可以描述两个图（graph）的相似度？
自然数0 的现实意义是什么？
一个无向图的邻接矩阵也是个实对称矩阵，它能否运用实对称矩阵的某些特有性质实现某些运用呢？
请问这个函数与不等式问题该怎么解答？
逆拓扑排序是拓扑排序的逆序嘛？
如何评价2020年的全国高中数学联赛？
数学上，「数」是怎么定义的？
一根 1m 长的玻璃棒，摔倒地上断成 3 段，最短一段的平均值是多少？
如何评价中国队在2020年IMO中获得团体第一名，领先第二名多达30分？