长坂坡七进七出
小时候读《三国演义》，当读到第41回赵子龙在当阳长坂坡七进七出，冲杀曹营，如入无人之境的那段描写时，心情的那份激动，实在难以形容。对赵子龙的超群武艺和英雄气概，佩服得五体投地。时移世易，今天偶然重翻旧籍，想到科学技术发展到今天，在现代化的战争中，赵子龙这种“匹夫之勇”，大概已没有多大的实际意义了。不过，当年与小伙伴们争论的一个看来有些可笑的问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
，却至今记忆犹新：赵子龙从曹营中七进七出，走的是同一条道路呢？还是不同的道路呢？或者有时走的是老路，有时又是杀开一条新路呢？
刘备从荆州一路败退而来，仓皇逃往夏口，一定是一路且战且走。赵子龙从曹军中七进七出，一方面为了赶上不断往前面溃逃的大部队，一方面又要尽量避开随后追杀过来的曹军，大概不可能走重复的路线吧。换句话说，杀进出的路随后即被曹军追兵堵死，必须从曹军疏于防备或来不及组织阻击的另一条路杀出来；下一次又必须从另外一条薄弱的路线杀进去……不妨设想，赵子龙每次杀进杀出，都经过不同的路线，大概不会十分错。如图48所示。
谁都不难理解，如果赵子龙每次进出都不走重复路线，“七进七出”就要走14条不同的路线。如果再来个“八进八出”、“九进九出”，那就要分别走16条或者18条不同的路线。总之，不管几进几出，如果不走相同的路线，那么所走路线条数恰好是进出次数的两倍，总是一个偶数。
虽然这个简单的道理谁都知道，但是谁能设想，它却涉及到数学史上一个著名的数学问题的解决，并导致一个新的数学分支的诞生。这个著名的数学问题就是“七桥问题”。
在18世纪，东普鲁士有一个叫做哥尼斯堡的城市(今属东波罗的海的立陶宛共和国)，一条名叫帕瑞格的大河流经这个城市，河中有两个小岛，把全城分割成4块互不相连的陆地。人们在河上架了7座桥把4块陆地像图49所示的那样联系起来。
当时哥尼斯堡的许多市民都热衷于解决如下的一个难题：
一个散步者能否从某一块陆地出发，不重复地走过每座桥一次，最后回到原来的出发点。
这就是有名的“哥尼斯堡七桥问题。”
这个问题似乎不难解决，试验起来也比较容易，不论年纪大小，不分文化高低，谁都可以动手试一试。所以吸引了许多人都来试验，但是谁也没有成功。于是有人写信向当时著名的数学家欧拉(Eu-ler，1707～1783)求教。欧拉毕竟是一位伟大的数学家，他收到求教信以后，并没有去重复人们已经多次失败了的试验，而是产生了一种直觉的猜想：许多人千百次的失败，是否意味着这样的走法根本就不存在呢？于是欧拉把这个问题进行数学抽象，把它转化为图50那样的网络图。他用A、B、C、D4个点
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示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的分析留给读者。勤劳的蜜蜂有糖吃
欧拉为了解决七桥问题而建立了网络理论这一重要的数学分支，今天它的理论及其应用都已经得到极大的发展，它在工程管理、信息传播、交通运输、程序设计等领域中都有十分出色的应用。
浙公网安备 33021202002483