前言組合數(shù)學概述.PPT

1、1,組合數(shù)學引論Introductory Combinatorics（第四版,美) Richard A . Brualdi 著 馮舜璽 羅平 裴偉東 譯 盧開澄 馮舜璽 校 主講教師： 李 向 軍 2008年9月 于 南 昌 大 學,2,第一章(Chapter 1)什么是組合數(shù)學?What is Combinatorics,3,組合數(shù)學概述,現(xiàn)代數(shù)學可以分為兩大類：一類是研究連續(xù)對象的，如分析、方程等；另一類就是研究離散對象的組合數(shù)學。 計算機出現(xiàn)以后，由于離散對象的處理是計算機科學的核心，研究離散對象的組合數(shù)學得到迅猛發(fā)展,4,組合數(shù)學概述,吳文俊院士指出：“每個時代都有它特殊的要求，使得數(shù)

2、學出現(xiàn)一個新的面貌，產(chǎn)生一些新的數(shù)學分支，組合數(shù)學這個新的分支也是在時代的要求下產(chǎn)生的?！?，“信息技術(shù)很可能會給數(shù)學本身帶來一場根本性的變革，而組合數(shù)學則將顯示出它的重要作用。” Gian-Carlo Rota教授曾提出要向中國領(lǐng)導人呼吁，組合數(shù)學是計算機軟件產(chǎn)業(yè)的基礎，中國最終一定能成為一個軟件大國，但是要實現(xiàn)這個目標的一個突破點就是發(fā)展組合數(shù)學,5,組合數(shù)學是一個古老而又年輕的數(shù)學分支，據(jù) 傳說，大禹在4000多年前就觀察到了神龜背上的幻方。賈憲，北宋數(shù)學家（約11世紀）著有：黃帝九章細草、算法敩古集（又稱“古算法導引” ），都已失傳。楊輝著詳解九章算法（1261年）中曾引賈憲的“開方作法

3、本源圖”（即指數(shù)為正數(shù)的二項式展開系數(shù)表 ， 現(xiàn)稱“楊輝三角” ）和“增乘方法”（求高次冪的正根法）。前者比帕斯卡（Pascal）三角形早600年，后者比霍納（William Geoge.Horner,1786-1837）的方法（1819年）早770年,組合數(shù)學的歷史,6,1666年萊布尼茲所著的組合數(shù)學論文一書問世，這是組合數(shù)學的第一部專著，書中首次使用了組合學（Combinatorics）一詞。 組合數(shù)學于60年代以來迅速發(fā)展的原因有：一是計算機運行程序的算法中，運行時間效率和存儲需求分析需要大量的組合數(shù)學思想；二是組合數(shù)學的思想和技巧不僅正在用于數(shù)學應用的傳統(tǒng)自然科學領(lǐng)域，而且也越來越多

4、地用于社會科學、生物科學、信息論等領(lǐng)域。 組合數(shù)學定義的一般描述：組合數(shù)學是研究離散結(jié)構(gòu)的存在、計數(shù)、分析和優(yōu)化等問題的一門科學,組合數(shù)學的歷史,7,我國古代的河洛圖(幻方)問題,傳說在公元前23世紀大禹治水的時候，在黃河支流洛水中，浮現(xiàn)出一個 大烏龜，甲上背有9種花點的圖案，人們將圖案中的花點數(shù)了一下，競驚奇地發(fā)現(xiàn)9種花點數(shù)正巧是19這9個數(shù)，各數(shù)位置的排列也相當奇妙，橫的3行、縱的3列以及兩對角線上各自的數(shù)字之和都為15,上圖為三階洛書,8,幻方問題,組合數(shù)學中有許多象幻方這樣精巧的結(jié)構(gòu)。 1977年美國旅行者1號、2號宇宙飛船就帶上了幻方以作為人類智慧的信號,階 幻 方,9,阿基米德手稿

5、,上圖為一份用希臘文寫在羊皮紙上的阿基米德手稿副本, 最近科學家借助現(xiàn)代科技手段初步破譯了古希臘數(shù)學家阿基米德的這篇論文, 結(jié)論是這篇被稱作Stomachion的論文解決的是組合數(shù)學問題,10,阿基米德手稿,在論文中阿基米德是在計算把14條不規(guī)則的紙帶拼成正方形一共能有多少種不同的拼法。這在現(xiàn)在被稱為tiling問題。 當今數(shù)學家借助計算機得出的答案是17152種拼法，這在當時是相當困難的,11,Periodic Tilings,Non-Periodic Tilings,Penrose Tilings,Symmetric Tilings,Symmetric Tilings,12,賈憲三角,中國

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

