Rotating Polyhedron

官方信息技术老师·20 页·深入(追求细节与边界)·0 次浏览·2 天前
旋转对称Burnside染色计数等价类

旋转多面体与Polya计数

看穿旋转等价:从对称群到 Burnside 计数,本质不同的染色到底有几种

按 空格/→ 演示下一步

1 / 20 页

全部页面点击任意一页,跳回舞台从这页播放

旋转对称Burnside染色计数等价类

旋转多面体与Polya计数

看穿旋转等价:从对称群到 Burnside 计数,本质不同的染色到底有几种

1第 1 页 · 旋转多面体与Polya计数

什么是旋转多面体

上一页我们看到 Polya 计数能剔除旋转带来的重复。要做这件事,前提是先严格界定:哪些操作算「让多面体回到自身」的合法旋转?这就要从数学上定义「旋转」本身。

SO(3) 中的旋转
det=+1 的 3×3 正交矩阵,保距、保角且保持定向
旋转的不动轴
存在一条不动点直线(旋转轴),轴外点沿圆弧运动
保持多面体不变
R·P = P:面、棱、顶点被置换到自身的位置
旋转角离散化
由对称性强制为 2π/n,n ∈ {2,3,4,5}
全体旋转成群
G ⊂ SO(3),群运算为旋转复合,阶数有限
骰子绕对称轴转 90°对应 →正多面体的合法旋转

轴过中心、角度离散、转后与原物重合——与定义一一对应

RSO(3), RR=I, detR=+1, u0: Ru=uR \in SO(3),\ R^{\top}R = I,\ \det R = +1,\ \exists\,\mathbf{u}\neq 0:\ R\mathbf{u} = \mathbf{u}
2第 2 页 · 什么是旋转多面体

正多面体的分类

上页划定了旋转多面体的范围。在它内部,对称性最高的一类——每个面、每条棱、每个顶点彼此等价——就是正多面体(柏拉图立体),世界上恰好五种,每种都自带一个固定的旋转对称群。

正四面体
4 个正三角面;旋转群 T,阶 12
正六面体(立方体)
6 个正方面;旋转群 O,阶 24
正八面体
8 个正三角面;旋转群 O,阶 24,与立方体对偶
正十二面体
12 个正五边面;旋转群 I,阶 60
正二十面体
20 个正三角面;旋转群 I,阶 60,与十二面体对偶
铺平面:正多边形只用三种对应 →正多面体只有五种

同一约束:顶点处正多边形角之和。平面凑到 360°,立体要严格小于 360°,正多边形内角有限,五种拼法全列完

VE+F=2V - E + F = 2
3第 3 页 · 正多面体的分类

正多面体的旋转群结构

看图:从正多面体出发,展开到各旋转群的对称轴构成。

图解渲染中…
T1通过四面体顶点的3重旋转轴T2通过四面体棱中点的2重旋转轴O1穿过对面中心的4重旋转轴O3连接对棱中点的2重旋转轴
4第 4 页 · 正多面体的旋转群结构

旋转作为面的置换

上一页看清了正多面体旋转群的阶与对称轴分布。这一页再下一层:每个具体旋转,到底把面搬到了哪?答案是——它把面集重新排了一遍。

面的像
旋转 g 把每个面 f 送到另一个面 g·f,仍是同一多面体的面
置换视角
把「f → g·f」列成表,就得到对称群 S_F 中的一个置换 σ_g
忠实同态
g ↦ σ_g 是 G→S_F 的群同态且核平凡,所以 G 嵌入 S_F
顶点和边同理
同样方式得 G 到 S_V、S_E 的同构嵌入,三种刻画彼此等价
魔方转动对应 →旋转对面集的置换

转魔方时每块小方块挪到新位置;多面体旋转也把「面」重排一次,规则就是置换

ϕ:GSF,g(fgf)\phi:\, G \to S_F,\quad g \mapsto (f \mapsto g\cdot f)
5第 5 页 · 旋转作为面的置换

立方体旋转的置换表示

由顶向下读:先看24个旋转按共轭类分成5组,再看每组在8顶点上的循环结构。

