長(zhǎng)坂坡七進(jìn)七出

1、長(zhǎng)坂坡七進(jìn)七出小時(shí)候讀三國(guó)演義，當(dāng)讀到第41回趙子龍?jiān)诋?dāng)陽(yáng)長(zhǎng)坂坡七進(jìn)七出，沖殺曹營(yíng)，如入無(wú)人之境的那段描寫時(shí)，心情的那份激動(dòng)，實(shí)在難以形容對(duì)趙子龍的超群武藝和英雄氣概，佩服得五體投地時(shí)移世易，今天偶然重翻舊籍，想到科學(xué)技術(shù)發(fā)展到今天，在現(xiàn)代化的戰(zhàn)爭(zhēng)中，趙子龍這種“匹夫之勇”，大概已沒(méi)有多大的實(shí)際意義了不過(guò)，當(dāng)年與小伙伴們爭(zhēng)論的一個(gè)看來(lái)有些可笑的問(wèn)題，卻至今記憶猶新：趙子龍從曹營(yíng)中七進(jìn)七出，走的是同一條道路呢？還是不同的道路呢？或者有時(shí)走的是老路，有時(shí)又是殺開(kāi)一條新路呢？劉備從荊州一路敗退而來(lái)，倉(cāng)皇逃往夏口，一定是一路且戰(zhàn)且走趙子龍從曹軍中七進(jìn)七出，一方面為了趕上不斷往前面潰逃的大部隊(duì)，一方面又

2、要盡量避開(kāi)隨后追殺過(guò)來(lái)的曹軍，大概不可能走重復(fù)的路線吧換句話說(shuō)，殺進(jìn)出的路隨后即被曹軍追兵堵死，必須從曹軍疏于防備或來(lái)不及組織阻擊的另一條路殺出來(lái)；下一次又必須從另外一條薄弱的路線殺進(jìn)去不妨設(shè)想，趙子龍每次殺進(jìn)殺出，都經(jīng)過(guò)不同的路線，大概不會(huì)十分錯(cuò)如圖1所示誰(shuí)都不難理解，如果趙子龍每次進(jìn)出都不走重復(fù)路線，“七進(jìn)七出”就要走14條不同的路線如果再來(lái)個(gè)“八進(jìn)八出”、“九進(jìn)九出”，那就要分別走16條或者18條不同的路線總之，不管幾進(jìn)幾出，如果不走相同的路線，那么所走路線條數(shù)恰好是進(jìn)出次數(shù)的兩倍，總是一個(gè)偶數(shù)雖然這個(gè)簡(jiǎn)單的道理誰(shuí)都知道，但是誰(shuí)能設(shè)想，它卻涉及到數(shù)學(xué)史上一個(gè)著名的數(shù)學(xué)問(wèn)題的解決，并導(dǎo)致一

