## 开端

The problem, which I am told is widely known, is as follows: in K¨onigsberg in Prussia, there is an island A, called the Kneiphof ; the river which surrounds it is divided into two branches, as can be seen in Fig. [1.2], and these branches are crossed by seven bridges, a, b , c , d , e , f and g. Concerning these bridges, it was asked whether anyone could arrange a route in such a way that he would cross each bridge once and only once. I was told that some people asserted that this was impossible, while others were in doubt: but nobody would actually assert that it could be done. From this, I have formulated the general problem: whatever be the arrangement and division of the river into branches, and however many bridges there be, can one ﬁnd out whether or not it is possible to cross each bridge exactly once?

## 证明它！

#### 方法

• 不适用于更复杂的情况（兄弟，真的遍历不完的
• 不能抽象为理论！！（这很重要，琐碎变为伟大的关键
• 会浪费注意力在那些根本不可能成为答案的路径上

#### 问题表示方法

AB中第一个字母指的是旅行者离开的区域，第二个字母指的是他过桥后到达的区域。

#### 怎样才会存在？

• 首先用字母 A、B、C 等表示被水隔开的各个区域。

• 然后，取桥的总数加上一，把结果写在下面的工作上面。

• 第三，把字母A、B、C等写在一列中，并在每一个旁边写下通向它的桥梁的数量。

• 第四，用星号表示那些有偶数桥的字母。

• 第五，在每一个偶数旁边写下一半的数字，在每一个奇数旁边写下一半的数字加一。

• 第六，把这些数字加起来，如果这个总和小于或等于上面写的数字，也就是桥的数量加上一，就得出结论，满足要求的旅程是可能的。

必须记住，如果总和比上面写的数字小一，那么旅程必须从标有星号的区域之一开始，如果总和相等，则必须从未标有星号的区域开始。

柯尼斯堡镇七桥问题的求解：

七座桥，$7+1=8$

地区 相邻桥数 通过地区次数
A 5 3
B 3 2
C 3 3
D 3 2

显然 $3+2+2+2>8$ 不满足题设

16
A* 8 4
B* 4 2
C* 4 2
D* 3 2
E 5 3
F* 6 3
16

EaFbBcFdAeFfCgAhCiDkAmEnApBoEiD

### 找到路径！

I do not therefore think it worthwhile to give any further details concerning the ﬁnding of the routes.