7、,Knigsberg橋?qū)膱D,15,36 軍官問題 (歐拉 1779) The Great Frederic的閱兵難題-歐拉的困惑 拉丁方陣,正交拉丁方陣,16,Euler 猜想,不存在6階正交拉丁方 不存在4k+2階正交拉丁方 現(xiàn)在的結(jié)論 對任正整數(shù) n2,6， 存在 n 階正交拉丁方,17,組合數(shù)學的應用,組合數(shù)學不僅在基礎數(shù)學研究中具有極其重要的地位，在其它的學科如計算機科學、編碼和密碼學、物理、化學、生物等學科中，甚至在企業(yè)管理，交通規(guī)劃，戰(zhàn)爭指揮，金融分析，城市物流等領(lǐng)域均有重要應用,18,組合數(shù)學的應用,著名的組合數(shù)學家 Thomas Tutte 在組合數(shù)學界是泰斗級的大師。直到

8、最近人們才知道，原來他對提前結(jié)束“二戰(zhàn)”有著突出貢獻。 Tutte 從德軍的兩條情報密碼出發(fā)，用組合數(shù)學的方法，重建了敵人的密碼機，確定了德軍密碼的內(nèi)部結(jié)構(gòu)，從而獲得了極為重要的情報,19,組合數(shù)學的應用,在美國有一家公司用組合數(shù)學的方法來提高企業(yè)管理的效益，這家公司辦得非常成功。 在美國已有專門的公司用組合設計的方法開發(fā)軟件，來解決工業(yè)界中的試驗設計問題。 德國一位著名組合數(shù)學家利用組合數(shù)學方法研究藥物結(jié)構(gòu)，為制藥公司節(jié)省了大量的費用，引起了制藥業(yè)的關(guān)注,20,四色問題,在日常生活中我們常?？梢杂龅浇M合數(shù)學的問題。比如一個著名的世界難題“四色猜想” ：一張地圖，用一種顏色對一個地區(qū)著色，那么

9、一共只需要四種顏色就能保證每兩個相鄰的地區(qū)顏色不同,21,四色問題,1852年，剛從倫敦大學畢業(yè)的Francis Guthrie提出了四色猜想。 1878年著名的英國數(shù)學家Cayley向數(shù)學界征求解答。 此后數(shù)學家 Heawood 花費了畢生的精力致力于四色研究，于1890年證明了五色定理（每個平面圖都是5頂點可著色的）。 直到1976年6月，美國數(shù)學家 K. Appel與 W. Haken，在3臺不同的電子計算機上，用了1200小時，才終于完成了“四色猜想”的證明，從而使四色猜想成為了四色定理,22,中國郵遞員問題,1962年中國組合數(shù)學家管梅谷教授提出了著名的“中國郵遞員問題”。 一個郵遞

10、員從郵局出發(fā)，要走完他所管轄的每一條街道，然后返回郵局。那么如何選擇一條盡可能短的路線,23,中國郵遞員問題,這個問題可以轉(zhuǎn)化為：給定一個具有非負權(quán)的賦權(quán)圖G， （1）用添加重復邊的方法求G的一個Euler賦權(quán)母圖G*，使得 盡可能小。 （2）求G*的Euler 環(huán)游。 這個問題可以由Fleury算法和1973年著名組合數(shù)學家J. Edmonds和Johnson 給出的一個好的算法解決,24,貨郎擔問題,一個貨郎要去若干城鎮(zhèn)賣貨，然后回到出發(fā)地，給定各城鎮(zhèn)之間所需的旅行時間后，應怎樣計劃他的路線，使他能去每個城鎮(zhèn)恰好一次而且總時間最短,25,貨郎擔問題,用圖論的術(shù)語說，就是在一個賦權(quán)完全圖中，