图解渲染中…
C2绕面中心轴的9个旋转C3绕体对角线的8个旋转C4绕棱中点的6个旋转S3与S5同循环结构,但属不同共轭类
6第 6 页 · 立方体旋转的置换表示

循环结构与不动点

上一页我们把立方体旋转写成了面的置换——一个6×6的矩阵。但矩阵不便直接数不变染色。

循环分解
任何置换都能拆成若干不相交的循环,每个元素恰属于一个
循环长度
一个循环内元素的个数,即该循环走几步回到自身
染色不动点
置换作用后染色不变,则该染色是该置换的一个不动点
循环同色法则
染色不动,当且仅当同一循环内所有面颜色相同
循环数决定染色数
用k种颜色,被某个置换固定的染色数等于k的循环数次方
值日小组围一圈对应 →循环内的同色约束

同一圈的人绑定:要动一起动,要停一起停

#Fix(σ)=kc(σ), c(σ)=σ 的循环数\#\text{Fix}(\sigma) = k^{c(\sigma)},\ c(\sigma)=\sigma\text{ 的循环数}
7第 7 页 · 循环结构与不动点

求旋转群的方法

求一个多面体的旋转群,按这五步走就能不重不漏。

1
找旋转轴
枚举穿过对顶点、对棱或对面的直线
2
确定轴阶
判断绕该轴转几度后多面体与自身重合
3
枚举旋转
列出每条轴上的非恒等旋转,按阶列举
4
加上恒等
恒等旋转(什么也不动)必须算一次
5
验证成群
检验封闭性,确认总数即为群阶 |G|
8第 8 页 · 求旋转群的方法

循环指标的定义

上一页我们把每个旋转都拆成了循环。这页要做一件事:把这 24 份『循环报告』汇总成一张总表——对每种循环类型,统计它在全群中出现几次,最后除以群的大小。

循环单项式
一个旋转拆完循环后,长 k 的循环有 c_k 个,贡献 x_k 的 c_k 次方
全群求和
24 个旋转各写一项单项式,结构相同的合并,系数就是出现的次数
除以群阶数
再除以 |G|=24,把『频次』转成『每个旋转的平均贡献』
群指纹 Z(G)
整个群的代数指纹;之后 Pólya 计数会把这个多项式原样代入
全班体检报告汇总对应 →循环指标

每份体检报告对应一个旋转的循环结构,循环指标就是全班报告的平均统计

Z(G)=1GgGx1c1(g)x2c2(g)xncn(g)Z(G) = \dfrac{1}{|G|} \sum_{g \in G} x_1^{c_1(g)}\, x_2^{c_2(g)} \cdots x_n^{c_n(g)}
9第 9 页 · 循环指标的定义

循环指标的计算流程

从旋转群出发,五步得到循环指标多项式 Z(G)。

1
确定旋转群
列出全部旋转操作,统计群阶 |G|
2
选定着色集
明确对面/顶点/边的置换对象
3
分解循环结构
把每个旋转写成不相交循环之积
4
编码为单项式
长度 i 的循环 k 个记作 xᵢ^k
5
求和并平均
所有单项式相加再除以 |G|,得 Z(G)
10第 10 页 · 循环指标的计算流程

立方体旋转群循环指标

立方体24个旋转按轴类型分类,每类给出循环结构与个数,最终汇成循环指标。

图解渲染中…
D1面轴转90°或270°:4侧面循环,2面不动D2面轴转180°:形成两个2-循环加两个不动C3顶点轴转120°/240°:6面分两组轮转C4棱轴转180°:6面分三个2-循环
11第 11 页 · 立方体旋转群循环指标

循环指标的代码实现

Python计算多面体循环指标的核心算法

循环指标的代码实现
Python计算多面体循环指标的核心算法
12第 12 页 · 循环指标的代码实现

Polya计数定理

上一页我们把立方体旋转群写成了循环指标 Z——一堆带字母的代数式。现在追问:怎么把 Z 变成具体数字?比如,用 3 种颜色染 6 个面,本质不同的方案有几个?

