🔢 mathematics

Kemeny's constant and Braess cliques in graphs

本文引入了布雷斯团（Braess cliques, $K_\ell$ ）的概念，将其定义为在插入图中会增加肯尼常数（平均旅行时间）的子图，并证明了对于 $\ell \geq 3$ ，此类团存在于多种图族中，包括几乎所有的连通平面标记图。

原作者： Jane Breen, Emma deBlieck, Kevin N. Vander Meulen

发布于 2026-08-06

📖 1 分钟阅读🧠 深度阅读

原作者： Jane Breen, Emma deBlieck, Kevin N. Vander Meulen

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一个城市，其中的每一条街道都是单行道，一名快递员在其中随机穿梭，完全随机地选择下一个转弯方向。他有时会陷入循环，有时会直接抵达目的地。在数学领域，特别是被称为“图论”的一个分支中，我们将这些城市映射为“图”——由点（顶点）和连接它们的线（边）组成。数学家们有一个特殊的工具叫做肯内米常数（Kemeny's constant），用来衡量我们的随机驾驶员从一个随机位置到达另一个随机位置的平均时间。你可以将其视为整个网络的“交通拥堵评分”：分数越低，意味着城市连接性越好，易于导航；分数越高，则意味着驾驶员可能会在其中漫无目的地徘徊很长时间。

通常你会认为，在城市中增加一条新路会让交通流量变得更好，从而降低这个拥堵评分。但在 20 世纪 20 年代，一位名叫迪特里希·布劳斯（Dietrich Braess）的交通工程师发现了一个令人脑洞大开的缺陷：有时，增加一条新路反而会让整个系统变慢。这就像是建造了一条捷径，却导致所有人同时涌向它，从而造成了交通瘫痪。虽然我们已经知道增加单条道路（即“布劳斯边”）可能会发生这种情况，但一组研究人员提出了一个疑问：如果我们一次性增加许多条道路，将一组孤立的点连接成一个紧密的集群，情况会如何？这会有所帮助，还是会让混乱更加严重？

简·布林（Jane Breen）、艾玛·德布里克（Emma deBlieck）和凯文·N·范德米伦（Kevin N. Vander Meulen）撰写的这篇论文深入探讨了那个问题。他们引入了一个新概念——布劳斯团（Braess clique）。想象一群朋友住在彼此互不相连的死胡同街上。如果你突然建造一个巨大的环岛将他们所有人连接在一起，你可能会预期交通会改善。但作者证明，在某些特定的图结构中，这样做——即将一组孤立的点变成一个完全连接的“团”——实际上会增加随机行人的平均旅行时间。这非常违反直觉：增加更多的连接反而降低了系统的效率。

研究人员并非仅仅靠猜测；他们使用了严谨的数学方法来展示这种现象何时以及为何发生。他们发现，如果你采用某种特定类型的图（例如带有“悬挂”顶点，即像树枝上的叶子一样的顶点，的树状图），并将这些叶子连接在一起，你就可以创造出一个布劳斯团。他们证明了对于几乎所有的连通平面图（即可以在纸上绘制且线条不交叉的地图），你都能找到三点或更多点的组合，一旦将它们连接起来，就会减慢随机行人的速度。

或许最令人惊讶的发现是这些“坏”连接是如何相互作用的。你可能会假设，如果一条路是“布劳斯路”（即会导致变慢的道路），那么一组这样的路在一起肯定会构成一个“布劳斯团”。作者表明事实并非总是如此。他们发现，有些道路组构成了一个布劳斯团，尽管该组中的任何单条道路本身都不是布劳斯路。反之，他们也发现了这样一些组，其中每一条路都是布劳斯路，但将它们全部连接在一起却并不会产生布劳斯团。这有点像：往蛋糕里加入一些坏食材可能会毁掉它，但加入整整一碗可能又会以一种奇特的方式达到平衡，或者反之亦然。

该论文还探讨了完全二部图（想象两组人，A 组中的每个人都与 B 组中的每个人是朋友，但 A 组中的任何人都与 A 组中的其他人不互为朋友）。他们计算了在向其中一组添加一个团时，何时会导致结果适得其反的精确条件。例如，在一个拥有 90 人的一组和 10 人另一组的图中，添加一个最多包含 32 人的团会使系统变差，而“最差”的添加方式是一个恰好有 33 人的团。

最终，这项工作不仅仅是寻找了一些奇特的例子；它描绘了这些悖论的版图。它表明，增加道路与交通流量之间的关系远比“路越多 = 交通越好”要复杂得多。通过理解这些“布劳斯团”，数学家可以更好地预测网络（从社交媒体连接到计算机数据流）在尝试通过增加链接来“修复”它们时会如何表现。作者总结道，虽然我们已经找到了许多通过增加连接来破坏网络的方法，但关于不同点的特定“可达性”及其如何驱动这些奇异、反直觉的结果，仍有许多值得学习之处。

技术摘要：图中的 Kemeny 常数与 Braess 团

