长坂坡七进七出.doc

长坂坡七进七出小时候读三国演义，当读到第41回赵子龙在当阳长坂坡七进七出，冲杀曹营，如入无人之境的那段描写时，心情的那份激动，实在难以形容。对赵子龙的超群武艺和英雄气概，佩服得五体投地。时移世易，今天偶然重翻旧籍，想到科学技术发展到今天，在现代化的战争中，赵子龙这种“匹夫之勇”，大概已没有多大的实际意义了。不过，当年与小伙伴们争论的一个看来有些可笑的问题，却至今记忆犹新：赵子龙从曹营中七进七出，走的是同一条道路呢？还是不同的道路呢？或者有时走的是老路，有时又是杀开一条新路呢？刘备从荆州一路败退而来，仓皇逃往夏口，一定是一路且战且走。赵子龙从曹军中七进七出，一方面为了赶上不断往前面溃逃的大部队，一方面又要尽量避开随后追杀过来的曹军，大概不可能走重复的路线吧。换句话说，杀进出的路随后即被曹军追兵堵死，必须从曹军疏于防备或来不及组织阻击的另一条路杀出来；下一次又必须从另外一条薄弱的路线杀进去不妨设想，赵子龙每次杀进杀出，都经过不同的路线，大概不会十分错。如图48所示。谁都不难理解，如果赵子龙每次进出都不走重复路线，“七进七出”就要走14条不同的路线。如果再来个“八进八出”、“九进九出”，那就要分别走16条或者18条不同的路线。总之，不管几进几出，如果不走相同的路线，那么所走路线条数恰好是进出次数的两倍，总是一个偶数。虽然这个简单的道理谁都知道，但是谁能设想，它却涉及到数学史上一个著名的数学问题的解决，并导致一个新的数学分支的诞生。这个著名的数学问题就是“七桥问题”。在18世纪，东普鲁士有一个叫做哥尼斯堡的城市(今属东波罗的海的立陶宛共和国)，一条名叫帕瑞格的大河流经这个城市，河中有两个小岛，把全城分割成4块互不相连的陆地。人们在河上架了7座桥把4块陆地像图49所示的那样联系起来。当时哥尼斯堡的许多市民都热衷于解决如下的一个难题：一个散步者能否从某一块陆地出发，不重复地走过每座桥一次，最后回到原来的出发点。这就是有名的“哥尼斯堡七桥问题。”这个问题似乎不难解决，试验起来也比较容易，不论年纪大小，不分文化高低，谁都可以动手试一试。所以吸引了许多人都来试验，但是谁也没有成功。于是有人写信向当时著名的数学家欧拉(Eu-ler，17071783)求教。欧拉毕竟是一位伟大的数学家，他收到求教信以后，并没有去重复人们已经多次失败了的试验，而是产生了一种直觉的猜想：许多人千百次的失败，是否意味着这样的走法根本就不存在呢？于是欧拉把这个问题进行数学抽象，把它转化为图50那样的网络图。他用A、B、C、D4个点表示4块陆地，用两点间的一条联线表示连接这两块陆地之间的一座桥，就得到一个由一些点和点之间的一些联线所组成的图形，这样的图形称为网络图。图50就是表示“七桥问题”的一个网络图。“七桥问题”能否解决实际上就转化为象图63那样的网络图能否“一笔画”的问题。什么叫“一笔画”呢？就是笔不准离开纸，每条线只许画一次，不重复地画出整个图形。1736年欧拉终于严格证明了像图50那样的网络图是不可能“一笔画”的。从而也就证明了“七桥问题”所要求的那种走法是不存在的。为什么像图50那样的网络图不能一笔画呢？我们从更广泛的意义上来回答这个问题。一个网络图如果从它的任何一个顶点出发，沿着网络图的线路可以到达任一个其它顶点，则称这个网络图是连通的，否则称为不连通的。在图51中，像A、B那样的顶点，它与奇数条相联(A与3条线相联，B与1条线相联)，称为奇点；而像C、D那样的顶点，它与偶数条线相联(C点与4条线相联，D点与2条线相联)，则称为偶点。不连通的网络图当然不可能一笔画，对于连通的网络图，网络理论断言：一个连通的网络图如果它的奇点不多于两个才可以一笔画，否则就不可以一笔画(起点与终点不要求一定重合)。这个结论的证明十分简单：如果一个图形可以一笔画，除了画笔的起点和终点之外，中间经过的任何一个点(例如图52中的G点)，当画笔沿某条路线到达这点之后，由于它不是终点，必定还要沿另一条新的路线离去，一进一出，两两配对，只有对偶点才有可能。奇点是不能作为中间点的，因为奇点与奇数条线相联，所以要么进入这点的线比离开这点的线多一条，要么离去这点的线比进入这点的线多一条。所以图中的奇点在一笔画时只能作为起点和终点。但一笔画只有一个起点和一个终点，最多能有两个奇点。所以当一个网络图中的奇点多于两个时，就一定不能一笔画出。如图52那个网络图，只有A、B两个奇点，所以一定可以一笔画出，不过A与B一定要作为起点和终点。一种可能的画法是ABCDEFGHIGB。再看“七桥问题”的网络图50，在那个图中，A、B、D三点都与3条线相联，B与5条线相联，它们都是奇点，即图50中有4个奇点，所以是不能一笔画出的。换句话说，“七桥问题”所要求的那种走法是不存在的。那么一个不能一笔画出的网络图，究竟要用多少笔才能画出呢？又用什么办法去判别它呢？这个问题很简单。我们以“七桥问题”的网络图为例，任取两个奇点，例如A与C，在它们之间加一条线，这两个点就都变成了偶点，图53便可一笔画出。当画笔经过补加的虚线时，事实上画笔已经间断一次，所以图50只要两笔可以画出。一般地，一个网络图中如果有2k+1或2k+2个奇点，则用k笔可以画成。曾为哥尼斯堡居民深感遗憾的人们已经可以感到欣慰了。因为1935年(当时这个城市属于苏联，称为加里宁格勒)，人们已在帕瑞格河上架起了第八座桥，所以现在市民们考虑的已不再是“哥尼斯堡七桥问题”，而是“加里宁格勒八桥问题了。你能找到一条散步的路线，从一块陆地出发走遍8座桥，而不重蹈旧迹吗？现在我们来讨论另一种有趣的网络图。图55叫做哈密尔顿环行图。它是英国数学家哈密尔顿(Hamilton，18051865)提出来的。图中每个顶点代表一个城市，点与点之间的联线代表一条道路，一个旅行者可以从任何一个城市出发走遍所有的城市再回到原处(不要求走遍所有的道路)，却不走重复的路线，也不经过除了出发点城市以外的其他城市两次，具有这种性质的图就称为哈密尔顿环行图。请你给图55设计一条环行线路。并不是所有的图都能成为哈密尔顿环行图，例如下面的图56和图57就不是哈密尔顿环行图：我们来证明图56不是哈密尔顿环行图。因为在图56中恰好有8个奇点和6个偶点，不难看到，不管你走什么路线，从偶点只能走到奇点，从奇点只能走到偶点。如果存在一条哈密尔顿环行路线，奇点和偶点必然相间地经过，如果最初从奇点出发，则在整个图中，奇点恰好比偶点多1个；从偶点出发，