请问这个关于全排列的图论结论如何证明？ 第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
相关话题
求使 y=sqrt(x+a)+sqrt(x+b) 成立的正整数对 (x,y) 的数量这一类的题如何解？为什么中国学生在国际奥林匹克数学竞赛中经常拿金牌，但却没有获得菲尔兹奖呢？
如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？
求使 y=sqrt(x+a)+sqrt(x+b) 成立的正整数对 (x,y) 的数量这一类的题如何解？
n! 和 n²，哪个更大呢？
一道数列题竞赛的感jio，但明明白白出现在考卷上，请问咋做?
为什么同样走了高考外的路，竞赛生被尊敬而艺术生不受待见?
为什么IMO的国家队成员很少有女生？
我好像证明了四色猜想，各位怎么看？
图论里的图用什么软件画比较好？
前一个讨论
覆叠空间理论中的“纤维”有什么直观解释么？
下一个讨论
怎么形象清晰地解释「周期 3 意味着混沌」?
相关的话题
这道排列组合该如何思考？是否存在将中国大陆部分一分为二的铁路路线？
数学上，「数」是怎么定义的？
无限大的围棋盘上某个子的存活概率是多少？
能解释下怎么从这个有向图生成如图的集合链？（数字电路并行全入度拓扑排序优化算法）？
你更喜欢数学竞赛还是物理竞赛?
读美本还是清北？优劣势是什么？
为什么正方体有十一种展开图？
离散数学求帮忙？
如何评价组合数学（combinatorics）这个学科？
质数集P与自然数集N等势吗?
竞赛组合题的成绩可以通过训练得到显著提高吗？
为什么集合的本身还可以是一个集合的元素？
如何证明这个图的染色问题？
为什么IMO的国家队成员很少有女生？
下面这个题该如何做？
为什么江苏数学高考那么难，数学竞赛反而没有浙江湖北湖南的强？
博弈论+图论，博士有哪些方向可以选择？
这道竞赛高数题咋写?
不可列个数的集合交集并集怎么定义？
为什么正方体有十一种展开图？
有n级台阶，每次可以走1～(n-1)的任意阶数，那么一共有多少种走法？
对于任意既约分数，都可以分解成有限个不同奇数的倒数和吗？
如何证明n+1~2n最大奇因子之和等于n²？
关口知宏的《中国铁道大纪行》里面的路线设计本质上是不是就是图论里面的“最长路径问题”？
有哪些指标可以描述两个图（graph）的相似度？
在五大基础学科竞赛中你有哪些笑话和梗？
这张图中能数出多少个三角形？
如何证明以下的这个组合恒等式？
包含所有各项不大于n的n元正整数列且长度最小的序列有多少个？