作者 | 刘洋洲
来源 | 转自知乎专栏《万物皆数也》,“数学英才”获授权转载,在此感谢!
据先秦典籍《世本》记载:「尧造围棋,丹朱善之」。作为距今约有四千年历史的古老游戏,究竟与数学有何缘分?本文尝试叙述之。
图论预备知识我们先了解一下关于图的基本概念。
无论是东方的星宿或是西方的星座,都是古人对于图论最初的应用。事实上,围棋本身极可能起源于上古天文学,围棋棋盘中心点称为天元,其余8个特殊位置的点称为星位(图2)。
图1
图2:标准围棋棋盘
所谓图(Graph),是由一些离散的点以及连接这些点的边所构成。我们将图记为,其中表示顶点集(vertex set),表示边集(edge set)。如果两顶点之间存在边,则说两者相邻,记为,此外连接两者的边也可以说与此两点相邻。
显然围棋棋盘是一个图,记为。我们把下棋落子的过程视为构造子图的过程,所谓子图即满足:
我们定义图的商运算:将子图整体替换为一个顶点 ,保持子图之外的顶点以及与不相邻的边不变,凡是与相邻的边,则将此边的端替换为.
图3:图的商运算。将「喜」变成「吉」。这个图源于剪纸。
我们说两个顶点是道路连通,即存在一系列首尾相接的边构成的道路,分别以此两点为首尾端点(如果道路首尾端点是同一个点,则称道路为圈)。连通的概念也可以推广到图与图之间。一个图可能是由若干个不连通的子图构成,如果把漫天的星座视为一个巨大的图,则每个连通的星座可以被称为连通分支。