3、個(gè)新的數(shù)學(xué)分支的誕生這個(gè)著名的數(shù)學(xué)問(wèn)題就是“七橋問(wèn)題”在18世紀(jì)，東普魯士有一個(gè)叫做哥尼斯堡的城市(今屬東波羅的海的立陶宛共和國(guó))，一條名叫帕瑞格的大河流經(jīng)這個(gè)城市，河中有兩個(gè)小島，把全城分割成4塊互不相連的陸地人們?cè)诤由霞芰?座橋把4塊陸地像圖2所示的那樣聯(lián)系起來(lái)當(dāng)時(shí)哥尼斯堡的許多市民都熱衷于解決下面的一個(gè)難題：一個(gè)散步者能否從某一塊陸地出發(fā)，不重復(fù)地走過(guò)每座橋一次，最后回到原來(lái)的出發(fā)點(diǎn)這就是有名的“哥尼斯堡七橋問(wèn)題”這個(gè)問(wèn)題似乎不難解決，試驗(yàn)起來(lái)也比較容易，不論年紀(jì)大小，不分文化高低，誰(shuí)都可以動(dòng)手試一試所以吸引了許多人都來(lái)試驗(yàn)，但是誰(shuí)也沒(méi)有成功于是有人寫信向當(dāng)時(shí)著名的數(shù)學(xué)家歐拉(Eu-le

4、r，17071783)求教歐拉畢竟是一位偉大的數(shù)學(xué)家，他收到求教信以后，并沒(méi)有去重復(fù)人們已經(jīng)多次失敗了的試驗(yàn)，而是產(chǎn)生了一種直覺(jué)的猜想：許多人千百次的失敗，是否意味著這樣的走法根本就不存在呢？于是歐拉把這個(gè)問(wèn)題進(jìn)行數(shù)學(xué)抽象，把它轉(zhuǎn)化為圖3那樣的網(wǎng)絡(luò)圖他用A、B、C、D4個(gè)點(diǎn)表示4塊陸地，用兩點(diǎn)間的一條聯(lián)線表示連接這兩塊陸地之間的一座橋，就得到一個(gè)由一些點(diǎn)和點(diǎn)之間的一些聯(lián)線所組成的圖形，這樣的圖形稱為網(wǎng)絡(luò)圖圖3就是表示“七橋問(wèn)題”的一個(gè)網(wǎng)絡(luò)圖“七橋問(wèn)題”能否解決實(shí)際上就轉(zhuǎn)化為象圖3那樣的網(wǎng)絡(luò)圖能否“一筆畫”的問(wèn)題什么叫“一筆畫”呢？就是筆不準(zhǔn)離開(kāi)紙，每條線只許畫一次，不重復(fù)地畫出整個(gè)圖形1736

5、年歐拉終于嚴(yán)格證明了像圖3那樣的網(wǎng)絡(luò)圖是不可能“一筆畫”的從而也就證明了“七橋問(wèn)題”所要求的那種走法是不存在的為什么像圖3那樣的網(wǎng)絡(luò)圖不能一筆畫呢？我們從更廣泛的意義上來(lái)回答這個(gè)問(wèn)題一個(gè)網(wǎng)絡(luò)圖如果從它的任何一個(gè)頂點(diǎn)出發(fā)，沿著網(wǎng)絡(luò)圖的線路可以到達(dá)任一個(gè)其它頂點(diǎn)，則稱這個(gè)網(wǎng)絡(luò)圖是連通的，否則稱為不連通的在圖4中，像A、B那樣的頂點(diǎn)，它與奇數(shù)條相聯(lián)(A與3條線相聯(lián)，B與1條線相聯(lián))，稱為奇點(diǎn)；而像C、D那樣的頂點(diǎn)，它與偶數(shù)條線相聯(lián)(C點(diǎn)與4條線相聯(lián)，D點(diǎn)與2條線相聯(lián))，則稱為偶點(diǎn)不連通的網(wǎng)絡(luò)圖當(dāng)然不可能一筆畫，對(duì)于連通的網(wǎng)絡(luò)圖，網(wǎng)絡(luò)理論斷言：一個(gè)連通的網(wǎng)絡(luò)圖如果它的奇點(diǎn)不多于兩個(gè)才可以一筆畫，否則就

6、不可以一筆畫（起點(diǎn)與終點(diǎn)不要求一定重合）這個(gè)結(jié)論的證明十分簡(jiǎn)單：如果一個(gè)圖形可以一筆畫，除了畫筆的起點(diǎn)和終點(diǎn)之外，中間經(jīng)過(guò)的任何一個(gè)點(diǎn)(例如圖5中的G點(diǎn))，當(dāng)畫筆沿某條路線到達(dá)這點(diǎn)之后，由于它不是終點(diǎn)，必定還要沿另一條新的路線離去，一進(jìn)一出，兩兩配對(duì)，只有對(duì)偶點(diǎn)才有可能奇點(diǎn)是不能作為中間點(diǎn)的，因?yàn)槠纥c(diǎn)與奇數(shù)條線相聯(lián)，所以要么進(jìn)入這點(diǎn)的線比離開(kāi)這點(diǎn)的線多一條，要么離去這點(diǎn)的線比進(jìn)入這點(diǎn)的線多一條所以圖中的奇點(diǎn)在一筆畫時(shí)只能作為起點(diǎn)和終點(diǎn)但一筆畫只有一個(gè)起點(diǎn)和一個(gè)終點(diǎn)，最多能有兩個(gè)奇點(diǎn)所以當(dāng)一個(gè)網(wǎng)絡(luò)圖中的奇點(diǎn)多于兩個(gè)時(shí)，就一定不能一筆畫出如圖5那個(gè)網(wǎng)絡(luò)圖，只有A、B兩個(gè)奇點(diǎn)，所以一定可以一筆畫出，

