开发者生态
morning
晚宴上的狄拉克定理
2026-11-23
1 阅读
约5分钟阅读
prideout
字号:
晚宴上的狄拉克定理 晚宴 音乐椅 传递土豆 参考文献 加布里埃尔·狄拉克(著名的图论学家)是保罗·狄拉克(更为著名的物理学家)的继子。保罗·狄拉克 (Paul Dirac) 在佛罗里达州立大学度过了他职业生涯的最后几年,而我父亲则在 20 世纪 70 年代学习了广义相对论课程。加布里埃尔提出了一个关于哈密顿循环的重要定理。在这篇文章中,我想回顾一下哈密顿循环,并回顾一下他的定理的有趣证明,其中涉及假设的晚宴。在几十年的时间里,当数学家们提出了适用于更广泛的图形的类似定理时,狄拉克定理得到了改进。在下图中,每个定理都比左边的定理更普遍。每个图都满足其自己的定理条件,但其左侧均不满足,并且其哈密顿循环为蓝色。我为什么要写狄拉克定理?好吧,我想写一个与哈密顿循环相关的简单证明,作为我下一篇文章的准备,下一篇文章将是关于巴尼特猜想的,这是我最喜欢的图论猜想之一。它在 2026 年 10 月 6 日的数学灾难中被提升为定理。在我的下一篇文章中,我将详细讨论这一点。哈密顿循环是沿着图的边缘行走,仅访问每个顶点一次并最终回到开始的地方。具有哈密顿量的图。哈密顿循环与旅行商问题有关(例如为亚马逊包裹设计送货路线)。但我个人最喜欢的应用程序是一个老式的计算机图形问题:给定一个三角形网格,您可以使用单个三角形条来渲染它吗?直观上,在相对于其顶点数具有大量边的图中找到哈密顿循环应该更容易。在某种程度上,这种直觉就是狄拉克形式化的:定理 1(狄拉克,1952)如果一个简单的图有顶点,并且每个顶点至少有邻居,那么该图就有一个哈密顿循环。下图显示了一个有 10 个顶点的随机图,其中每个顶点恰好有 5 个邻居,因此该定理保证了哈密顿循环。在右侧,同一张图已重新排列,使其哈密顿循环围绕外部运行……就像圆形餐桌一样。要了解为什么该定理是正确的,首先想象一个聚会,其中每个客人都是一个顶点,每个友谊都是一个边。友谊是双向的,没有人是自己的朋友,这就是图论中简单的意思。哈密顿循环是一种让每个人都坐在圆桌旁的方法,这样每个客人都坐在两个朋友之间: 定理 2(狄拉克定理,在聚会上)如果聚会有客人,并且每个客人至少与其他客人是朋友,那么客人可以坐在圆桌旁,这样每个客人都坐在两个朋友之间。这是计划。每个人都按随机顺序就座。并排坐着的两个客人是同桌,他们可能是朋友,也可能是陌生人。是朋友的座位上的边缘是蓝色的,其他朋友的边缘是灰色的。陌生人的座位上会出现一个间隙,该间隙会出现一条橙色虚线。这是之前作为一方的图表,按随机顺序就座,有四个间隙:因此,如果我们能找到一种始终消除所有间隙的方法,那么我们就证明了该定理是正确的。我们将通过一系列有点类似于玩音乐椅的动作来做到这一点。说陌生人并肩而坐,只是顺时针的。并假设在桌子的其他地方,还有两个同座,并且 ,顺时针旋转 ,其中 是 的朋友,并且 是 的朋友。动作是这样的:大家从顺时针方向绕到站起来,再按相反的顺序坐下。这是一个翻转。然后,坐在 旁边,坐在 旁边,都是一对朋友。在下图中,翻转的拉伸部分呈蓝色阴影。拖动其下方的滑块以观看其翻转。为什么引理 1 为真?在翻转的这段时间内,每位客人都有两个和以前一样的座位,只是坐在相对的两侧。因此,唯一发生变化的座位是在两个端点。在翻转之前,那些是 和 ,他们是陌生人,并且 和 。翻转后,他们是、、、、、谁是朋友。 (如果 和 也是陌生人,那么翻转会立即关闭两个间隙。) 和 的友谊,以及 和 的友谊,像 X 一样交叉。让我们将这样的一对友谊称为交叉:一个从 到 ,一个从 到客人,顺时针方向。每次交叉都会发生翻转。下面的交互图在聚会上运行之前的算法,从恰好有四个间隙的座位排列开始,然后翻转,直到没有间隙为止。 A B C D E F G H I J u v x y u v x y u v x y A D E H C B G F I J 4 个间隙 4 个间隙 3 个间隙 1 个间隙 无间隙 算法如下:让每个人以任意顺序就座,而一些陌生人 u 和 v 并排坐着,v 正好位于 u 的顺时针方向:找到 u 的一个朋友 x,他坐在 v 的朋友 y 的逆时针位置 将每个人的顺序从 v 颠倒到 x 所以 wh
这篇文章对您有帮助吗?
订阅66必读
每日精选科技资讯,直达你的邮箱