请问这个关于全排列的图论结论如何证明？ 第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
相关话题
请问这个集合不是零测集有什么具体例子吗？如何比较 cos 38° 和 tan 38° 的大小？
为什么多项数学杯赛被叫停？
n! 和 n²，哪个更大呢？
图论和拓扑有什么区别？
若两个正整数互质，如何证明它们的平方也互质？
这个结论是对的吗？能否初等证明？
对这个图有什么看法？
如何评价 2021 阿里巴巴数学竞赛决赛试题？
数学上，「数」是怎么定义的？
前一个讨论
覆叠空间理论中的“纤维”有什么直观解释么？
下一个讨论
怎么形象清晰地解释「周期 3 意味着混沌」?
相关的话题
无限大的围棋盘上某个子的存活概率是多少？如何评价IMO（国际奥数） 2019中国队团体总分与美国并列第一，重新夺回团体桂冠？
偏序集与完备格？
学习数论图论有必要先学抽代和高代吗？
如果有人想走遍中国所有的省级行政区（含港澳台），总路程最小可以是多长？
如何看待中国数学竞赛落败引网民狂欢？
这道组合难题怎么解?
在集合的势的意义下，是否存在比实数集更大的全序集？
如何理解「梅涅劳斯定理」和「塞瓦定理」，这两个定理在实际中有什么应用？
为什么同样走了高考外的路，竞赛生被尊敬而艺术生不受待见?
过反比例函数上任意三点连成的三条线段的中点的圆过定点吗？为什么？
这道极限怎么求呢?
不可列个数的集合交集并集怎么定义？
如何看待第二届阿里巴巴全球数学竞赛第一轮预选赛赛题？
能否求出n次对称群中置换的最大阶？
有没有哪些数学题的某一步处理堪称神来之笔？
从 1~100 这 100 个数，按照怎样的顺序排列是最混乱的？
交换环的子环是否一定是交换环？
任取两个大于 2 的整数，其互质的概率是多少？
为什么正方体有十一种展开图？
如何看待阿里巴巴全球数学竞赛第一轮题目?
高中学科竞赛的意义何在?
何猷君的数学水平有多强？
数学竞赛和物理竞赛的强度差距有多大？
请问如何把所有自然数均分成三类？
如何评价数海钓鱼将钓鱼题广泛传播的行为?
有哪些指标可以描述两个图（graph）的相似度？
为什么IMO的国家队成员很少有女生？
这个极限怎么做啊呢捏？
一个无向图的邻接矩阵也是个实对称矩阵，它能否运用实对称矩阵的某些特有性质实现某些运用呢？