哥尼斯堡七桥问题

已解决，1736年组合数学与离散数学

问题陈述

哥尼斯堡市(今加里宁格勒)建在普雷格尔河两岸及两座小岛上,由七座桥连接。能否在城中散步,恰好经过每座桥一次,且不重复走过任何一座桥?

欧拉最初的论证是一个关于奇偶性的数论式论证,还不是用现代图论语言写成的证明——当时“图”“顶点”“边”这些概念本身尚未出现。

欧拉的洞见——只有顶点的度数重要,几何布局无关紧要——成为图论的种子。他发现的一般判据,如今称为欧拉回路定理:一个连通图存在经过每条边恰好一次的闭合路径,当且仅当每个顶点的度数都是偶数;而存在经过每条边恰好一次的开放路径,即欧拉路径,当且仅当恰好有零个或两个奇数度顶点。

参考文献