单向铁路网络的奇偶性条件-计算机科学-机器学习-算法.pdfVIP

单向铁路网络的奇偶性条件

DaiAkita∗DanielSchenz†‡

2025年7月10日

本

译

中摘要

3我们提出了玩具火车轨道网络为单向的奇偶条件，即每个可到达

v

4点只能从一个方向接近。我们证明了这个问题等价于确定由该网络获

4

0得的有符号图的平衡性，其中边被赋予正号或负号。利用有符号图理

0

1论，我们推导出两个等效的单向奇偶条件：(i)每个循环必须包含连接

.

8同一侧开关的偶数条边，以及(ii)每个循环在开关处必须包含偶数个

0

3角度。有符号图理论还提供了一个分析标准：一个连通网络为单向当

2且仅当其有符号拉普拉斯矩阵的最小特征值为零，这暗示了一种计算

:

v

i工具来评估单向性。

x

r

a

1介绍

玩具火车（见图1）是简单的玩具，却能为儿童、成人和数学家提供长

时间的乐趣。确实，一些研究人员已经研究了从玩具火车衍生出的数学问

题。Demaine等人[1]考虑了一个问题，即有限长度的火车是否可以从一种

∗GraduateSchoolofInformationScienceandTechnology,TheUniversityofTokyo,

7-3-1Hongo,Bunkyo-ku,Tokyo113-8656,Japanxd.akita@ne.t.u-tokyo.ac.jp

†StrategicPlanningOffice,KobeUniversity,Japan

‡CorporateCommunications,UniversityofVienna,Austria

1

图1:我们考虑由直轨、弯轨、道岔和桥梁组成的玩具铁路。桥梁的存在

使得非平面网络成为可能。此外，我们需要铁路是封闭的，即它们没有死

胡同。

配置移动到另一种配置，并利用非确定性约束逻辑分析该问题的难度，这

种逻辑用约束图表示重新配置问题。Mitani[2]考察了由圆弧和不分支的直

线段组成的铁路线。他证明了通过组合这些元素可以到达平面上的任意点，

并且还研究了形成闭合路径需要多少个部件。

Garmo[3]考虑了我们在这里分析的完全相同的铁路网络模型。在这个

模型中，火车沿着轨道向前移动，并且永远不会被允许倒退；特别是，它不

能直接在Y形道岔的两个分支末端之间行驶。在这种限制下，我们观察到

几种特征性网络类型（图2）。在一个功能网络（图2a）中，从任何一点出

发的火车可以到达其他所有点，而在一个故障网络（图2b）中，这种全局

可达性失败了。A单向铁路网络（图2c）允许所有轨道固定一个方向，使

得每个火车行程都与该方向一致——或者完全相反——而一个双向铁路网

络（图2d）则不允许有这样的定向。

加莫[3]正式处理这些铁路网络的特征，并考虑随机铁路网络拥有这些

特征的概率。为了计算这些概率，他将铁路网络建模为3-正则多图，从数

学上定义了这些属性，并证明了功能性和单向性的概率分别收敛到1/3和

0，当网络规模趋于无穷大时。虽然他推导了一个功能的几何必要且充分条

件——即不存在吸收-配置——但其他几何方面仍然存在未解之谜。

这里，我们通过有符号图理论的视角来关注单向铁路网络的特性。由

哈拉里[4]引入的有向图是一个边带有正号(+)或负号(–)的图。如果每

2

(a)