11、找出一個具有最小權(quán)的Hamilton 圈（包含圖G的每個頂點的圈)。 這個問題目前還沒有有效的算法。 Hamilton問題是圖論的一個重要問題，圖論中的許多問題，包括四色問題、圖的因子問題，最終都與Hamilton問題有關(guān),26,相識問題,1958年，美國的數(shù)學月刊上登載著這樣一個有趣的問題：“任何6個人的聚會，其中總會有3個人相互認識，或3個人相互不認識”。 用6個頂點表示6個人，用紅色連線表示兩者相識，用藍色連線表示兩者不相識。于是問題化為下述命題,27,相識問題,對6個頂點的完全圖K6任意進行紅、藍兩邊著色，則圖中一定存在一個同色三角形,28,Ramsey數(shù),推廣為一般問題：給定任意正整

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

13、中，一定有n個頂點組成一個凸n邊形。 5頂點一定含有一個凸四邊形 Erdos 和 Szekeres (1935) 證明了 g(n) 一定存在，并且有,5個頂點時的情形,31,機器證明吳消元法,1976年吳文俊教授開始進行研究幾何定理的機器證明，并在很短的時間內(nèi)取得重大突破。 他的基本思想如下：引進坐標，將幾何定理用代數(shù)方程組的形式表達；提出一套完整可行的符號解法，將此代數(shù)方程組求解。此兩步中，一般第二步更為困難,32,機器證明吳消元法,周咸青利用并發(fā)展吳方法，編制出計算機軟件，證明了500多條有相當難度的幾何定理，并在美國出版了幾何定理機器證明的專著。 吳方法不僅可證明已有的幾何定理，而且可以

14、自動發(fā)現(xiàn)新的定理?？梢詮腒erler定律推導牛頓定律；解決一些非線性規(guī)劃問題；給出Puma型機器人的逆運動方程的解。 吳文俊教授還將其方法推廣到微分幾何定理的機器證明上,33,網(wǎng)絡流問題,隨著中國經(jīng)濟快速的增長，城市化是未來中國的發(fā)展方向。人大通過的“十五”規(guī)劃，把物流業(yè)作為戰(zhàn)略重點列入要大力發(fā)展的新興服務產(chǎn)業(yè)。如何制定一個運輸計劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個網(wǎng)絡最大流問題,34,網(wǎng)絡流問題,1956年Ford 和Fulkerson 提出了關(guān)于網(wǎng)絡流問題的一個重要定理。 最大流最小割定理：在任何網(wǎng)絡中，最大流的值等于最小割的容量。 由這個定理可以引出求網(wǎng)絡最大流的一個算法標號法

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