7、不過(guò)A與B一定要作為起點(diǎn)和終點(diǎn)一種可能的畫法是ABCDEFGHIGB再看“七橋問(wèn)題”的網(wǎng)絡(luò)圖3，在那個(gè)圖中，A、B、D三點(diǎn)都與3條線相聯(lián)，B與5條線相聯(lián)，它們都是奇點(diǎn)，即圖3中有4個(gè)奇點(diǎn)，所以是不能一筆畫出的換句話說(shuō)，“七橋問(wèn)題”所要求的那種走法是不存在的那么一個(gè)不能一筆畫出的網(wǎng)絡(luò)圖，究竟要用多少筆才能畫出呢？又用什么辦法去判別它呢？這個(gè)問(wèn)題很簡(jiǎn)單我們以“七橋問(wèn)題”的網(wǎng)絡(luò)圖為例，任取兩個(gè)奇點(diǎn)，例如A與C，在它們之間加一條線，這兩個(gè)點(diǎn)就都變成了偶點(diǎn)，圖6便可一筆畫出當(dāng)畫筆經(jīng)過(guò)補(bǔ)加的虛線時(shí)，事實(shí)上畫筆已經(jīng)間斷一次，所以圖3只要兩筆可以畫出一般地，一個(gè)網(wǎng)絡(luò)圖中如果有2k+1或2k+2個(gè)奇點(diǎn)，則用k筆

8、可以畫成曾為哥尼斯堡居民深感遺憾的人們已經(jīng)可以感到欣慰了因?yàn)?935年(當(dāng)時(shí)這個(gè)城市屬于蘇聯(lián)，稱為加里寧格勒)，人們已在帕瑞格河上架起了第八座橋，所以現(xiàn)在市民們考慮的已不再是“哥尼斯堡七橋問(wèn)題”，而是“加里寧格勒八橋問(wèn)題”了你能找到一條散步的路線，從一塊陸地出發(fā)走遍8座橋，而不重蹈舊跡嗎？現(xiàn)在我們來(lái)討論另一種有趣的網(wǎng)絡(luò)圖圖8叫做哈密爾頓環(huán)行圖它是英國(guó)數(shù)學(xué)家哈密爾頓(Hamilton，18051865)提出來(lái)的圖中每個(gè)頂點(diǎn)代表一個(gè)城市，點(diǎn)與點(diǎn)之間的聯(lián)線代表一條道路，一個(gè)旅行者可以從任何一個(gè)城市出發(fā)走遍所有的城市再回到原處(不要求走遍所有的道路)，卻不走重復(fù)的路線，也不經(jīng)過(guò)除了出發(fā)點(diǎn)城市以外的其他城市兩次，具有這種性質(zhì)的圖就稱為哈密爾頓環(huán)行圖請(qǐng)你給圖8設(shè)計(jì)一條環(huán)行線路并不是所有的圖都能成為哈密爾頓環(huán)行圖，例如下面的圖9和圖10就不是哈密爾頓環(huán)行圖：我們來(lái)證明圖9不是哈密爾頓環(huán)行圖因?yàn)樵趫D9中恰好有8個(gè)奇點(diǎn)和6個(gè)偶點(diǎn)，不難看到，不管你走什么路線，從偶點(diǎn)只能走到奇點(diǎn)，從奇點(diǎn)只能走到偶點(diǎn)如果存在一條哈密爾頓環(huán)行路線，奇點(diǎn)和偶點(diǎn)必然相間地經(jīng)過(guò)，如果最初從奇點(diǎn)出發(fā)，則在整個(gè)圖中，奇點(diǎn)恰好比偶點(diǎn)多1個(gè)；從偶點(diǎn)