組合數(shù)學(xué)淺析

摘要:該文介紹了組合數(shù)學(xué)的定義及研究?jī)?nèi)容，組合數(shù)學(xué)的經(jīng)典問(wèn)題及組合數(shù)學(xué)在日常生產(chǎn)、生活和計(jì)算機(jī)科學(xué)中的廣泛應(yīng)用和重要意義。

關(guān)鍵詞:組合數(shù)學(xué);四色問(wèn)題;郵差問(wèn)題

中圖分類(lèi)號(hào):O157 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1009-3044(2010)11-2801-02

Analysis of Combinatorial Mathematics

HU Qin

(Baiyun Middle School in ZongYang Country， Anqing 246728， China)

Abstract: The paper introduces definition， research content and classical problems of combinatorial mathematics. In addition， the paper introduces extensive use and significance of combinatorial mathematics in daily production， daily life and computer science.

Key words: combinatorial mathematics; four color problem; postman problem

組合數(shù)學(xué)，又稱(chēng)為離散數(shù)學(xué)，是一門(mén)研究離散對(duì)象的科學(xué)[1]。組合數(shù)學(xué)是計(jì)算機(jī)出現(xiàn)以后迅速發(fā)展起來(lái)的一門(mén)數(shù)學(xué)分支，隨著計(jì)算機(jī)科學(xué)的日益發(fā)展，組合數(shù)學(xué)的重要性也日漸凸顯[2]。電子計(jì)算機(jī)處理的信息，都是僅用“0”與“1”兩個(gè)簡(jiǎn)單數(shù)字表示的信息，或者是用這種數(shù)字進(jìn)行了編碼的信息。所以離散對(duì)象的處理就成了計(jì)算機(jī)科學(xué)的核心，而組合數(shù)學(xué)是一門(mén)研究離散對(duì)象的科學(xué)。現(xiàn)代數(shù)學(xué)的研究?jī)?nèi)容主要包括兩個(gè)方面:一方面類(lèi)是研究連續(xù)對(duì)象的，如分析、代數(shù)等，另一方面就是研究離散對(duì)象的組合數(shù)學(xué)。

組合數(shù)學(xué)主要研究符合一定條件的組態(tài)對(duì)象、計(jì)數(shù)及構(gòu)造等方面的問(wèn)題[2-4]。離散構(gòu)形問(wèn)題是組合數(shù)學(xué)的主要研究?jī)?nèi)容，主要包括:①構(gòu)形構(gòu)形的存在性問(wèn)題;②構(gòu)形的構(gòu)造性問(wèn)題;③構(gòu)形的計(jì)數(shù)問(wèn)題;④構(gòu)形的最優(yōu)化問(wèn)題。

1666年，《組合藝術(shù)》一書(shū)是組合數(shù)學(xué)發(fā)展史上的里程碑，在此后的三百多年里，組合數(shù)學(xué)取得了快速發(fā)展，特別是20世紀(jì)40年代以來(lái)，電子計(jì)算機(jī)的廣泛應(yīng)用對(duì)組合數(shù)學(xué)產(chǎn)生了巨大影響，組合數(shù)學(xué)在與計(jì)算機(jī)科學(xué)相結(jié)合中獲得了廣闊的發(fā)展空間，從而也為計(jì)算機(jī)科學(xué)奠定了理論基礎(chǔ)。組合數(shù)學(xué)不僅計(jì)算機(jī)技術(shù)中的網(wǎng)絡(luò)優(yōu)化、編碼和密碼學(xué)中有重要的應(yīng)用價(jià)值，在企業(yè)管理、交通規(guī)劃、金融分析等領(lǐng)域都有重要的應(yīng)用[5]。在21世紀(jì)，組合數(shù)學(xué)將會(huì)緊密的伴隨著計(jì)算機(jī)科學(xué)向前發(fā)展，組合論技巧將會(huì)計(jì)算機(jī)化，進(jìn)而成為各種解算機(jī)的重要組成部分。

