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

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

南開大學(xué)組合數(shù)學(xué)中心陳永川

2004年7月組合數(shù)學(xué)概述現(xiàn)代數(shù)學(xué)可以分為兩大類：一類是研究連續(xù)對象的，如分析、方程等；另一類就是研究離散對象的組合數(shù)學(xué)。計算機出現(xiàn)以后，由于離散對象的處理是計算機科學(xué)的核心，研究離散對象的組合數(shù)學(xué)得到迅猛發(fā)展。組合數(shù)學(xué)概述吳文俊院士指出，每個時代都有它特殊的要求，使得數(shù)學(xué)出現(xiàn)一個新的面貌，產(chǎn)生一些新的數(shù)學(xué)分支，組合數(shù)學(xué)這個新的分支也是在時代的要求下產(chǎn)生的。最近，吳文俊院士又指出，信息技術(shù)很可能會給數(shù)學(xué)本身帶來一場根本性的變革，而組合數(shù)學(xué)則將顯示出它的重要作用。Gian-CarloRota教授曾提出要向中國領(lǐng)導(dǎo)人呼吁，組合數(shù)學(xué)是計算機軟件產(chǎn)業(yè)的基礎(chǔ)，中國最終一定能成為一個軟件大國，但是要實現(xiàn)這個目標(biāo)的一個突破點就是發(fā)展組合數(shù)學(xué)。

組合數(shù)學(xué)的歷史傳說在公元前23世紀(jì)大禹治水的時候，在黃河支流洛水中，浮現(xiàn)出一個大烏龜，甲上背有9種花點的圖案，人們將圖案中的花點數(shù)了一下，競驚奇地發(fā)現(xiàn)9種花點數(shù)正巧是1—9這9個數(shù)，各數(shù)位置的排列也相當(dāng)奇妙，橫的3行、縱的3列以及兩對角線上各自的數(shù)字之和都為15。上圖為三階洛書幻方問題組合數(shù)學(xué)中有許多象幻方這樣精巧的結(jié)構(gòu)。1977年美國旅行者1號、2號宇宙飛船就帶上了幻方以作為人類智慧的信號。神農(nóng)幻方2200BC

11514412679810115133216

15世紀(jì)４階幻方阿基米德手稿上圖為一份用希臘文寫在羊皮紙上的阿基米德手稿副本,最近科學(xué)家借助現(xiàn)代科技手段初步破譯了古希臘數(shù)學(xué)家阿基米德的這篇論文,結(jié)論是這篇被稱作Stomachion的論文解決的是組合數(shù)學(xué)問題。阿基米德手稿在論文中阿基米德是在計算把14條不規(guī)則的紙帶拼成正方形一共能有多少種不同的拼法。這在現(xiàn)在被稱為tiling問題。當(dāng)今數(shù)學(xué)家借助計算機得出的答案是17152種拼法，這在當(dāng)時是相當(dāng)困難的。PeriodicTilings

Non-PeriodicTilingsPenroseTilings

SymmetricTilings

SymmetricTilings

賈憲三角中國最早的組合數(shù)學(xué)理論可追溯到宋朝時期的”賈憲三角”,后來被楊輝引用,所以普遍稱之為”楊輝三角”,這在西方是1654年由帕斯卡提出，但比中國晚了400多年。11，11，2，11，3，3，11，4，6，4，11，5，10，10，5，11，6，15，20，15，6，1七橋問題近代圖論的歷史可追溯到18世紀(jì)的七橋問題—穿過K?nigsberg城的七座橋，要求每座橋通過一次且僅通過一次。Euler1736年證明了不可能存在這樣的路線。Euler定理如果一個圖包含一條經(jīng)過每條邊恰好一次的閉途徑，則稱這個圖為歐拉圖。對任意的非空連通圖，若它是歐拉的,當(dāng)且僅當(dāng)它沒有奇度點。K?nigsberg橋?qū)?yīng)的圖36軍官問題

(歐拉1779)

TheGreatFrederic的閱兵難題-------歐拉的困惑

拉丁方陣:

正交拉丁方陣:Euler猜想不存在6階正交拉丁方不存在4k+2階正交拉丁方

