请问这个关于全排列的图论结论如何证明？ 第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
相关话题
如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？如何用数学知识解答「在进行社区大规模核酸检测时，分成几人一组进行混检效率最高」？
这题怎做呢？
如何评价2021年第三届阿里巴巴全球数学竞赛？
学高中数学竞赛要不要学一下大学数学（比如数论、图论、高代）？
各位大佬19题怎么做啊?
如何在理论上解释「四色定理」？
如何评价2021年第62届IMO试题？
一道难度较大的不等式问题，请问如何入手？
数学竞赛和数学研究有什么区别？
前一个讨论
覆叠空间理论中的“纤维”有什么直观解释么？
下一个讨论
怎么形象清晰地解释「周期 3 意味着混沌」?
相关的话题
考虑一个半径为 1 的圆，若「随机」选择圆上的弦，求弦长的概率分布？如何评价2021年第三届阿里巴巴全球数学竞赛？
这道排列组合该如何思考？
如何解这个数列的通项公式？
如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？
模糊层次分析法的三角模糊值含意？
环中任何一个非空子集都可以生成理想吗？
如何证明f(A∩B) ⊆ f(A)∩f(B) 而不是f(A∩B) = f(A)∩f(B) ？
有哪些指标可以描述两个图（graph）的相似度？
如何估计Ramsey数的上界？
博弈论+图论，博士有哪些方向可以选择？
整數分拆中的分拆函數能否延拓至非整數？
等比数列的任意连续三项的中间一项都是另外两项的等比中项吗？
如何扩充相交族？
能否求出n次对称群中置换的最大阶？
如何看待阿里巴巴全球数学竞赛？对其他学科有哪些实际影响和意义？
如何证明下面这个图论问题？
有哪些指标可以描述两个图（graph）的相似度？
哪些看似与图论无关的问题可用图论模型解决？
为什么多项数学杯赛被叫停？
如何看待阿里巴巴全球数学竞赛？对其他学科有哪些实际影响和意义？
有哪些看起来很简单但做起来很难的数学题？
x^11+x^7+1的因式分解是怎么想出来的？
下面这道数竞平面几何题求好的解题思路和方法？
n! 和 n²，哪个更大呢？
为什么规定 0 的阶乘为 1？
高中学科竞赛必须砸钱才能出成果吗？会不会使阶级更加固化？
如何看待本次数学大赛决赛圈有各行业不同年龄段选手入围，是否高手就在我们身边？
阶乘的概念能否推广到全体实数，甚至是全体复数？
模糊层次分析法的三角模糊值含意？