您是否曾经尝试过下面的脑筋急转弯，即您必须连点成线，一笔勾勒出一座房子的轮廓，而不能越线而行？或者您点击过 Facebook 的好友推荐，或者玩过《卡坦岛殖民者》（Settlers of Catan）。如果是这样，您就体验了图论的一种形式，这是一个令中国西安交通大学刘旭军博士着迷的数学领域。

图论被用来理解复杂的网络。最近在"着色"研究方面取得的进展为优化网络结构和潜在的通信系统提供了启示。刘旭军博士和他的合作者成功解决了一个在该领域引起广泛关注的问题。

连点成线，一笔勾勒出房子的轮廓，且不越线。图片来源：XJTLU

刘博士说："我最初的计划是从事另一个数学领域的研究，但我被图论中优雅而美丽的证明思想所吸引。"

图论是数学的一个分支，探索图的关系和性质，但我们谈论的不是饼图和散点图。

那么什么是图形呢？

假设您想找出乘坐火车往返伦敦和维也纳的最有效方式。你可以把每个城市画成一个点（数学中称为顶点），把城市之间的路线画成直线或曲线（称为边）。顶点和边的组合构成了一幅图。然后，可以利用该图研究两个城市之间的联系和路线。图论可以帮助数学家对计算机科学和电子工程等各个领域的复杂网络进行建模和分析。

乘坐火车从伦敦前往维也纳： 图中显示了经过较小城市的可能路线。资料来源：XJTLU

最近，刘博士与美国大山谷州立大学的迈克尔-桑塔纳（Michael Santana）博士和泰勒-肖特（Taylor Short）博士合作，解决了一个引起图论研究人员广泛关注的问题。

该团队的研究涉及图论的一个方面，即着色。着色理论处理的问题是给图的某些部分贴标签，以符合某些规则并避免特定冲突。

例如，想象一下，你想给下面的每个点着色，这样就永远不会有两个相同颜色的点挨在一起--这就是着色的一个例子。

如果没有两个相同颜色的点相邻，那么四个点至少需要两种颜色。图片来源：XJTLU

刘博士解释道："我研究的着色类型叫做打包着色，它是由广播网络中的频率分配问题引起的。世界上有很多广播电台，我们想给每个电台分配一个频率；分配到相同频率的电台之间至少要有一定的距离，而每个频率要求的最小距离是不同的。这个问题带来的一个问题是'这种分配所需的最小频率数是多少？"

一对不共享端点的边的例子。资料来源：XJTLU

在最近的工作中，刘博士和他的合作者成功解决了数学家霍夸尔（Hocquard）、拉尤（Lajou）和卢扎尔（Lužar）于 2022 年在《图论杂志》（Journal of Graph Theory）上提出的一个问题。

这个问题涉及子立方图的分割，其中每个顶点（点）最多有三条边（线）相连。考虑到有两种不同类型的边缘，任务是确定如何将边缘划分为多个类别：

类型 I - 要求每对边不共用一个端点（每条边有两个端点）。

类型 II - 要求其中的每对边不仅不共用一个端点，而且它们的端点不被另一条边连接。

研究小组要解决的问题是，是否有可能在将 I 类的数量固定为一个的同时，尽量减少 II 类的数量。

两条不共用一个端点且其端点未被另一条边连接的边的示例。图片来源：XJTLU

刘博士说："通过解决这个猜想，我们为加深对亚立方图结构特性的理解做出了重大贡献，并可能为解决著名的厄尔多斯-奈舍特日尔猜想提供启示。它还可能为解决通信网络中的问题提供指导"。

自从刘博士决定在伊利诺伊大学亚历山大-科斯托奇卡（Alexandr Kostochka）教授的指导下攻读图论博士学位以来，他已经成功解决了多个猜想，其中包括2012年阿贝尔奖得主Szemerédi及其合著者提出的一个问题。

刘博士说，他将继续解决该领域的更多问题。"我计划继续研究图着色问题，重点是通过更多的方法探索包装着色，如组合零点定理（Combinatorial Nullstellensatz）和概率方法。希望通过这些研究方向，为该领域做出有意义的贡献。