著名的哥尼斯堡七桥问题

欧洲有一座城市，叫哥尼斯堡。有一条河流经城区，河中有两个小岛， 共有七座桥将河的两岸和两个小岛联接起来。图中 A、B 表示两岸，C、D 表示两个小岛，数字 1 至 7 表示七座桥。

有人提出一个问题，能不能从某一地点出发（例如 D 点），通过七座桥各一次（即不能重复过桥），然后回到出发地（也就是 D 点）？这就是有名的哥尼斯堡七桥问题。

1736 年，数学家欧拉发表了一篇论文，将上面的问题用下图表示出来。同样地，图上 A、B 表示两岸，C、D 表示两个小岛，数字 1 至 7 表示七座桥。

图中的点叫顶点，用来表示具体的事物。图中的线叫做边，用来表示事物之间的某种关系。这种图不是按比例画出的，边长不代表真正距离或其他数量关系，顶点和边的位置也不与实际位置一一对应。这样，就可以将复杂的工程系统、运输系统、管理系统等等简化成图，来解决工程任务花费时间最少、运输距离最短、管理费用最省等最优化问题。

欧拉将哥尼斯堡七桥问题抽象成一个图，将上述过桥问题抽象成一笔画问题后，他证明，上图中的顶点都只与奇数条边相连接，因此不能将图一笔画成而不重复任一条边。假设第 4 条桥不是连接 C、D 小岛，而是连接 A、B 两岸，则可用下图表示。可以明显地看出各点均与偶数条边相连接，此图就可以不重复地一笔画成。

我们再看一下架设电话线的例子。在下图中，要在各单位之间架设电话线。电话线必须将它们连接，但为了节省线路，两单位之间也可以通过其他单位接通电话，例如乙村可以通过甲村、汽车站同学校接通电话，因此不必在乙村与学校间再架设一条电话线。这种简单形式的图就是“树”。

由于每两单位之间架线的长度不同，因此，实际上要求找到所架电线最短的“树”，按这“树”的样子架线，所花时间最少、也最省钱。

架设电话线的“树”