1 組合數(shù)學(xué)中經(jīng)典問(wèn)題

組合數(shù)學(xué)中的經(jīng)典問(wèn)題[6-9]主要包括:①棋盤(pán)完美覆蓋;②切割立方體;③幻方;④四色問(wèn)題;⑤36軍官問(wèn)題;⑥最短路徑;⑦NIM取子問(wèn)題;⑧羊狼菜過(guò)河問(wèn)題;⑨中國(guó)郵遞員問(wèn)題;⑩穩(wěn)定婚姻問(wèn)題。以下重點(diǎn)介紹四色問(wèn)題和中國(guó)郵遞員問(wèn)題。

1.1 四色問(wèn)題

四色問(wèn)題即使用四種不同的顏色對(duì)世界地圖著色，要求相鄰國(guó)家的顏色相異。采用數(shù)學(xué)語(yǔ)言對(duì)本問(wèn)題進(jìn)行形式化描述如下:將平面任意地細(xì)分為不相重迭的區(qū)域，每一個(gè)區(qū)域總可以用1，2，3，4這4個(gè)數(shù)字之一來(lái)標(biāo)記，而不會(huì)使相鄰的兩個(gè)區(qū)域得到相同的數(shù)字。

一個(gè)多世紀(jì)以來(lái)，在四色問(wèn)題的研究證明過(guò)程中，由于對(duì)象問(wèn)題復(fù)雜且缺乏數(shù)學(xué)通常的解題規(guī)范，人工直接驗(yàn)證不可行。本世紀(jì)70年代，電子計(jì)算機(jī)的迅速發(fā)展和廣泛應(yīng)用使四色問(wèn)題的研究出現(xiàn)了轉(zhuǎn)機(jī)。美國(guó)伊利諾斯大學(xué)的阿佩爾、哈肯等人在研究了前人各種證明方法和思想的基礎(chǔ)后，從1972年起，開(kāi)始了用計(jì)算機(jī)證明四色問(wèn)題的研究工作。終于在1976年徹底解決了四色問(wèn)題，整個(gè)證明過(guò)程在計(jì)算機(jī)上花費(fèi)了1200個(gè)小時(shí)。地圖四色問(wèn)題是第一個(gè)主要由計(jì)算機(jī)完成證明的數(shù)學(xué)難題。科學(xué)家們?cè)谘芯亢徒鉀Q四色問(wèn)題的過(guò)程中，還由此產(chǎn)生不少新的數(shù)學(xué)理論，發(fā)展了很多數(shù)學(xué)計(jì)算方法，刺激了拓?fù)鋵W(xué)與圖論的發(fā)展

1.2 中國(guó)郵遞員問(wèn)題

一個(gè)郵遞員的工作是:按一定路線(xiàn)遞送他所負(fù)責(zé)的街區(qū)的各條街道的郵件，最后返回郵局，要求郵遞員必須走過(guò)他負(fù)責(zé)的街區(qū)的每一條街道至少一次，并希望選擇一條總路程最短的遞送路線(xiàn)。尋找這樣的一條最短遞送路線(xiàn)的問(wèn)題，在國(guó)際學(xué)術(shù)界稱(chēng)之為中國(guó)郵遞員問(wèn)題，因?yàn)樗紫仁怯芍袊?guó)數(shù)學(xué)家管梅谷教授在1962年首次提出并加以研究的。

1.2.1 歐拉回路

設(shè)G(V，E)為一個(gè)圖，圖G中一個(gè)回路，若它恰通過(guò)G中每條邊一次，則稱(chēng)該回路為歐拉(Euler)回路，并稱(chēng)圖G為歐拉圖。歐拉回路與哥尼斯堡7橋問(wèn)題相聯(lián)系的，在哥尼斯堡7橋問(wèn)題中，歐拉證明了不存在這樣的回路。在一個(gè)圖中，連接一個(gè)節(jié)點(diǎn)的邊數(shù)稱(chēng)為該節(jié)點(diǎn)的度數(shù)。對(duì)歐拉圖，有下列結(jié)果:

