连接点：中国数学家解决了热门着色问题
BALI @ 2023.09.20 , 07:09 上午
乘火车从伦敦前往维也纳： 图中显示了途经较小城市的可能路线。
你是否试过一个脑筋急转弯游戏，需要你在一个连续的笔画中将点连接起来，以勾勒出一座房子的轮廓，而不要回头重画线条？或者你可能点击过Facebook的好友推荐，或者玩过《卡坦岛》。
如果是这样，你就经历了图论的一种形式，这是中国西交利物浦大学的Xujun Liu博士所着迷的数学领域。
Liu博士表示：“我最初的计划是研究数学的其他领域，但我被图论中的证明思想的优雅和美丽所吸引。”
图论是数学的一个分支，探讨图的关系和属性，但我们不是指饼图和散点图。
假设你想找出从伦敦到维也纳最有效的火车旅行方式。你可以将每个城市表示为一个点(在数学中称为顶点)，将城市之间的路线表示为线条或曲线(称为边)。顶点和边的组合构成了一个图。
然后可以使用该图来研究两个城市之间的连接和路线。
图论可以帮助数学家在包括计算机科学和电气工程在内的各个领域中建模和分析复杂网络。
Liu博士与美国格兰德谷州立大学的Michael Santana博士和Taylor Short博士合作，最近解决了一个吸引了图论研究者很多关注的问题。论文《每个子立方图都是(1,2^7)-包装边着色的》发表在《图论杂志》上。
着色示例： 如果没有两个相同颜色的点相邻，那么四个点至少需要两种颜色。
不同颜色的着色
该团队的研究涉及图论中的一项内容，称为着色。着色理论涉及标记图的部分以符合某些规则并避免特定冲突的问题。
例如，想象一下你想要为下面的每个点涂上颜色，以确保相邻的两个点永远不会有相同的颜色-这就是一种着色问题。
Liu博士解释说：“我研究一种称为包装着色的着色类型，它涉及广播网络中的频率分配问题。
“世界上有许多广播电台，我们希望为每个电台分配一个频率；分配相同频率的电台需要彼此之间至少保持一定的距离，并且每个频率需要不同的最小距离。
“从这个问题中引申出的一个问题是‘这种分配所需的最小频率数量是多少？’”
战略发展
在最近的研究中，Liu博士和合作者成功解决了2022年《图论杂志》中Hocquard、Lajou和Lužar提出的一个问题。
这个问题涉及到子立方图的划分，其中每个顶点(点)最多与三条边(线)相连。
任务是确定如何将边分成多个类别，考虑到存在两种不同类型的边：
类型I-要求每对边不共享一个端点(每条边有两个端点)。
类型II-要求其中的每对边不仅不共享一个端点，而且它们的端点也不通过另一条边相连。
该团队尝试解决的问题是，是否可能在类型I连接和类型II连接之间进行完美的划分，即每个子立方图都具有相同数量的类型I和类型II的边。
通过深入研究子立方图的性质和结构，Liu博士和他的合作者发现了一种划分方法，可以满足上述要求。他们证明了每个子立方图都可以进行(1,2^7)-包装边着色，这意味着可以使用27种不同的颜色对每个边进行着色，而且相邻的边不会有相同的颜色。
这项研究的结果对于理解和解决图论中的其他问题具有重要意义，特别是与子立方图相关的问题。它对计算机科学、通信网络和组合数学等领域的研究和应用具有潜在的影响。
Liu博士表示：“解决这个问题是一个重要的里程碑，它填补了图论中的一个空白，并为未来的研究提供了新的方向和挑战。”
该研究的成功展示了数学在解决实际问题和推动科学进步方面的重要性。图论作为一门数学分支，为我们理解和分析各种复杂系统和网络提供了有力的工具。
Liu博士和他的合作者的工作为图论领域的发展做出了宝贵的贡献，并为解决其他着色和图分割问题提供了新的思路。他们的成果将进一步推动图论的研究，并有可能在实际应用中产生重要影响。
PREV : 清华的规划师们发现，AI系统被在城市规划设计方面超越人类
NEXT : 摸鱼日报 [第18期]