引
关于正方体展开图相信大家在小学的时候就有接触过相关问题,「正方体的平面展开图有11种」这个结论往往老师一带而过,似乎这只是一个动手验证的结果,并不值得深思。但如果真要深究下去,为什么偏偏是这11种?真的没有第12种展开图了吗?除了用计算机穷举的方法之外,有没有严格的数学证明呢?铺垫
我们在曾经的文章《围棋中的数学原理(一)》中接触过关于图论的基础概念,接下来我们再引入一些更方便的代数工具,用来刻画图(本文所说的图皆为简单无向图,即连接顶点之间的边至多有一个,并且边本身没有方向)。任意一个图有如下代数表示,我们称之为邻接矩阵:先给图的顶点标号,一个矩阵的第行第列元素表示第个顶点与第个顶点是否存在一条边相连,若存在,则,否则 标号方式不同,邻接矩阵固然不同,但它们彼此都是等价的(只需要交换若干次第行和第行,以及第列和第列,两个彼此等价的邻接矩阵会相互转换,想想为什么)。例如一条长度为2的道路,我们不妨从左到右依次给各个顶点标号为1、2、3,于是它的邻接矩阵是我们称之为图的Laplace矩阵。上例中各点的度数为:证明概要
每一个正方体展开图都是沿着正方体的条棱切割得到的。所以问题的关键在于讨论切割图(切割经过的顶点和边所形成的图)的种类数。由于平面展开图的边界是连通的,所以切割图也是连通的;另外切割中绝不可能出现环路,否则展开图的一部分就和主体断开了,我们所谓的展开图必须是连通的。连通且无环的图我们称之为树。并且,展开图的边界经过正方体的全部顶点,于是切割图也经过全部顶点。一个图的子图是树,若经过的全部顶点,我们称是的生成树,或支撑树。图片来源于byoshovel的回答 - 知乎
https://www.zhihu.com/question/310424939/answer/583733121
我们先回答一个基本又关键的问题:切割树究竟有多少个?Kirchhoff 矩阵-树定理 图的生成树集合的元素个数等于
其中表示任意的主子式,即去掉第行第列后剩下的子式。
由于正方体每个顶点都与3条棱连接,故其Laplace矩阵#R语言
A1<-c(0,1,0,1,1,0,0,0)
A2<-c(1,0,1,0,0,1,0,0)
A3<-c(0,1,0,1,0,0,1,0)
A4<-c(1,0,1,0,0,0,0,1)
A5<-c(1,0,0,0,0,1,0,1)
A6<-c(0,1,0,0,1,0,1,0)
A7<-c(0,0,1,0,0,1,0,1)
A8<-c(0,0,0,1,1,0,1,0)
A<-c(A1,A2,A3,A4,A5,A6,A7,A8)
A<-matrix(A,8,8,TRUE) #邻接矩阵
A
> A
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,] 0 1 0 1 1 0 0 0
[2,] 1 0 1 0 0 1 0 0
[3,] 0 1 0 1 0 0 1 0
[4,] 1 0 1 0 0 0 0 1
[5,] 1 0 0 0 0 1 0 1
[6,] 0 1 0 0 1 0 1 0
[7,] 0 0 1 0 0 1 0 1
[8,] 0 0 0 1 1 0 1 0
Lap <- diag(rep(3,8))-A #Laplace矩阵
det(Lap[-8,][,-8]) #去掉第8行第8列,并求其行列式
>[1] 384
!! 结论1 正方体的支撑树共有384个。
也就是说,我们所要寻找的正方体展开图的个数的上限是384,而这384种情况中,有大量在对称意义下的等价的情况,我们需要计算究竟有多少个等价类,这是我们所追求的答案。首先要明白我们是在什么对称意义下讨论——考虑正方体的等距对称群。从几何的角度而言,正方体有以下对称方式:这些对称变换可以相互叠加,就像是整数的加法一样,它们都是数学上的群。立方体等距对称群的代数表示为如果两棵生成树通过以上对称方式可以重合,我们就认为两者等价,或者换一种说法,两者处于群变换的同一轨道。我们设想任意一棵生成树,在以上全体变换下,演化出种种与之对称的情况,形成一个「轨道」,而不等价的树彼此形成的轨道彼此分离,否则两者处于同一轨道。于是我们的问题的答案正是轨道数。而计算轨道数也有现成的公式,我们同样不加证明引入——Burnside 引理 群作用在集合上,所形成的轨道数为:
其中
即在变换作用下保持不变的元素的集合。
如今我们让正方体的等距变换群作用于正方体的生成树集合,由抽象代数的知识可知,所以最终的问题全部聚焦于如何计算——在作用下不变的树的个数,这是问题的难点。所幸对于正方体的等距变换群而言,大多数,当然经过了数学家Richard Goldstone和Robert Suzzi Valli(2016)[1]一系列严格的证明。证明过程我们略去,直接说结论:!! 结论2 拥有不变树的变换只有两种:1. 关于对棱中点连线旋转180度(Rot2);2. 关于过四条平行棱中点的平面的反射(Ref2).
!! 结论3 不考虑恒等变换,上面两种变换Rot2、Ref2的不变树中都有且仅有一条不动边,并且将这个边反转,即设,,则
注意变换Rot2和Ref2本身的不动边分别是2条、4条。但是加上在一个不变树内的条件,于是只能有1条。于是我们采用逐渐生长的策略:选取一个不动边,对于Rot2而言有2种选择方式(),对于Ref2而言有4种选择();然后依照这两种变换,逐渐选取新的边、以及经过变换后的边,直到得到生成树为止。空心圆圈表示下一个新边生长「发芽」之处
由对称性,变换子群Rot2有个变换;变换子群Ref2有个变换。最后我们带入Burnside 引理的计算公式:参考文献
[1] Richard Goldstone and Robert Suzzi Valli(2016), unfoldings of the cube, arXiv:1604.05004 [math.GR].
[2] S.Axler, F.W. Gehring and K.A. Ribert, Algebraic Graph Theory.