定理1對(duì)連通圖G(V，E)，其中V表示圖中的節(jié)點(diǎn)集，E表示邊集，則下列條件是相互等價(jià)的:①G是一個(gè)歐拉圖;②G的每一個(gè)節(jié)點(diǎn)的度數(shù)都是偶數(shù);③G的邊集合E可以分解為若干個(gè)回路的并。

證明 :⑴?圯⑵已知G為歐拉圖，則必存在一個(gè)歐拉回路。回路中的節(jié)點(diǎn)都是偶度數(shù)。⑵?圯⑶ 設(shè)G中每一個(gè)節(jié)點(diǎn)的度數(shù)均為偶數(shù)。若能找到一個(gè)回路C1使G=C1，則結(jié)論成立。否則，令G1=G\\C1，由C1上每個(gè)節(jié)點(diǎn)的度數(shù)均為偶數(shù)，則G1中的每個(gè)節(jié)點(diǎn)的度數(shù)亦均為偶數(shù)。于是在G1必存在另一個(gè)回路C2。令G2=G1\\C2，…。由于G為有限圖，上述過(guò)程經(jīng)過(guò)有限步，最后必得一個(gè)回路Cr使 Gr=Gr-1\\Cr上各節(jié)點(diǎn)的度數(shù)均為零，即Cr=Gr-1。這樣就得到G的一個(gè)分解 G=C1∪C2∪…∪Cr。⑶?圯⑴設(shè)G=C1∪C2∪…∪Cr，其中Ci(i=1，2，…，r)均為回路。由于G為連通圖，對(duì)任意回路Ci，必存在另一個(gè)回路Cj與之相連，即Ci與Cj存在共同的節(jié)點(diǎn)。現(xiàn)在我們從圖G的任意節(jié)點(diǎn)出發(fā)，沿著所在的回路走，每走到一個(gè)共同的節(jié)點(diǎn)處，就轉(zhuǎn)向另一個(gè)回路，…，這樣一直走下去就可走遍G的每條邊且只走過(guò)一次，最后回到原出發(fā)節(jié)點(diǎn)，即G為一個(gè)歐拉圖。

利用定理1去判斷一個(gè)連通圖是否為歐拉圖比較容易，但要找出歐拉回路，當(dāng)連通圖比較復(fù)雜時(shí)就不太容易了。下面介紹歐拉回路的求解。

1.2.2 歐拉回路的求解

循環(huán)的找到出發(fā)點(diǎn)。從某個(gè)節(jié)點(diǎn)開(kāi)始，然后查出一個(gè)從這個(gè)出發(fā)回到這個(gè)點(diǎn)的環(huán)路徑。這種方法保證每個(gè)邊都被遍歷。如果有某個(gè)點(diǎn)的邊沒(méi)有被遍歷就讓這個(gè)點(diǎn)為起點(diǎn)，這條邊為起始邊，把它和當(dāng)前的環(huán)銜接上。這樣直至所有的邊都被遍歷。這樣，整個(gè)圖就被連接到一起了。求解歐拉回路的弗羅萊算法算法步驟如下:

