长坂坡七进七出.doc

长坂坡七进七出小时候读《三国演义》 ，当读到第 41 回赵子龙在当阳长坂坡七进七出，冲杀曹营，如入无人之境的那段描写时，心情的那份激动，实在难以形容对赵子龙的超群武艺和英雄气概，佩服得五体投地时移世易，今天偶然重翻旧籍，想到科学技术发展到今天，在现代化的战争中，赵子龙这种“匹夫之勇” ，大概已没有多大的实际意义了不过，当年与小伙伴们争论的一个看来有些可笑的问题，却至今记忆犹新：赵子龙从曹营中七进七出，走的是同一条道路呢？还是不同的道路呢？或者有时走的是老路，有时又是杀开一条新路呢？刘备从荆州一路败退而来，仓皇逃往夏口，一定是一路且战且走赵子龙从曹军中七进七出，一方面为了赶上不断往前面溃逃的大部队，一方面又要尽量避开随后追杀过来的曹军，大概不可能走重复的路线吧换句话说，杀进出的路随后即被曹军追兵堵死，必须从曹军疏于防备或来不及组织阻击的另一条路杀出来；下一次又必须从另外一条薄弱的路线杀进去……不妨设想，赵子龙每次杀进杀出，都经过不同的路线，大概不会十分错如图48 所示谁都不难理解，如果赵子龙每次进出都不走重复路线， “七进七出”就要走 14 条不同的路线如果再来个“八进八出” 、“九进九出” ，那就要分别走 16 条或者 18 条不同的路线。

总之，不管几进几出，如果不走相同的路线，那么所走路线条数恰好是进出次数的两倍，总是一个偶数虽然这个简单的道理谁都知道，但是谁能设想，它却涉及到数学史上一个著名的数学问题的解决，并导致一个新的数学分支的诞生这个著名的数学问题就是“七桥问题” 在 18 世纪，东普鲁士有一个叫做哥尼斯堡的城市(今属东波罗的海的立陶宛共和国)，一条名叫帕瑞格的大河流经这个城市，河中有两个小岛，把全城分割成 4 块互不相连的陆地人们在河上架了 7 座桥把 4 块陆地像图 49 所示的那样联系起来当时哥尼斯堡的许多市民都热衷于解决如下的一个难题：一个散步者能否从某一块陆地出发，不重复地走过每座桥一次，最后回到原来的出发点这就是有名的“哥尼斯堡七桥问题 ”这个问题似乎不难解决，试验起来也比较容易，不论年纪大小，不分文化高低，谁都可以动手试一试所以吸引了许多人都来试验，但是谁也没有成功于是有人写信向当时著名的数学家欧拉(Eu-ler，1707～1783)求教欧拉毕竟是一位伟大的数学家，他收到求教信以后，并没有去重复人们已经多次失败了的试验，而是产生了一种直觉的猜想：许多人千百次的失败，是否意味着这样的走法根本就不存在呢？于是欧拉把这个问题进行数学抽象，把它转化为图 50 那样的网络图。

他用 A、B、C、D4 个点表示 4块陆地，用两点间的一条联线表示连接这两块陆地之间的一座桥，就得到一个由一些点和点之间的一些联线所组成的图形，这样的图形称为网络图图 50 就是表示“七桥问题”的一个网络图七桥问题”能否解决实际上就转化为象图 6—3 那样的网络图能否“一笔画”的问题什么叫“一笔画”呢？就是笔不准离开纸，每条线只许画一次，不重复地画出整个图形1736 年欧拉终于严格证明了像图 50 那样的网络图是不可能“一笔画”的从而也就证明了“七桥问题”所要求的那种走法是不存在的　　为什么像图 50 那样的网络图不能一笔画呢？我们从更广泛的意义上来回答这个问题一个网络图如果从它的任何一个顶点出发，沿着网络图的线路可以到达任一个其它顶点，则称这个网络图是连通的，否则称为不连通的在图 51 中，像 A、B 那样的顶点，它与奇数条相联(A 与 3条线相联，B 与 1 条线相联)，称为奇点；而像 C、D 那样的顶点，它与偶数条线相联(C 点与 4 条线相联，D 点与 2 条线相联)，则称为偶点不连通的网络图当然不可能一笔画，对于连通的网络图，网络理论断言：一个连通的网络图如果它的奇点不多于两个才可以一笔画，否则就不可以一笔画(起点与终点不要求一定重合)。