Polya 定理的角色
把抽象的循环指标转化为可计算染色数公式的桥梁;本质是 Burnside 引理的代数化身
代入规则的直觉
每个 aᵢ 表示长度 i 的循环;同循环必须同色 → 用 k 色时长 i 循环恰有 k 种染色选择
k 色计数公式
(1/|G|) Σ k^{c(σ)};等价于把循环指标里所有 aᵢ 同时替换为 k
加权版本
想区分颜色用量时,把 aᵢ 替换为颜色权重和 Σxⱼ,可生成多变量计数函数
代数式里的字母换成数字对应 →循环指标的 aᵢ 换成 k

Z 是带变量的代数式;aᵢ=k 即把所有变量同时赋值为颜色数,得到具体计数

$N(k) = Z(G)(k,k,\ldots,k) = \frac{1}{|G|}\sum_{\sigma \in G} k^{c(\sigma)}$
13第 13 页 · Polya计数定理

染色计数的完整步骤

从问题描述到最终计数,六步走完一遍完整染色计数流程。

1
确定旋转群
明确多面体对象,列出全部合法旋转
2
列置换形式
把每个旋转写成面的置换 σᵢ
3
拆循环结构
统计每个置换的循环长度与个数
4
算循环指标
按循环类型加权求和,写出 Z(G)
5
代入颜色数
把每个 xₖ 替换为可用颜色数 m
6
求等价类数
Polya 定理一步算出不等价染色数
14第 14 页 · 染色计数的完整步骤

Burnside vs Polya方法对比

两种方法在旋转多面体染色问题中的优劣

Burnside vs Polya方法对
两种方法在旋转多面体染色问题中的优劣
15第 15 页 · Burnside vs Polya方法对比

立方体染色实例图解

四面体、六面体、八面体的具体染色计数

立方体染色实例图解
四面体、六面体、八面体的具体染色计数
16第 16 页 · 立方体染色实例图解

非正则多面体的处理

立方体染色我们算得清清楚楚。但立方体是正多面体,旋转有 24 种。一般凸多面体呢?有的除恒等外一动就变形,也有的介于两者之间——关键是系统地把它找出来。

对称性差异悬殊
有的多面体有几十种旋转,有的除恒等外一动就变形
枚举自旋转
在 SO(3) 中找出所有让多面体与自身重合的旋转
用图代替几何
把面棱顶点的邻接关系建成图,自同构就是旋转
自同构诱导置换
每个图自同构自然给出顶点/边/面上的置换
代回 Polya
把置换按循环结构代入循环指标公式即可
拼不规则拼图对应 →求非正则多面体旋转群

形状怪异的拼图块几乎只有一种摆法;非正则多面体自旋转也极少

Grot(P)Aut(F(P))G_{\mathrm{rot}}(P) \cong \mathrm{Aut}(\mathcal{F}(P))
17第 17 页 · 非正则多面体的处理

带约束的染色问题

前几页我们让 Polya 大包大揽——任意面、任意色、相邻随意。但真实染色总有规矩:调色板只有 k 种颜色,相邻两面不能同色。这些约束把游戏彻底改写了。

颜色数量受限
k 种颜色调色板:代入循环指标即可,本就是 Polya 默认设定
相邻面不同色
棱相连的两面颜色必须不同,本质是多面体表面的图染色
群作用被破坏
约束不沿群轨道封闭,Polya「同轨同计数」前提直接失效
问题变难
一般约束染色是 NP-hard;多面体实例因对称可化简但仍棘手
实用策略
分情况枚举、容斥原理、对称性剪枝,按结构选招数
地图四色问题对应 →多面体邻接约束染色

邻国不同色 = 邻面不同色,都是平面图染色

P(G,k)=1GgGkc(g)(无约束时k 直接代入)P(G, k) = \frac{1}{|G|} \sum_{g \in G} k^{c(g)} \quad (\text{无约束时} k \text{ 直接代入})
18第 18 页 · 带约束的染色问题

旋转多面体自测

点击作答

正四面体旋转群的循环指标为 Z = (1/12)(x₁⁴ + 8x₁x₃ + 3x₂²)。用 3 种颜色染 4 个顶点,按 Polya 定理不同染色方案数是?

19第 19 页 · 旋转多面体自测

课后思考与延伸

开放性问题:多面体旋转的深层结构与应用边界

课后思考与延伸
开放性问题:多面体旋转的深层结构与应用边界
20第 20 页 · 课后思考与延伸