本
文
摘
要
引
问:正方体的平面展开图有多少种?
答:11种。
关于正方体展开图相信大家在小学的时候就有接触过相关问题,「11」这个结论往往老师一带而过,似乎这只是一个动手验证的结果,并不值得深思。
但如果真要深究下去,为什么偏偏是这11种?真的没有第12种展开图了吗?凸黄金多面体为何只有五种除了用计算机穷举的方法之外,有没有严格的数学证明呢?
铺垫
我们在曾经的文章《围棋中的数学原理(一)》中接触过关于图论的基础概念,接下来我们再引入一些更方便的代数工具,用来刻画图(本文我们只关注简单无向图)。
任意一个图有如下代数表示,我们称之为邻接矩阵:先给图G(V,E)G(V,E)的顶点标号,一个矩阵A=(aij)A=(a_{ij})的第ii行第jj列的元素aija_{ij}表示第ii个顶点与第jj个顶点是否存在一条边eij∈Ee_{ij}\in E相连,若存在,则aij=1a_{ij}=1,否则aij=0.a_{ij}=0. 标号方式不同,邻接矩阵固然不同,但它们彼此都是等价的(只需要交换若干次第ii行和第jj行,以及第ii列和第jj列,两个彼此等价的邻接矩阵会相互转换,想想为什么)。
例如一条长度为2的道路∙−∙−∙\bullet -\bullet-\bullet,我们不妨从左到右依次给各个顶点标号为1、2、3,于是它的邻接矩阵是
A=(010101010).A=\left( \begin{array}{ccc} 0&1&0\\ 1&0&1\\ 0&1&0 \end{array} \right).\\
我们在邻接矩阵的基础上稍微加工,就会得到:
Δ:=diag(degvi)−A\Delta :=\text{diag}(\deg v_i)-A \\
我们称之为图GG的Laplace矩阵。上例中各点的度数为:
degv1=1,degv2=2,degv3=1.\deg v_1=1,\quad \deg v_2=2,\quad \deg v_3=1. \\
于是∙−∙−∙\bullet -\bullet-\bullet的Laplace矩阵为:
Δ=(121)−(010101010)=(1−10−12−10−11).\Delta=\left( \begin{array}{ccc} 1&&\\ &2&\\ &&1 \end{array} \right)-\left( \begin{array}{ccc} 0&1&0\\ 1&0&1\\ 0&1&0 \end{array} \right)= \left( \begin{array}{rrrr} 1&-1&0\\ -1&2&-1\\ 0&-1&1 \end{array} \right).\\
证明概要
每一个正方体展开图都是通过沿着正方体的7条棱切割得到的。所以问题的关键在于讨论切割图(切割经过的顶点和边所形成的图)的种类数。
由于平面展开图的边界是连通的,所以切割图也是连通的;另外切割中绝不可能出现环路,否则展开图的一部分就和主体断开了,我们所谓的展开图必须是连通的。连通且无环的图我们称之为树。并且,展开图的边界经过正方体的全部顶点,于是切割图也经过全部顶点。一个图GG的子图TT是树,若TT经过GG的全部顶点,我们称TT是GG的生成树,或支撑树。
于是切割图一定是正方体的生成树Σ\Sigma.
图片来源于byoshovel的回答 - 知乎 https://www.zhihu.com/question/310424939/answer/583733121我们先回答一个基本又关键的问题:切割树究竟有多少个?
我们不加证明地引入——
Kirchhoff 矩阵-树定理 图GG的生成树 ***Σ\Sigma的元素个数等于
|Σ|=|detΔ−|.|\Sigma|=|\det \Delta^-|.\\
其中Δ−\Delta^-表示Δ\Delta任意的(n−1)×(n−1)(n-1)\times (n-1)主子式,即去掉第ii行第ii列后剩下的子式。
如上图写出正方体的邻接矩阵
A=[0101100010100100010100101010000110000101010010100010010100011010].A=\left[ \begin{array}{rrrr} 0&1&0&1&1&0&0&0\\ 1&0&1&0&0&1&0&0\\ 0&1&0&1&0&0&1&0\\ 1&0&1&0&0&0&0&1\\ 1&0&0&0&0&1&0&1\\ 0&1&0&0&1&0&1&0\\ 0&0&1&0&0&1&0&1\\ 0&0&0&1&1&0&1&0\\ \end{array} \right]. \\
由于正方体每个顶点都与3条棱连接,故其Laplace矩阵
Δ=[3−10−1−1000−13−100−1000−13−100−10−10−13000−1−10003−10−10−100−13−1000−100−13−1000−1−10−13].\Delta=\left[ \begin{array}{rrrr} 3&-1&0&-1&-1&0&0&0\\ -1&3&-1&0&0&-1&0&0\\ 0&-1&3&-1&0&0&-1&0\\ -1&0&-1&3&0&0&0&-1\\ -1&0&0&0&3&-1&0&-1\\ 0&-1&0&0&-1&3&-1&0\\ 0&0&-1&0&0&-1&3&-1\\ 0&0&0&-1&-1&0&-1&3\\ \end{array} \right]. \\
于是去掉最后一行、最后一列后,我们计算其行列式
detΔ−=384.\det \Delta^-=384. \\
#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种情况中,有大量在对称意义下的等价的情况,我们需要计算究竟有多少个等价类,这是我们所追求的答案。
首先要明白我们是在什么对称意义下讨论——考虑正方体的等距对称群。从几何的角度而言,正方体有以下对称方式:
旋转类 从左到右依次记为Rot1,Rot2,Rot3.反射类 从左到右依次记为Ref1,Ref2.这些对称变换可以相互叠加使用,就像是整数的加法一样,它们都是数学上的群。立方体等距对称群G=Isom(C)G=\text{Isom}(\mathcal{C})的代数表示为
Isom(C)=S4×Z2.\text{Isom}(\mathcal{C})=S_4\times \mathbb{Z}_ 2. \\
如果两棵生成树通过以上对称方式可以重合,我们就认为两者等价,或者换一种说法,两者处于群变换的同一轨道。我们设想任意一棵生成树,在以上全体变换下,演化出种种与之对称的情况,形成一个「轨道」,而不等价的树彼此形成的轨道彼此分离,否则两者处于同一轨道。于是我们的问题的答案正是轨道数。
而计算轨道数也有现成的公式,我们同样不加证明引入——
Burnside 引理 群GG作用在 ***XX上,所形成的轨道数为:
Orb(X)=1|G|∑g∈G|Fix(g)|.\text{Orb}(X)=\frac{1}{|G|}\sum_{g\in G}|\text{Fix}(g)|. \\
其中
Fix(g):={x∈X|xg=x}⊆X\text{Fix}(g):=\{x\in X\ |\ x^g=x\} \subseteq X \\
即在变换gg作用下保持不变的元素的 *** 。
Burnside引理是计数原理的基石。
如今我们让正方体的等距变换群G=Isom(C)G=\text{Isom}(\mathcal{C})作用于正方体的生成树 *** X=ΣX=\Sigma,由抽象代数的知识可知|G|=|S4×Z2|=48|G|=|S_4\times \mathbb{Z}_ 2|=48,所以最终的问题全部聚焦于如何计算|Fix(g)||\text{Fix}(g)|——在gg作用下不变的树的个数,这是问题的难点。
所幸对于正方体的等距变换群Isom(C)\text{Isom}(\mathcal{C})而言,大多数|Fix(g)|=0|\text{Fix}(g)|=0,当然经过了数学家Richard Goldstone和Robert Suzzi Valli(2016)[1]一系列严格的证明,证明过程我们略去,直接说结论:
!! 结论2 拥有不变树的变换只有两种:1. 关于对棱中点连线旋转180度(Rot2);2. 关于过四条平行棱中点的平面的反射(Ref2).
另外还有一个关键性的结论——
!! 结论3 不考虑恒等变换,上面两种变换Rot2、Ref2的不变树中都有且仅有一条不动边,并且将这个边反转,即设e=vivje=v_iv_j,g∈Rot2, Ref2g\in \text{Rot2, Ref2},则
eg=e=vjvi.e^g=e=v_jv_i.\\注意变换Rot2和Ref2本身的不动边不仅仅只有一条(分别是2条、4条)。
于是我们采用逐渐生长的策略:选取一个不动边,对于ρ0∈\rho_0\inRot2而言有2种选择方式(×2\times 2),对于φ0∈\varphi_0\inRef2而言有4种选择(×4\times 4);然后依照这两种变换,逐渐选取新的边、以及经过变换后的边,直到形成一棵生成树为止。
空心圆圈表示生长「发芽」之处于是可得
|Fix(φ0)|=4×4=16,|Fix(ρ0)|=8×2=16.\begin{array}{lll} |\text{Fix}(\varphi_0) |=4\times 4=16,\\ \\ |\text{Fix} (\rho_0)|=8\times 2=16.\\ \end{array} \\
由于对称性,像ρ0\rho_0变换群Rot2有12/2=612/2=6个变换;φ0\varphi_0变换群Ref2有12/4=312/4=3个变换。最后我们带入Burnside 引理的计算公式:
Orb(X)=1|G|∑g∈G|Fix(g)|=1|G|(|Fix(id)|+|Fix(Rot2)|+|Fix(Ref2)|)=148(384+6×16+3×16)=11.\begin{array}{llll} \text{Orb}(X)&\\ =\cfrac{1}{|G|}\sum_{g\in G}|\text{Fix}(g)|\\ =\cfrac{1}{|G|}(|\text{Fix}(id)|+|\text{Fix}(\text{Rot2})|+|\text{Fix}(\text{Ref2})|) \\ =\cfrac{1}{48}(384+6\times 16+3\times 16)\\=11. \end{array} \\
参考文献
[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.
为什么正方体有十一种展开图? 我老早以前写的回答,当时我还很稚嫩。方法很初等,也很简洁,只是我一直觉得可能不太严谨。