①任取起始點(diǎn)v0，v0→R;②設(shè)路R={e1(v0，vi1)，{e2(vi1，vi2)，…，{er(vir-1，vir)}已選出，則從E\\(e1，e2，…，er)中選出邊er+1，使er+1與vir相連，除非沒(méi)有其它選擇，Gr\\{er+1}仍應(yīng)為連通的。③重復(fù)步驟②，直至不能進(jìn)行下去為止。

定理2連通的有向圖存在歐拉回路的充分必要條件是對(duì)任意節(jié)點(diǎn)，進(jìn)入該節(jié)點(diǎn)邊數(shù)(進(jìn)數(shù))與離開(kāi)該點(diǎn)的邊數(shù)(出數(shù))相等。

1.2.3 郵差問(wèn)題求解

用圖論的述語(yǔ)，在一個(gè)連通的賦權(quán)圖G(V，E)中，要尋找一條回路，使該回路包含G中的每條邊至少一次，且該回路的權(quán)數(shù)最小。也就是說(shuō)要從包含G的每條邊的回路中找一條權(quán)數(shù)最小的回路。

如果G是歐拉圖，若圖中有歐拉回路，因?yàn)闅W拉回路通過(guò)所有的邊，因此任何一個(gè)歐拉回路即為此問(wèn)題的解，則很容易由1.2.2節(jié)中描述弗羅萊算法求出一個(gè)歐拉回路求出一個(gè)歐拉回路，但是若G不是歐拉圖，即存在奇度數(shù)的節(jié)點(diǎn)，則中國(guó)由遞員問(wèn)題的解決要困難得多。有興趣的讀者可以參考文獻(xiàn)[7]。

在現(xiàn)實(shí)生活中，很多問(wèn)題都可以轉(zhuǎn)化為中國(guó)郵遞員問(wèn)題，例如道路清掃時(shí)如何使開(kāi)空車(chē)的總時(shí)間最少的問(wèn)題等等。上面例題所用的求最優(yōu)郵路的方法叫“奇偶點(diǎn)圖上作業(yè)法”。

2 計(jì)算機(jī)科學(xué)與組合數(shù)學(xué)

隨著計(jì)算機(jī)技術(shù)的深入發(fā)展，特別是計(jì)算機(jī)網(wǎng)絡(luò)的廣泛使用，計(jì)算機(jī)的使用已經(jīng)深入到科學(xué)研究和人們?nèi)粘Ｉ畹母鱾€(gè)領(lǐng)域。計(jì)算機(jī)要向更加智能化的方向發(fā)展，其出路仍然是數(shù)學(xué)的算法和數(shù)學(xué)的機(jī)械化。算法研究是計(jì)算機(jī)科學(xué)的重要研究領(lǐng)域，組合數(shù)學(xué)家在20世紀(jì)70年代初建立的算法復(fù)雜性NP理論為計(jì)算機(jī)算法復(fù)雜性的研究提供了重要的理論基礎(chǔ)。組合數(shù)學(xué)是計(jì)算機(jī)產(chǎn)業(yè)的基礎(chǔ)，開(kāi)發(fā)高層次的軟件產(chǎn)品離不開(kāi)組合數(shù)學(xué)。

組合數(shù)學(xué)在國(guó)外早已成為十分重要的學(xué)科，甚至可以說(shuō)是計(jì)算機(jī)科學(xué)的基礎(chǔ)，當(dāng)今計(jì)算機(jī)科學(xué)界的權(quán)威人士很多都是研究組合數(shù)學(xué)出身的。美國(guó)和印度之所以能在軟件行業(yè)處于世界領(lǐng)先的地位，與這兩個(gè)國(guó)家在基礎(chǔ)數(shù)學(xué)，特別是組合數(shù)學(xué)方面的人才儲(chǔ)備分不開(kāi)的，但在國(guó)內(nèi)仍有一部人對(duì)組合數(shù)學(xué)的認(rèn)識(shí)不夠，認(rèn)為組合數(shù)學(xué)只是一門(mén)純粹的基礎(chǔ)學(xué)科，對(duì)經(jīng)濟(jì)發(fā)展實(shí)際意義不大，可實(shí)際情況是軟件產(chǎn)業(yè)、網(wǎng)絡(luò)算法和分析、信息壓縮、網(wǎng)絡(luò)安全、編碼技術(shù)、系統(tǒng)軟件都離不開(kāi)組合數(shù)學(xué)的理論和方法上的支持。以基礎(chǔ)數(shù)學(xué)為代表的基礎(chǔ)理論研究已成為我國(guó)軟件業(yè)發(fā)展的瓶頸，中國(guó)要想能成為一個(gè)軟件大國(guó)，就應(yīng)加強(qiáng)組合數(shù)學(xué)教學(xué)和人才培養(yǎng)等工作。

