和之前一样,我们还是通过一个有趣的问题来引入主题。
问题: 在 \(n\times n\) 的正方形网格图 \(G_n\) 的所有生成树中等概率地随机任选一个,记这个随机生成树为 \(T\),\(T\) 叫做 \(G_n\) 的一个均匀生成树。对 \(G_n\) 中任一顶点 \(v\),\(v\) 是 \(T\) 的叶节点的概率是多少?
这个问题可以换一种更通俗的描述:
问题: 对一个完全随机的 \(n\times n\) 的完美迷宫,它包含的“死角”的比例是多少?
为什么这两个问题是一回事?
一个迷宫称作是完美的,如果迷宫中的任何两个房间之间都有且仅有唯一的道路相连,这正是生成树的等价描述!迷宫中的一个房间称作是“死角”,当且仅当它只有一条道路与其它房间相通,没有其它出路,这正是叶节点的等价描述!
下图显示了三个不同的均匀生成树,它们分别来自大小为 \(80\times 80\),\(120\times120\) 和 \(200\times200\) 的三个网格图,这三个生成树的叶节点(用蓝色标出)占全体顶点的比例分别为 \(1884/6400=0.294375\),\(4234/14400\approx0.294028\),\(11776/40000=0.2944\)。咦?看起来好像是在围着一个固定的值波动喔?
更新:由于使用 POV-Ray 渲染三维双曲蜂巢非常的慢,所以我放弃了这种途径,并将代码从 Github 主分支中移除。你可以在 旧存档 中找到本文使用的代码。关于怎样渲染双曲蜂巢读者可以参考 另一个项目。
本文介绍我刚刚完成的一个 Python 程序。虽然是刚刚完成,但是它占去了我这半年来大部分的业余时间,也算是一个艰苦攻关,呕心沥血之作。主要是它涉及的理论比较复杂,要用到 Coxeter 群的一些深刻的性质,即所谓的 automatic property。这半年里面不少时间是花在学习 Casselman 和 Brink & Howlett 等人的文章上面,这才弄懂了其中的数学原理(见参考文献)。
虽然完成这个程序很有成就感,但是我无意强调这个程序的任何优越性:它采用的 Coxeter 群的计算方法并不先进,难入行家的法眼。而且它的代码比较丑,大概率除了我,别人也很难用起来。
这个程序的目的是使用群论的方式来绘制二维和三维的各种 均匀密铺。所谓均匀密铺,你可以理解为用一些正多边形的瓷砖密铺整个空间,使得瓷砖的顶点在对称群作用下是传递的(构成单一轨道)。
我先展示一些这个程序的例子,然后介绍它的实现原理。
Maryam Mirzakhani 在 2014 年的 一次报告 中提出了如下的问题:(问题大约在视频的 25 分 50 秒处)
问题: 假设平面上有一个正方形的房间,房间的四面墙壁都是光滑的反射镜子。子弹在碰到墙壁时会遵循入射角等于出射角的规律无限反射下去。房间中有一位政要和一个刺客,他们的位置是固定的,但可能是房间中任何两点。能否在房间中放置有限数量的保镖,使得这些保镖可以封锁刺客的所有射击角度,从而确保政要不被子弹击中?
根据 这篇论文 的考据,这个问题曾经在 1989 年列宁格勒的数学竞赛中出现过。最近,通过 PBS 和 math3ma 的博客 的科普推广,这个问题又引起了不少人的兴趣。我强烈建议读者在深入阅读本文之前,先观看这些视频和博客。它们的讲解非常通俗易懂,对于普通读者来说非常友好。
Greg Egan 在他的博客中 进一步讨论了房间是正三角形和正六边形的情况。虽然他给出的答案是正确的,但是他对正六边形情形的解释有点让人难以理解(Greg Egan 的一贯风格)。
正方形、正三角形和正六边形是仅有的三种可以用有限多个保镖保护目标的情形,对其它正 \(N\,(N\ne3,4,6)\) 边形房间,有限数量的保镖是不行的。
本文是对 math3ma 和 Greg Egan 博客文章的补充,我将主要针对正六边形的情况进行详细解释。我觉得从仿射 Weyl 群的角度来看这个情形最方便,但这对大多数读者来说可能是个陌生的概念。我还是假定读者知道群的概念,并尽量结合直观的图形来解释。如果读者对深入了解仿射 Weyl 群感兴趣,可以参考 Humphreys (1990) chapter 4。
本文的代码在 Github 上。这个项目包含了一个交互式的脚本,你可以在窗口中点击并拖拽鼠标来查看刺客射击的轨迹以及保镖的位置:
正方形 | 正三角形 | 正六边形 |
2021/06/27 更新:我更新了一下 shader 代码,把每个动画放在一个 SVG 图片中。最后几个动画代码是可以使用键盘选择场景的,具体操作如下:
- 按下
1
开启/关闭 Möbius 变换。 - 按下
2
开启/关闭椭圆旋转。 - 按下
3
开启/关闭双曲缩放。 - 按下
4
开启/关闭展示 Riemann 球面。
这几个按键可以组合出许多不同的效果来!
本文的想法源自 Roice Nelson 的 shadertoy 项目,我觉得他的创意很棒,就是效果有点糙,于是 动手改进了一番。不懂的人看这个动画可能只是觉得好玩,其实它背后的数学并不简单。
这篇文章将用动画的形式从三个角度演示 Möbius 变换,这三个角度是密切相关的:
- Möbius 变换作为扩充复平面 \(\hat{\mathbb{C}}\) 到自身的全纯函数。
- Möbius 变换作为 Riemann 球面 \(S^2\) 到自身的全纯函数。
- Möbius 变换作为上半双曲空间中的等距变换。
本文只做演示,并不介绍详细的数学证明。读者可以参考下面的资料:
- 维基百科页面.
- Visual complex analysis, Tristan Needham.
- Indra’s pearls, chapter 3.
- An introduction to complex function theory. Bruce P. Palka. Undergraduate texts in mathematics. chapter IX, section 2.
本文的动画应该可以帮助你更好地理解这些资料中的内容。
当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器