現(xiàn)在的結(jié)論對任正整數(shù)n≠2,6，存在n階正交拉丁方組合數(shù)學(xué)的應(yīng)用組合數(shù)學(xué)不僅在基礎(chǔ)數(shù)學(xué)研究中具有極其重要的地位，在其它的學(xué)科如計算機科學(xué)、編碼和密碼學(xué)、物理、化學(xué)、生物等學(xué)科中，甚至在企業(yè)管理，交通規(guī)劃，戰(zhàn)爭指揮，金融分析，城市物流等領(lǐng)域均有重要應(yīng)用。組合數(shù)學(xué)的應(yīng)用著名的組合數(shù)學(xué)家ThomasTutte在組合數(shù)學(xué)界是泰斗級的大師。直到最近人們才知道，原來他對提前結(jié)束“二戰(zhàn)”有著突出貢獻。Tutte從德軍的兩條情報密碼出發(fā)，用組合數(shù)學(xué)的方法，重建了敵人的密碼機，確定了德軍密碼的內(nèi)部結(jié)構(gòu)，從而獲得了極為重要的情報。組合數(shù)學(xué)的應(yīng)用在美國有一家公司用組合數(shù)學(xué)的方法來提高企業(yè)管理的效益，這家公司辦得非常成功。在美國已有專門的公司用組合設(shè)計的方法開發(fā)軟件，來解決工業(yè)界中的試驗設(shè)計問題。德國一位著名組合數(shù)學(xué)家利用組合數(shù)學(xué)方法研究藥物結(jié)構(gòu)，為制藥公司節(jié)省了大量的費用，引起了制藥業(yè)的關(guān)注。

四色問題在日常生活中我們常?？梢杂龅浇M合數(shù)學(xué)的問題。比如一個著名的世界難題“四色猜想”

：一張地圖，用一種顏色對一個地區(qū)著色，那么一共只需要四種顏色就能保證每兩個相鄰的地區(qū)顏色不同。四色問題

1852年，剛從倫敦大學(xué)畢業(yè)的FrancisGuthrie提出了四色猜想。1878年著名的英國數(shù)學(xué)家Cayley向數(shù)學(xué)界征求解答。此后數(shù)學(xué)家Heawood花費了畢生的精力致力于四色研究，于1890年證明了五色定理（每個平面圖都是5頂點可著色的）。直到1976年6月，美國數(shù)學(xué)家K.Appel與W.Haken，在3臺不同的電子計算機上，用了1200小時，才終于完成了“四色猜想”的證明，從而使"四色猜想"成為了四色定理。

中國郵遞員問題1962年中國組合數(shù)學(xué)家管梅谷教授提出了著名的“中國郵遞員問題”。一個郵遞員從郵局出發(fā)，要走完他所管轄的每一條街道，然后返回郵局。那么如何選擇一條盡可能短的路線。中國郵遞員問題這個問題可以轉(zhuǎn)化為：給定一個具有非負(fù)權(quán)的賦權(quán)圖G，（1）用添加重復(fù)邊的方法求G的一個Euler賦權(quán)母圖G*，使得盡可能小。

（2）求G*的Euler環(huán)游。這個問題可以由Fleury算法和1973年著名組合數(shù)學(xué)家J.Edmonds和Johnson給出的一個好的算法解決。貨郎擔(dān)問題一個貨郎要去若干城鎮(zhèn)賣貨，然后回到出發(fā)地，給定各城鎮(zhèn)之間所需的旅行時間后，應(yīng)怎樣計劃他的路線，使他能去每個城鎮(zhèn)恰好一次而且總時間最短？貨郎擔(dān)問題用圖論的術(shù)語說，就是在一個賦權(quán)完全圖中，找出一個具有最小權(quán)的Hamilton圈（包含圖G的每個頂點的圈)。這個問題目前還沒有有效的算法。Hamilton問題是圖論的一個重要問題，圖論中的許多問題，包括四色問題、圖的因子問題，最終都與Hamilton問題有關(guān)。相識問題

1958年，美國的《數(shù)學(xué)月刊》上登載著這樣一個有趣的問題：“任何6個人的聚會，其中總會有3個人相互認(rèn)識，或3個人相互不認(rèn)識”。

用6個頂點表示6個人，用紅色連線表示兩者相識，用藍(lán)色連線表示兩者不相識。于是問題化為下述命題：相識問題對6個頂點的完全圖K6任意進行紅、藍(lán)兩邊著色，則圖中一定存在一個同色三角形。