16、數(shù)學的方法有 一個實際的用途：美國的醫(yī)院在確定錄取住院醫(yī)生時，他們將考慮申請者的志愿的先后次序，同時也給申請者排序。按這樣的 次序考慮出的總的方案將沒有醫(yī)院和申請者兩者同時后悔的情況。 實際上，高考學生的最后錄取方案也可以用這種方法,38,棧排序問題(Knuth, 1960s,模式: 對任意一個排列 , 最小的元素用代替，次小的元素用代替以此類推，這樣得到的排列叫的模式。 例如 914的模式為：312 37925 的模式為： 24513,39,棧排序問題(Knuth, 1960s,避免排列：一個排列是避免的，當且僅當它的任意子序列中沒有模式。 例如 132564是避免 312的排列 14623

17、5是包含312的排列,40,棧排序問題(Knuth, 1960s,8,7,6,5,4,3,2,1,避免312排列,41,全一問題,假設博物館里有若干個房間，每個房間里有一盞燈和一個開關(guān)，每次按下某個房間的開關(guān)，可以改變這個房間以及它相鄰的房間的燈的狀態(tài),42,全一問題,問是否可以找到一種開燈的方案，使得所有房間的燈由全亮變?yōu)槿珳纾窟@就是Sutner 于1989年提出的“全一問題”（All-Ones Problem,43,最小全一問題,求操作次數(shù)最少的解稱為最小全一問題。 我們已經(jīng)知道，對于一般圖上的最小全一問題是NP完備的。 陳永川教授與他人合作找到了一個線性時間算法，很好地解決了樹和單圈圖的

18、最小全一問題。（SIAM Journal on Computing，2004,44,網(wǎng)絡可靠性問題,一個通訊網(wǎng)絡怎樣布局穩(wěn)定性最好，而且費用最節(jié)?。?美國的貝爾實驗室和IBM公司都有世界一流的組合數(shù)學家在研究這個問題，這個問題直接關(guān)系到巨大的經(jīng)濟利益,45,最短網(wǎng)絡問題,如何用最短的線路將三部電話連起來？ 此問題可抽象為設ABC為等邊三角形，連接三頂點的路線（稱為網(wǎng)絡）。這種網(wǎng)絡有許多個，其中最短路線者顯然是二邊之和（如ABAC,A,B,C,46,最短網(wǎng)絡問題,但若增加一個周轉(zhuǎn)站（新點P），連接4點的新網(wǎng)絡的最短路線為PAPBPC。最短新路徑之長N比原來只連三點的最短路徑O要短。 這樣得到的網(wǎng)

19、絡不僅比原來節(jié)省材料，而且穩(wěn)定性也更好,A,B,C,P,47,PollakGilbert猜想,由于最短網(wǎng)絡在運輸、通訊和計算機等現(xiàn)代經(jīng)濟與科技領(lǐng)域中都有重要的應用，對這個問題的研究也越來越深入。問題的對象已由三個點擴展到任意有限個點集,48,PollakGilbert猜想,斯坦納（Steiner）最小樹是可以在給定的點之外再增加若干個點(稱為斯坦納點)，然后將所有這些點連起來。 如果不允許增加任何額外的點作為網(wǎng)絡的頂點，這種最短網(wǎng)絡稱為最小生成樹。 在前面的例子中Steiner最小樹的長為 而最小生成樹的長為2,49,PollakGilbert猜想,1968年貝爾實驗室數(shù)學中心主任波雷克(Po

20、llak)和研究員吉爾伯特(Gilbert)提出如下猜想： 平面上任意n點集，斯坦納最小樹長與最小生成樹之長的比值的最小值是 。 這個猜想又被稱為斯坦納比猜想,50,PollakGilbert猜想,PollakGilbert猜想起源于在美國貝爾電話公司發(fā)生的一個富有戲劇性的事件。 1967年前，貝爾公司按照連結(jié)各分部的最小生成樹的長度來收費。1967年一家航空公司戳了貝爾公司一個大洞。當時這家企業(yè)申請要求貝爾公司增加一些服務點，而這些服務點恰恰位于構(gòu)造該公司各分部的斯坦納最小樹需增加的斯坦納頂點上。這使得貝爾公司不僅要拉新線，增加服務網(wǎng)點，而且還要減少收費。這一意外事件迫使貝爾公司自此以后便采

21、用了斯坦納最小樹原則,51,PollakGilbert猜想,1990年，中科院應用數(shù)學所研究員堵丁柱與美籍華人黃光明合作，證明了PollakGilbert猜想。在美國離散數(shù)學界引起轟動，被列為19891990年度美國離散數(shù)學界與理論計算機科學界的兩項重大成果之一。 在不列顛百科全書1992年鑒的數(shù)學評論中，該成果被列為世界上當年六項數(shù)學成果首項。 該成果被我國列為1992年十大科技成就之一,52,無尺度網(wǎng)絡,20世紀20年代，由Karinthy提出。 1950年， Pool 和 Kochen提出這樣一個問題：“兩個毫無關(guān)系的人，要讓他們互相認識，至少要經(jīng)過多少人？” 美國哈佛大學社會心理學家S

22、. Milgram在1967年做過一項有趣的實驗，據(jù)說他從內(nèi)布拉斯加州的奧馬哈隨機選了300人，然后請他們每個人嘗試寄一封信到波士頓的一位證券業(yè)務員。寄信的規(guī)則很簡單，就是任何收信者只能把信寄給自己熟識的人,53,重要結(jié)論,6度分離” 對每個人來說，平均大約只需要通過個人就能將信寄到目的地。 研究無尺度網(wǎng)絡，對于防備黑客攻擊、防治流行病、和開發(fā)新藥等，都具有重要的意義。 在1999年，Barabasi et al.發(fā)現(xiàn)在因特網(wǎng)上，任意兩個網(wǎng)頁間的鏈接最多為19次。(Nature 401, 1999,54,無尺度網(wǎng)絡的一個例子,因特網(wǎng)是一個無尺度網(wǎng)絡，左圖的星爆形結(jié)構(gòu)描繪了從某一測試站點到其他約十萬個站點的最短連結(jié)路徑。圖中以相同的顏色來表示相類似的站點,55,Szem