最著名的数学电影——《心灵捕手》，求解电影中的图论难题

本文的目的是向你讲述1997年奥斯卡获奖电影《心灵捕手》中的虚构人物威尔（Will）解决的两个数学问题。

电影中的情节

《心灵捕手》讲述了虚构人物威尔·亨特的故事，尽管他拥有非凡的智慧，但他却在波士顿的麻省理工学院担任清洁工。有一天，他在走廊的黑板上发现了一个由菲尔兹奖获奖教授杰拉尔德·兰博（Gerald Lambeau）提出的问题。威尔拥有超强的记忆力，他记住了这个问题，并在家中浴室的镜子上解决了它。第二天回到麻省理工学院，他忍不住在黑板上匿名地写出了他的答案。
第二天，教授提出了另一个更难的问题。威尔再次解决了它，但当他写解题过程时被教授抓住了，教授震惊地发现麻省理工最聪明的年轻数学家是一个没有受过教育的清洁工。

第一个问题

  • 杰拉尔德·兰博教授审阅威尔写出的解题过程。
问题1：给定图G，求：
  1. 邻接矩阵A（在图论和计算机科学中，邻接矩阵是用来表示有限图的一个方阵。矩阵的元素表示图中顶点对是否相邻。）
  2. 找出长度为3的路径数的矩阵
  3. 从i到j的路径数的生成函数
  4. 从1到3的路径数的生成函数
  • 图1：图G
第一个问题，在图论中，求图G中顶点i到顶点j的路径数。为此，设G是一个顶点集合V ={1，2，3，4}的图，和边E ={(1、2)，(1,4)，(2、4)，(2、3)，(2,3)}，其中(2、3)是一个双边。
问题1的解
问题1.1，给定图G，求邻接矩阵A
邻接矩阵是用来表示有限图的一个方阵。邻接矩阵L的元素表示图中顶点对是否相邻。对于一个具有一组顶点V的简单图（一个自环是两个端点为同一顶点的边。如果有多于一条边连接同一对顶点，则它们均被称为重边。一个图的重数是重复次数最多的边的重复次数。如果一个图不含自环或重边，则称为简单图），邻接矩阵是一个正方形|L| × |L|矩阵，当顶点i到顶点j有一条边时，其元素L_ij为1；当顶点i到顶点j有两条边时，其元素L_ij为2；当顶点i到顶点j没有边时L_ij为0。矩阵的对角线元素都是零，因为在简单图中不允许从顶点i到自身（循环）的边。对于沿边集E的所有长度为1的路径，这给了我们如下图G的邻接矩阵：
  • 问题1.1的解。顶点i到j的边元素和图G的邻接矩阵，表示顶点i到j之间的边数
问题1.2，找出长度为3的路径数的矩阵
问题1.2是找出一个矩阵，编码了长度为3的路径的所有可能情况。从i到j的n + 1步路径包括从i到k的n步路径和从k到j的1步路径。也就是说，Lⁿ⁺¹的ij项由下面的和给出：
  • 方程1
例如，对于k = 1，2：
  1. 从顶点i到顶点j的路径，长度为3；
  2. 从顶点i到k的路径，长度为2；
  3. 从顶点k到j的路径，长度为1。
通过矩阵乘法，对于从i到j的所有长度为3的路径，给出了以下矩阵：
  • 问题1.2的解。表示图G中顶点i到j长度为3的路径数的矩阵
问题1.3，求i→j路径数的生成函数
问题1.3要求从顶点i到j的生成函数。为了回答这个问题，霍瓦特（Horváth）等人考虑一个由幂级数定义的解析生成函数：
  • 方程2
其中系数z^n表示从i到j的路径数为n的数目。从问题1.3中，我们发现ω_n（i→j）是矩阵L^n的ij项。这个问题要求生成能同时给出所有项的生成函数，因此考虑由我们熟悉的幂级数给出的矩阵L是有意义的：
  • 方程3
其中L^n是包含从每个顶点i到j的路径数的数目的矩阵（解决问题1.2的一般情况）。可以用常见的几何幂级数恒等式来计算求和，即：
  • 方程4
为了计算(I−z × L)的逆，我们可以使用克莱默法则。设M_ij为去除M的第i列和第j行得到的矩阵,得到一个矩阵N，它的ij项是:
  • 方程5