Ramsey數(shù)推廣為一般問題：給定任意正整數(shù)a和b，總存在一個最小整數(shù)r(a,b)，使得r(a,b)個人中或者有a個人互相認(rèn)識，或者有b個人互相不認(rèn)識。稱r(a,b)為Ramsey數(shù)。Erd?s-Szekeres定理Ramsey定理是由Erd?s和Szekeres于1935年提出的。它是下述定理的一個推廣：定理（Erd?s和Szekeres）：若a,b∈N，n=ab+1，且x1,…,xn是任一n個實數(shù)的序列，則這個序列包含一個有a+1項的單調(diào)遞增（遞減）的子序列，或一個有b+1項的單調(diào)遞減（遞增）的子序列。HappyEnd問題對于n≥3，處于平面上一般位置（任意三個頂點不共線）的g(n)個頂點中，一定有n個頂點組成一個凸n邊形。

5頂點一定含有一個凸四邊形Erdos和Szekeres(1935)證明了g(n)一定存在，并且有5個頂點時的情形機器證明——吳消元法1976年吳文俊教授開始進行研究幾何定理的機器證明，并在很短的時間內(nèi)取得重大突破。他的基本思想如下：引進坐標(biāo)，將幾何定理用代數(shù)方程組的形式表達(dá)；提出一套完整可行的符號解法，將此代數(shù)方程組求解。此兩步中，一般第二步更為困難。機器證明——吳消元法周咸青利用并發(fā)展吳方法，編制出計算機軟件，證明了500多條有相當(dāng)難度的幾何定理，并在美國出版了幾何定理機器證明的專著。吳方法不僅可證明已有的幾何定理，而且可以自動發(fā)現(xiàn)新的定理?？梢詮腒erler定律推導(dǎo)牛頓定律；解決一些非線性規(guī)劃問題；給出Puma型機器人的逆運動方程的解。吳文俊教授還將其方法推廣到微分幾何定理的機器證明上。網(wǎng)絡(luò)流問題隨著中國經(jīng)濟快速的增長，城市化是未來中國的發(fā)展方向。人大通過的“十五”規(guī)劃，把物流業(yè)作為戰(zhàn)略重點列入要大力發(fā)展的新興服務(wù)產(chǎn)業(yè)。如何制定一個運輸計劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個網(wǎng)絡(luò)最大流問題。

網(wǎng)絡(luò)流問題1956年Ford和Fulkerson提出了關(guān)于網(wǎng)絡(luò)流問題的一個重要定理。最大流最小割定理：在任何網(wǎng)絡(luò)中，最大流的值等于最小割的容量。由這個定理可以引出求網(wǎng)絡(luò)最大流的一個算法——標(biāo)號法。1970年，Edmonds和Karp對標(biāo)號程序加以改進，使之成為一個好的算法。穩(wěn)定的婚姻問題

組合數(shù)學(xué)中有一個著名定理：如果一個村子里每一個女孩都恰好認(rèn)識k個男孩，并且每一個男孩也恰好認(rèn)識k個女孩，那么每一個女孩都可以嫁給她認(rèn)識的一個男孩，并且每一個男孩都可以娶一個他認(rèn)識的女孩。（k正則二部圖，一定存在一個完美匹配）穩(wěn)定的婚姻問題但是這樣的安排方法不一定是最好的。假如能找到兩對夫婦，彼此都更喜歡對方的配偶，那么這樣婚姻有潛在的不穩(wěn)定性。用圖論匹配理論中Gale-Shapley算法，可以找到一種婚姻的安排方法，使得沒有上述的不穩(wěn)定情況出現(xiàn)。穩(wěn)定的婚姻問題

這種組合數(shù)學(xué)的方法有

一個實際的用途：美國的醫(yī)院在確定錄取住院醫(yī)生時，他們將考慮申請者的志愿的先后次序，同時也給申請者排序。按這樣的

次序考慮出的總的方案將沒有醫(yī)院和申請者兩者同時后悔的情況。

實際上，高考學(xué)生的最后錄取方案也可以用這種方法。

棧排序問題(Knuth,1960’s)模式:對任意一個排列π,最小的元素用１代替，次小的元素用２代替……以此類推