请问这个关于全排列的图论结论如何证明？ 第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
相关话题
如何评价2020年的全国高中数学联赛？阿贝尔变换强大在哪里？
这是一个主客观赋权模型，但我不理解数学意义，有没有帮忙解释一下的？
请问这个关于全排列的图论结论如何证明？
全国高中数学联赛等学科竞赛是否会有黑幕？
如何估计Ramsey数的上界？
如何证明这个与树有关的递推式？
给定正整数 n，将 1 拆分为 n 个互不相同的单位分数之和，不计次序，有几种拆法？
环中任何一个非空子集都可以生成理想吗？
你更喜欢数学竞赛还是物理竞赛?
前一个讨论
覆叠空间理论中的“纤维”有什么直观解释么？
下一个讨论
怎么形象清晰地解释「周期 3 意味着混沌」?
相关的话题
在圆上选取n个点，两两连线，最多可以在圆内形成多少个交点？竞赛党们，你们最喜欢的科学家是谁？
能否把数学竞赛变得更有观赏性？
如何扩充相交族？
如何证明这个与树有关的递推式？
想问问数学大神们几个问题，学习数学的兴趣来源是什么？数学在生活中的具体应用？
能否把数学竞赛变得更有观赏性？
为什么集合的本身还可以是一个集合的元素？
如何证明哈代不等式?
你更喜欢数学竞赛还是物理竞赛?
1^k+2^k+3^k+…+n^k 的公式是什么（n，k 均为自然数）？
如图，这个二元函数的界怎么估算？
如何看待阿里巴巴全球数学竞赛第一轮题目?
宁波大学的陈计教授是一个什么样的人？
高中想选一门竞赛该怎么选？
如果让过去的顶级数学家参加IMO，会是什么成绩？
有哪些指标可以描述两个图（graph）的相似度？
请问如何把所有自然数均分成三类？
有限个人，任意两个人有且只有1个公共朋友，那么一定存在1个人是所有人的朋友，这是什么数学问题?
若两个正整数互质，如何证明它们的平方也互质？
如何估计这个级数？
请问这个集合不是零测集有什么具体例子吗？
竞赛生和普通学生有哪些区别？
这个结论是对的吗？能否初等证明？
自然数0 的现实意义是什么？
如何证明这个与树有关的递推式？
有没有详细介绍圆锥曲线的极点与极线以及交比的书（不用矩阵）？
请问这个关于全排列的图论结论如何证明？
为什么集合的本身还可以是一个集合的元素？
有哪些指标可以描述两个图（graph）的相似度？