根据克莱默法则，如果M是可逆的，则
  • 方程6
即逆矩阵M的ij项为：
  • 方程7
计算M =（I−z × L）的逆，得到：
  • 方程8
代替M：
  • 问题1.3的解。从i到j的路径数的生成函数
这就是威尔在电影中的解，只不过他的解省略了（−1）^（i+j）这一项，他用1表示单位矩阵，而不是更常见的i。
问题1.4，求路径数从1到3的生成函数
为了解决问题1.4，我们应用从i到j的路径数的一般公式，再到1到3的情况：
  • 方程9
它的行列式很容易找到：
  • 方程10和11，(I - zL)的行列式及（I₁₃−zL₁₃）的行列式
给出以下表达式，利用行列式的定义得到：
  • 方程12，从顶点1到顶点3路径数的生成函数的确定公式。
  • 方程13。求解了从顶点1到顶点3路径数的生成函数值的确定公式
为了得到这个幂级数的系数，我们计算函数的泰勒级数：
  • 方程14。用于计算f（z）的泰勒级数的函数，麦克劳林级数，其中f^n（0）是f在0处的n阶导数。
对于表达式f（z），我们可以使用除法法则，g（z） = 2z^2，h（z） = 4z^3−6z^2−z +1。在影片中，威尔提供了f（z）展开的前六个导数的值，它们是：
  • 问题1.4的解。

第二个问题

  • 兰博教授盯着第二个问题的正确答案
由于威尔并没有在他的答案上署名，所以兰博教授提出了第二个问题，他对他的同学们说“我们花了两年多的时间来证明”。这个问题与树结构有关：
问题2

a.n个结点上的树的数量是多少？

b.绘制所有n = 10的同态（胚）不可约树

问题2的解
问题2.1实际上是在问：对于一个正整数n, n个结点上的树的数量是n^（n-2）。这个公式是以亚瑟·凯利的名字命名的。1889年，凯利在《纯粹与应用数学季刊》上发表了一篇关于树的定理的笔记，他通过考虑结点的度（也即是宽度，简单地说，就是结点的分支数），扩展了这个公式，因此该公式以他的名字命名。
问题2.2要求绘制所有n = 10的同态不可约树。同态不可约树是没有2度的树。
我们可以通过将同态不可约树的顶点标记为 1，…., 10来分组，其结点的度是d_₁，…，d_₁₀。因为树有10个结点，我们知道它们有9条边。我们可以根据叶子的数量（结点度为1的点）对这些树进行分类：
如果有9个叶，1个非叶，则我们得到一个“星形”，单个结点连接每一个叶：
  • 如果有8叶和2非叶，那么 d_₁ + d_₂ = 10和d_₁≥d_₂≥3，所以：a) d_₁= 7，d_₂= 3（一棵树）；或b) d_₁= 6和d_₂= 4（一棵树）；或c) d_₁= d_₂= 5（一棵树）。
  • 具有8个叶子的同态不可约树
若有7个叶子，则d_₁+ d_₂+ d_₃= 11，d_₁≥d_₂≥d_₃≥3，则：a) d_₁= d_₂= 5，d_₃= 3（两棵树），或b) d_₁= 5，d_₂= d_₃= 3（三棵树）。
  • a)同态不可约树，7个叶子，d_₁）d_₂= 5，d_₃= 3
  • b)同态不可约树，7个叶子，d_₁= 5，d_₂= d_₃= 3
如果有6个叶子，则d_₁+d_₂+d_₃+d_₄= 3。
  • 6个叶子的同态不可约树，d_₁= d_₂= d_₃= d_₄= 3
n=10，总共是10棵树。在电影中，只出现了8棵，要么是因为威尔被兰博教授打断了，要么是因为电影人制作人的疏忽。

题外话

在《心灵捕手》的早期版本中，角色威尔是一位物理学天才，但哈佛大学的谢尔登·格拉肖（Sheldon Glashow）认为这是关于一位数学家的故事，因为现代物理学通常是一个团队项目，而一些数学定理通常是一项单独的任务。影片的数学顾问是多伦多大学的物理学教授，已故的帕特里克·奥唐纳（ Patrick O’Donnell）。
据推测，威尔这个角色的原型是天才少年威廉·西迪斯（William Sidis，1898-1944），他以非凡的数学才能著称。
赞 (0)

相关推荐