柯尼斯堡大桥和图表的诞生
柯尼斯堡 (Königsberg),位于 1652,拥有普雷格尔河 (Pregel) 及其岛屿。你可以数一下桥梁的数量。梅里安-埃尔本·公共领域 普雷格尔河穿过柯尼斯堡市(今俄罗斯加里宁格勒),形成两条河流 岛屿。七座桥梁连接城市的四个区域。居民们好奇这是否可行 每座桥步行一次。
在阅读答案之前,请自己尝试一下:
选择从哪里开始,然后单击桥梁来跨越它们。你能通过7吗? Ative o JavaScript para ver esta figura interativa.
欧拉意识到街道的形状、岛屿的大小和桥梁的长度并不重要。 重要的是哪些区域链接到哪些区域。他用点画取代了地图 (区域)和线路(桥梁)。今天,这被称为图表:
欧拉论文(1736)的原始图:区域为 A、B、C 和 D,桥为 a、b、c、d、e、f 和 g。莱昂哈德·欧拉·公共领域 今天我们画同样的问题是这样的:
柯尼斯堡图。红色数字表示到达每个区域的桥梁数量。 Ative o JavaScript para ver esta figura interativa.
现在扣分。在游览中,每次经过一个区域(没有开始或结束 它),使用一座桥进入,另一座桥退出。然后来自中间区域的桥梁到来 总是成对:到达它的桥的数量必须偶数。仅起始区域和 到达阶段可能有奇数个桥梁。
结论:只有在至多两个区域拥有奇数座桥梁的情况下,游览才有可能。
在柯尼斯堡计数:
地区 桥梁 偶数还是奇数? 克奈夫岛 5 (a, b, c, d, e) 奇怪的 北岸 3 (a, b, f) 奇怪的 南岸 3 (c, d, g) 奇怪的 洛姆塞岛 3 (e, f, g) 奇怪的 有四个个奇怪的区域,所以游览是不可能的。欧拉在 1735 中提出了这个论点, 它被认为是图论的第一个结果,这个领域今天已经落后了 GPS、社交网络和送货路线。