问题陈述
Kemeny 常数 $K(G)$ 是一个谱不变性，用于衡量在图 $G$ 中，以顶点度数作为权重随机选择两个顶点时，随机游走路径的期望长度。一种被称为 Braess 悖论的反直觉现象存在于图中：向图中添加一条边会导致 $K(G)$ 增加，从而降低了从随机游走角度来看图的整体连通性或“效率”。这样的边被称为“Braess 边”。虽然 Braess 边的存在已在多种图族（例如具有悬挂孪生顶点的树、完全多部图）中得到证实，但同时添加多条边的行为研究尚不充分。具体而言，本文研究了“Braess 团”的概念：即一个独立集，在该集合中插入所有可能的边（形成一个团）会导致 $K(G)$ 增加。核心问题是：在什么条件下会存在 Braess 团，它们与单个 Braess 边有何关系，以及什么样的结构属性会促进这种现象的发生。

方法论
作者结合使用了谱图论、马尔可夫链分析和组合矩阵理论。

马尔可夫链公式化： 图上的随机游走被建模为具有转移矩阵 $T = D^{-1}A$ 的马尔可夫链。Kemeny 常数可以表示为非平凡特征值之倒数的和，或者通过平均首次到达时间以及 $I-T$ 的广义逆进行结构化表示。
等价划分与商矩阵： 本文的一个核心方法论工具是使用等价划分。当图中包含“孪生顶点”（共享相同邻接集的顶点）时，转移矩阵可以简化为一个较小的商矩阵。作者推导出了将原图的 Kemeny 常数与其商矩阵联系起来的表达式，从而可以在不重新计算完整谱的情况下，分析在孪生集内添加边的影响。
可达性指数： 本文利用了可达性指数 $\alpha_G(v)$ ，它代表了从平稳起点到达顶点 $v$ 的期望时间。作者建立了原图与添加悬挂顶点或团之后的图之间关于可达性指数的关系。
结构分解： 对于具有割点或特定分离（1-分离）的图，作者应用了将 $K(G)$ 分解为子图组件的公式，从而便于计算添加边时 $K(G)$ 的变化。

主要贡献与结果

Braess 团的定义与特征化： 本文正式定义了一个 Braess 团 $K_\ell$ 为一个包含 $\ell$ 个顶点的独立集，其中插入完全图 $K_\ell$ 会增加 $K(G)$ 。作者提供了一个通用公式（定理 3.5），用于计算向具有公共度数为 $r$ 的 $k$ 个孪生顶点组成的独立集添加团时 Kemeny 常数的变化。该公式取决于顶点的可达性指数和图的大小。
特定图族中的存在性：
- 带有悬挂孪生顶点的图： 作者分析了将 $k$ 个悬挂顶点连接到单个顶点 $v$ 的图。他们推导出了导致该独立集构成 Braess 团的充分条件（推论 4.5）：如果原图中的边数 $m$ 满足 $m > \frac{k+1}{4}$ 。
- 完全二部图： 通过扩展先前关于 $K_{\ell, n-\ell}$ 中 Braess 边的研究结果，本文确定了在一个部集中存在阶数为 $k$ 的 Braess 团的充要条件（定理 4.7）。该条件为 $k < \frac{7\ell - 3n + 2}{5}$ 。
- 平面图： 通过改编先前文献中关于 Braess 边的论证，作者观察到几乎每个连通的标记平面图对于任何 $\ell \ge 3$ 都拥有一个 Braess $K_\ell$ （推论 4.6）。
Braess 边与团之间的相互作用： 本文挑战了以下直觉：即一个 Braess 团必须完全由 Braess 边组成，或者 Braess 边的团必然构成一个 Braess 团。
- 定理 5.1： 展示了在完全二部图 $K_{\ell, 2}$ （对于 $\ell \ge 4$ ）中，与度数为 2 的顶点对相连的边是 Braess 边，然而这些顶点构成的共团并不构成 Braess 团。
- 定理 5.3： 构建了一个图族（涉及附着在基础图上的蜘蛛图），该族拥有一个 Braess $K_3$ ，其中三条边本身都不是 Braess 边。
- 定理 5.13： 提供了一个 Braess $K_3$ 的例子，其中恰好有一条边是 Braess 边，而另外两条不是。

意义与主张
本文声称推进了对“添加边导致 Kemeny 常数增加”这一结构机制的理解。其主要意义在于证明了 “Braess 效应” 不仅仅是单条边的属性，而是可以通过同时添加形成团的多条边来放大或改变。作者强调，Braess 边与 Braess 团之间的关系是非平凡的：

一组 Braess 边不一定构成一个 Braess 团。
一个 Braess 团可能包含不是 Braess 边的边，甚至可能完全不包含 Braess 边。

这项工作表明，可达性指数是预测这些现象的关键参数。作者总结道，虽然 Braess 边的存在在某种程度上是反直觉的，但 Braess 团的存在则更加反直觉，因为人们通常会预期添加一个高度连通的子图（一个团）会普遍提高连通性。本文提供了明确的构造和代数条件，划定了直觉失效的边界，为随机游走在图上的研究提供了更深层的结构见解。作者谦虚地建议，进一步探索可达性指数的作用以及对于具有大型独立集的图中 $K(G)$ 变化的幅度，仍是一个值得研究的领域。

类似论文