當(dāng)前，有識(shí)之士也已充分認(rèn)識(shí)到組合數(shù)學(xué)等基礎(chǔ)數(shù)學(xué)的重要性，南開(kāi)大學(xué)于1997 年成立了南開(kāi)大學(xué)組合數(shù)學(xué)中心，主要從事組合數(shù)學(xué)理論研究，如今已經(jīng)成為一個(gè)具有國(guó)際影響力的組合數(shù)學(xué)研究機(jī)構(gòu)[9]，并創(chuàng)辦了我國(guó)第一份組合數(shù)學(xué)國(guó)際刊物《組合年刊》。另外，清華大學(xué)、中國(guó)科技大學(xué)、同濟(jì)大學(xué)等重點(diǎn)大學(xué)也建立了研究組合數(shù)學(xué)的重點(diǎn)實(shí)驗(yàn)室。總之，近幾年來(lái)，我國(guó)的組合數(shù)學(xué)基礎(chǔ)研究工作受到各高校及廣大科學(xué)工作者越來(lái)越多的關(guān)注，特別是在高校學(xué)生間開(kāi)展的數(shù)學(xué)建模競(jìng)賽活動(dòng)，提高了學(xué)生用計(jì)算機(jī)技術(shù)解決實(shí)際問(wèn)題的能力，也大大刺激了學(xué)生對(duì)組合數(shù)學(xué)的求知需求，激發(fā)了學(xué)習(xí)組合數(shù)學(xué)的熱潮。

3 結(jié)論

隨著計(jì)算機(jī)的普及推廣，組合數(shù)學(xué)這門(mén)古老的學(xué)科煥發(fā)出蓬勃的生機(jī)。組合數(shù)學(xué)是一門(mén)研究?jī)?nèi)容豐富、應(yīng)用廣泛的學(xué)科，同時(shí)它也是一門(mén)講究方法，講究技巧的學(xué)科。組合數(shù)學(xué)的魅力在于一個(gè)組合數(shù)學(xué)問(wèn)題的能否得到完善的解決往往取決于能否找到巧妙的解法，計(jì)算機(jī)強(qiáng)大的計(jì)算能力為尋求組合數(shù)學(xué)問(wèn)題的巧妙解法提供了無(wú)限的可能，同時(shí)組合數(shù)學(xué)也反過(guò)來(lái)有效地推動(dòng)了計(jì)算機(jī)科學(xué)的發(fā)展。

參考文獻(xiàn):

[1] 陳永川.話(huà)說(shuō)組合數(shù)學(xué)[J].科學(xué)中國(guó)人，2003(5).

[2] 孫怡東.計(jì)數(shù)組合學(xué)中若干問(wèn)題的研究[D].大連理工大學(xué)，2006.

[3] 鄧明立.有限域思想的歷史演變[D].河北師范大學(xué)，2004.

[4] 侯慶虎.組合數(shù)學(xué)中的代數(shù)方法[D].南開(kāi)大學(xué)，2001.

[5] 左光紀(jì).組合數(shù)學(xué)的科學(xué)藝術(shù)表現(xiàn)[J].青海師專(zhuān)學(xué)報(bào)，2000(6).

[6] 王春香，李玲.《組合數(shù)學(xué)》教學(xué)指導(dǎo)[J].高等函授學(xué)報(bào):自然科學(xué)版，2003(6).

[7] 舒興明.利用Floyed-Hungary法求解中國(guó)郵路問(wèn)題[J].華南熱帶農(nóng)業(yè)大學(xué)學(xué)報(bào)，2003(9).

[8] 吳振奎，王全文.中國(guó)郵路問(wèn)題的一個(gè)解法[J].運(yùn)籌與管理，2004(3).

[9] 周聞.在奮進(jìn)中崛起——記南開(kāi)大學(xué)組合數(shù)學(xué)研究中心[J].中國(guó)基礎(chǔ)科學(xué)，2004(3).