这个结论的证明十分简单：如果一个图形可以一笔画，除了画笔的起点和终点之外，中间经过的任何一个点(例如图 52 中的G 点)，当画笔沿某条路线到达这点之后，由于它不是终点，必定还要沿另一条新的路线离去，一进一出，两两配对，只有对偶点才有可能奇点是不能作为中间点的，因为奇点与奇数条线相联，所以要么进入这点的线比离开这点的线多一条，要么离去这点的线比进入这点的线多一条所以图中的奇点在一笔画时只能作为起点和终点但一笔画只有一个起点和一个终点，最多能有两个奇点所以当一个网络图中的奇点多于两个时，就一定不能一笔画出　　如图 52 那个网络图，只有 A、B 两个奇点，所以一定可以一笔画出，不过 A 与 B 一定要作为起点和终点一种可能的画法是A—B—C—D—E—F—G—H—I—G—B再看“七桥问题”的网络图 50，在那个图中，A、B、D 三点都与 3 条线相联，B 与 5 条线相联，它们都是奇点，即图 50 中有 4 个奇点，所以是不能一笔画出的换句话说， “七桥问题”所要求的那种走法是不存在的那么一个不能一笔画出的网络图，究竟要用多少笔才能画出呢？又用什么办法去判别它呢？这个问题很简单我们以“七桥问题”的网络图为例，任取两个奇点，例如 A 与 C，在它们之间加一条线，这两个点就都变成了偶点，图 53 便可一笔画出。

当画笔经过补加的虚线时，事实上画笔已经间断一次，所以图 50只要两笔可以画出一般地，一个网络图中如果有 2k+1 或 2k+2 个奇点，则用 k笔可以画成曾为哥尼斯堡居民深感遗憾的人们已经可以感到欣慰了因为 1935 年(当时这个城市属于苏联，称为加里宁格勒)，人们已在帕瑞格河上架起了第八座桥，所以现在市民们考虑的已不再是“哥尼斯堡七桥问题” ，而是“加里宁格勒八桥问题了你能找到一条散步的路线，从一块陆地出发走遍 8 座桥，而不重蹈旧迹吗？　　现在我们来讨论另一种有趣的网络图图 55 叫做哈密尔顿环行图它是英国数学家哈密尔顿(Hamilton，1805～1865)提出来的图中每个顶点代表一个城市，点与点之间的联线代表一条道路，一个旅行者可以从任何一个城市出发走遍所有的城市再回到原处(不要求走遍所有的道路)，却不走重复的路线，也不经过除了出发点城市以外的其他城市两次，具有这种性质的图就称为哈密尔顿环行图请你给图 55 设计一条环行线路并不是所有的图都能成为哈密尔顿环行图，例如下面的图56 和图 57 就不是哈密尔顿环行图：我们来证明图 56 不是哈密尔顿环行图因为在图 56 中恰好有 8 个奇点和 6 个偶点，不难看到，不管你走什么路线，从偶点只能走到奇点，从奇点只能走到偶点。

如果存在一条哈密尔顿环行路线，奇点和偶点必然相间地经过，如果最初从奇点出发，则在整个图中，奇点恰好比偶点多 1 个；从偶点出发，则偶点比奇点多 1 个但图 56 中奇点比偶点多 2 个，所以图 56 不可能是哈密尔顿环行图我们把对图 57 的分析留给读者欧拉为了解决七桥问题而建立了网络理论这一重要的数学分支，今天它的理论及其应用都已经得到极大的发展，它在工程管理、信息传播、交通运输、程序设计等领域中都有十分出色的应用。