《淺談組合數(shù)學(xué)》PPT課件

淺談組合數(shù)學(xué),南開大學(xué) 組合數(shù)學(xué)中心 陳永川 2004年7月,組合數(shù)學(xué)概述,現(xiàn)代數(shù)學(xué)可以分為兩大類：一類是研究連續(xù)對象的，如分析、方程等；另一類就是研究離散對象的組合數(shù)學(xué)。 計算機(jī)出現(xiàn)以后，由于離散對象的處理是計算機(jī)科學(xué)的核心，研究離散對象的組合數(shù)學(xué)得到迅猛發(fā)展。,組合數(shù)學(xué)概述,吳文俊院士指出，每個時代都有它特殊的要求，使得數(shù)學(xué)出現(xiàn)一個新的面貌，產(chǎn)生一些新的數(shù)學(xué)分支，組合數(shù)學(xué)這個新的分支也是在時代的要求下產(chǎn)生的。 最近，吳文俊院士又指出，信息技術(shù)很可能會給數(shù)學(xué)本身帶來一場根本性的變革，而組合數(shù)學(xué)則將顯示出它的重要作用。 Gian-Carlo Rota教授曾提出要向中國領(lǐng)導(dǎo)人呼吁，組合數(shù)學(xué)是計算機(jī)軟件產(chǎn)業(yè)的基礎(chǔ)，中國最終一定能成為一個軟件大國，但是要實(shí)現(xiàn)這個目標(biāo)的一個突破點(diǎn)就是發(fā)展組合數(shù)學(xué)。,組合數(shù)學(xué)的歷史,傳說在公元前23世紀(jì)大禹治水的時候，在黃河支流洛水中，浮現(xiàn)出一個 大烏龜，甲上背有9種花點(diǎn)的圖案，人們將圖案中的花點(diǎn)數(shù)了一下，競驚奇地發(fā)現(xiàn)9種花點(diǎn)數(shù)正巧是19這9個數(shù)，各數(shù)位置的排列也相當(dāng)奇妙，橫的3行、縱的3列以及兩對角線上各自的數(shù)字之和都為15。,上圖為三階洛書,幻方問題,組合數(shù)學(xué)中有許多象幻方這樣精巧的結(jié)構(gòu)。 1977年美國旅行者1號、2號宇宙飛船就帶上了幻方以作為人類智慧的信號。, 階 幻 方,阿基米德手稿,上圖為一份用希臘文寫在羊皮紙上的阿基米德手稿副本, 最近科學(xué)家借助現(xiàn)代科技手段初步破譯了古希臘數(shù)學(xué)家阿基米德的這篇論文, 結(jié)論是這篇被稱作Stomachion的論文解決的是組合數(shù)學(xué)問題。,阿基米德手稿,在論文中阿基米德是在計算把14條不規(guī)則的紙帶拼成正方形一共能有多少種不同的拼法。這在現(xiàn)在被稱為tiling問題。 當(dāng)今數(shù)學(xué)家借助計算機(jī)得出的答案是17152種拼法，這在當(dāng)時是相當(dāng)困難的。,Periodic Tilings,Non-Periodic Tilings,Penrose Tilings,Symmetric Tilings,Symmetric Tilings,賈憲三角,中國最早的組合數(shù)學(xué)理論可追溯到宋朝時期的”賈憲三角”, 后來被楊輝引用, 所以普遍稱之為”楊輝三角”, 這在西方是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,七橋問題,近代圖論的歷史可追溯到18世紀(jì)的七橋問題穿過Knigsberg城的七座橋，要求每座橋通過一次且僅通過一次。 Euler1736年證明了不可能存在這樣的路線。,Euler 定理,如果一個圖包含一條經(jīng)過每條邊恰好一次的閉途徑，則稱這個圖為歐拉圖。 對任意的非空連通圖，若它是歐拉的, 當(dāng)且僅當(dāng)它沒有奇度點(diǎn)。,Knigsberg橋?qū)?yīng)的圖,36 軍官問題 (歐拉 1779) The Great Frederic的閱兵難題-歐拉的困惑 拉丁方陣:,正交拉丁方陣:,Euler 猜想,不存在6階正交拉丁方 不存在4k+2階正交拉丁方 現(xiàn)在的結(jié)論 對任正整數(shù) n2,6， 存在 n 階正交拉丁方,組合數(shù)學(xué)的應(yīng)用,組合數(shù)學(xué)不僅在基礎(chǔ)數(shù)學(xué)研究中具有極其重要的地位，在其它的學(xué)科如計算機(jī)科學(xué)、編碼和密碼學(xué)、物理、化學(xué)、生物等學(xué)科中，甚至在企業(yè)管理，交通規(guī)劃，戰(zhàn)爭指揮，金融分析，城市物流等領(lǐng)域均有重要應(yīng)用。,組合數(shù)學(xué)的應(yīng)用,著名的組合數(shù)學(xué)家 Thomas Tutte 在組合數(shù)學(xué)界是泰斗級的大師。直到最近人們才知道，原來他對提前結(jié)束“二戰(zhàn)”有著突出貢獻(xiàn)。 Tutte 從德軍的兩條情報密碼出發(fā)，用組合數(shù)學(xué)的方法，重建了敵人的密碼機(jī)，確定了德軍密碼的內(nèi)部結(jié)構(gòu)，從而獲得了極為重要的情報。,組合數(shù)學(xué)的應(yīng)用,在美國有一家公司用組合數(shù)學(xué)的方法來提高企業(yè)管理的效益，這家公司辦得非常成功。 在美國已有專門的公司用組合設(shè)計的方法開發(fā)軟件，來解決工業(yè)界中的試驗設(shè)計問題。 德國一位著名組合數(shù)學(xué)家利用組合數(shù)學(xué)方法研究藥物結(jié)構(gòu)，為制藥公司節(jié)省了大量的費(fèi)用，引起了制藥業(yè)的關(guān)注。,四色問題,在日常生活中我們常?？梢杂龅浇M合數(shù)學(xué)的問題。比如一個著名的世界難題“四色猜想” ：一張地圖，用一種顏色對一個地區(qū)著色，那么一共只需要四種顏色就能保證每兩個相鄰的地區(qū)顏色不同。,四色問題,1852年，剛從倫敦大學(xué)畢業(yè)的Francis Guthrie提出了四色猜想。 1878年著名的英國數(shù)學(xué)家Cayley向數(shù)學(xué)界征求解答。 此后數(shù)學(xué)家 Heawood 花費(fèi)了畢生的精力致力于四色研究，于1890年證明了五色定理（每個平面圖都是5頂點(diǎn)可著色的）。 直到1976年6月，美國數(shù)學(xué)家 K. Appel與 W. Haken，在3臺不同的電子計算機(jī)上，用了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的每個頂點(diǎn)的圈)。 這個問題目前還沒有有效的算法。 Hamilton問題是圖論的一個重要問題，圖論中的許多問題，包括四色問題、圖的因子問題，最終都與Hamilton問題有關(guān)。,相識問題,1958年，美國的數(shù)學(xué)月刊上登載著這樣一個有趣的問題：“任何6個人的聚會，其中總會有3個人相互認(rèn)識，或3個人相互不認(rèn)識”。 用6個頂點(diǎn)表示6個人，用紅色連線表示兩者相識，用藍(lán)色連線表示兩者不相識。于是問題化為下述命題：,相識問題,對6個頂點(diǎn)的完全圖K6任意進(jìn)行紅、藍(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ù)。,Erds -Szekeres 定理,Ramsey定理是由Erds和Szekeres于1935年提出的。它是下述定理的一個推廣： 定理（Erds和Szekeres） ：若 a, b N，n=ab+1，且x1, , xn是任一n個實(shí)數(shù)的序列，則這個序列包含一個有a+1項的單調(diào)遞增（遞減）的子序列，或一個有b+1項的單調(diào)遞減（遞增）的子序列。,Happy End 問題,對于n3，處于平面上一般位置（任意三個頂點(diǎn)不共線）的g(n)個頂點(diǎn)中，一定有n個頂點(diǎn)組成一個凸n邊形。 5頂點(diǎn)一定含有一個凸四邊形 Erdos 和 Szekeres (1935) 證明了 g(n) 一定存在，并且有,5個頂點(diǎn)時的情形,機(jī)器證明吳消元法,1976年吳文俊教授開始進(jìn)行研究幾何定理的機(jī)器證明，并在很短的時間內(nèi)取得重大突破。 他的基本思想如下：引進(jìn)坐標(biāo)，將幾何定理用代數(shù)方程組的形式表達(dá)；提出一套完整可行的符號解法，將此代數(shù)方程組求解。此兩步中，一般第二步更為困難。,機(jī)器證明吳消元法,周咸青利用并發(fā)展吳方法，編制出計算機(jī)軟件，證明了500多條有相當(dāng)難度的幾何定理，并在美國出版了幾何定理機(jī)器證明的專著。 吳方法不僅可證明已有的幾何定理，而且可以自動發(fā)現(xiàn)新的定理。可以從Kerler定律推導(dǎo)牛頓定律；解決一些非線性規(guī)劃問題；給出Puma型機(jī)器人的逆運(yùn)動方程的解。 吳文俊教授還將其方法推廣到微分幾何定理的機(jī)器證明上。,網(wǎng)絡(luò)流問題,隨著中國經(jīng)濟(jì)快速的增長，城市化是未來中國的發(fā)展方向。人大通過的“十五”規(guī)劃，把物流業(yè)作為戰(zhàn)略重點(diǎn)列入要大力發(fā)展的新興服務(wù)產(chǎn)業(yè)。如何制定一個運(yùn)輸計劃使生產(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)號程序加以改進(jìn)，使之成為一個好的算法。,穩(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é)的方法有 一個實(shí)際的用途：美國的醫(yī)院在確定錄取住院醫(yī)生時，他們將考慮申請者的志愿的先后次序，同時也給申請者排序。按這樣的 次序考慮出的總的方案將沒有醫(yī)院和申請者兩者同時后悔的情況。 實(shí)際上，高考學(xué)生的最后錄取方案也可以用這種方法。,棧排序問題(Knuth, 1960s),模式: 對任意一個排列 , 最小的元素用代替，次小的元素用代替以此類推，這樣得到的排列叫的模式。 例如 914的模式為：312 37925 的模式為： 24513,棧排序問題(Knuth, 1960s),避免排列：一個排列是避免的，當(dāng)且僅當(dāng)它的任意子序列中沒有模式。 例如 132564是避免 312的排列 146235是包含312的排列,棧排序問題(Knuth, 1960s),8,7,6,5,4,3,2,1,避免312排列,全一問題,假設(shè)博物館里有若干個房間，每個房間里有一盞燈和一個開關(guān)，每次按下某個房間的開關(guān)，可以改變這個房間以及它相鄰的房間的燈的狀態(tài)。,全一問題,問是否可以找到一種開燈的方案，使得所有房間的燈由全亮變?yōu)槿珳?？這就是Sutner 于1989年提出的“全一問題”（All-Ones Problem)。,最小全一問題,求操作次數(shù)最少的解稱為最小全一問題。 我們已經(jīng)知道，對于一般圖上的最小全一問題是NP完備的。 陳永川教授與他人合作找到了一個線性時間算法，很好地解決了樹和單圈圖的最小全一問題。（SIAM Journal on Computing，2004）,網(wǎng)絡(luò)可靠性問題,一個通訊網(wǎng)絡(luò)怎樣布局穩(wěn)定性最好，而且費(fèi)用最節(jié)省？ 美國的貝爾實(shí)驗室和IBM公司都有世界一流的組合數(shù)學(xué)家在研究這個問題，這個問題直接關(guān)系到巨大的經(jīng)濟(jì)利益。,最短網(wǎng)絡(luò)問題,如何用最短的線路將三部電話連起來？ 此問題可抽象為設(shè)ABC為等邊三角形，連接三頂點(diǎn)的路線（稱為網(wǎng)絡(luò)）。這種網(wǎng)絡(luò)有許多個，其中最短路線者顯然是二邊之和（如ABAC）。,A,B,C,最短網(wǎng)絡(luò)問題,但若增加一個周轉(zhuǎn)站（新點(diǎn)P），連接4點(diǎn)的新網(wǎng)絡(luò)的最短路線為PAPBPC。最短新路徑之長N比原來只連三點(diǎn)的最短路徑O要短。 這樣得到的網(wǎng)絡(luò)不僅比原來節(jié)省材料，而且穩(wěn)定性也更好。,A,B,C,P,PollakGilbert猜想,由于最短網(wǎng)絡(luò)在運(yùn)輸、通訊和計算機(jī)等現(xiàn)代經(jīng)濟(jì)與科技領(lǐng)域中都有重要的應(yīng)用，對這個問題的研究也越來越深入。問題的對象已由三個點(diǎn)擴(kuò)展到任意有限個點(diǎn)集。,PollakGilbert猜想,斯坦納（Steiner）最小樹是可以在給定的點(diǎn)之外再增加若干個點(diǎn)(稱為斯坦納點(diǎn))，然后將所有這些點(diǎn)連起來。 如果不允許增加任何額外的點(diǎn)作為網(wǎng)絡(luò)的頂點(diǎn)，這種最短網(wǎng)絡(luò)稱為最小生成樹。 在前面的例子中Steiner最小樹的長為 而最小生成樹的長為2。,PollakGilbert猜想,1968年貝爾實(shí)驗室數(shù)學(xué)中心主任波雷克(Pollak)和研究員吉爾伯特(Gilbert)提出如下猜想： 平面上任意n點(diǎn)集，斯坦納最小樹長與最小生成樹之長的比值的最小值是 。 這個猜想又被稱為斯坦納比猜想。,PollakGilbert猜想,PollakGilbert猜想起源于在美國貝爾電話公司發(fā)生的一個富有戲劇性的事件。 1967年前，貝爾公司按照連結(jié)各分部的最小生成樹的長度來收費(fèi)。1967年一家航空公司戳了貝爾公司一個大洞。當(dāng)時這家企業(yè)申請要求貝爾公司增加一些服務(wù)點(diǎn)，而這些服務(wù)點(diǎn)恰恰位于構(gòu)造該公司各分部的斯坦納最小樹需增加的斯坦納頂點(diǎn)上。這使得貝爾公司不僅要拉新線，增加服務(wù)網(wǎng)點(diǎn)，而且還要減少收費(fèi)。這一意外事件迫使貝爾公司自此以后便采用了斯坦納最小樹原則 。,PollakGilbert猜想,1990年，中科院應(yīng)用數(shù)學(xué)所研究員堵丁柱與美籍華人黃光明合作，證明了PollakGilbert猜想。在美國離散數(shù)學(xué)界引起轟動，被列為19891990年度美國離散數(shù)學(xué)界與理論計算機(jī)科學(xué)界的兩項重大成果之一。 在不列顛百科全書1992年鑒的數(shù)學(xué)評論中，該成果被列為世界上當(dāng)年六項數(shù)學(xué)成果首項。 該成果被我國列為1992年十大科技成就之一。,無尺度網(wǎng)絡(luò),20世紀(jì)20年代，由Karinthy提出。 1950年， Pool 和 Kochen提出這樣一個問題：“兩個毫無關(guān)系的人，要讓他們互相認(rèn)識，至少要經(jīng)過多少人？” 美國哈佛大學(xué)社會心理學(xué)家S. Milgram在1967年做過一項有趣的實(shí)驗，據(jù)說他從內(nèi)布拉斯加州的奧馬哈隨機(jī)選了300人，然后請他們每個人嘗試寄一封信到波士頓的一位證券業(yè)務(wù)員。寄信的規(guī)則很簡單，就是任何收信者只能把信寄給自己熟識的人。,重要結(jié)論,“6度分離” 對每個人來說，平均大約只需要通過個人就能將信寄到目的地。 研究無尺度網(wǎng)絡(luò)，對于防備黑客攻擊、防治流行病、和開發(fā)新藥等，都具有重要的意義。 在1999年，Barabasi et al.發(fā)現(xiàn)在因特網(wǎng)上，任意兩個網(wǎng)頁間的鏈接最多為19次。(Nature 401, 1999),無尺度網(wǎng)絡(luò)的一個例子,因特網(wǎng)是一個無尺度網(wǎng)絡(luò)，左圖的星爆形結(jié)構(gòu)描繪了從某一測試站點(diǎn)到其他約十萬個站點(diǎn)的最短連結(jié)路徑。圖中以相同的顏色來表示相類似的站點(diǎn)。,Szemerdi 定理,若 k 為一個正整數(shù)并且0，則存在一個正整數(shù) N = N(k,) ，使得集合1，2，N的每一個N 長的子集都包含 k 長的等差級數(shù)。 N(k,) 有一個很有名的界,Szemerdi 定理,其中下界是由Behrend（對k=3的情形）和Rankin 給出的，上界是由W.Timothy Gowers 給出的。 Gowers因為給出了這個上界而獲得了1998年的Fields獎。,生物數(shù)學(xué),目前，計算生物學(xué)、基因理論、生物信息學(xué)都是最前沿的研究領(lǐng)域。 隨著人類基因組計劃的完成和其他基因計劃的完成，所有公認(rèn)的和潛在的蛋白質(zhì)元都可以被確定，通過大規(guī)模的實(shí)驗技術(shù)，可以生成大量的生物學(xué)數(shù)據(jù)。,生物數(shù)學(xué),如何處理這些數(shù)據(jù)來獲得生物學(xué)的信息，這里組合數(shù)學(xué)和隨機(jī)圖論都起到了關(guān)鍵的作用。 如果將基因看作網(wǎng)絡(luò)中的頂點(diǎn)，將他們之間的作用看作網(wǎng)絡(luò)中的邊，那么每一次大規(guī)模實(shí)驗將給我們帶來關(guān)于基因交互作用網(wǎng)絡(luò)的一些信息。這個網(wǎng)絡(luò)的拓?fù)湫再|(zhì)是科學(xué)家們關(guān)心的焦點(diǎn)（如每一個頂點(diǎn)的度和網(wǎng)絡(luò)中的最小距離問題是兩個初步的問題）。,生物信息學(xué),組合數(shù)學(xué)和概率統(tǒng)計在生物信息學(xué)中有重要應(yīng)用。 美國科學(xué)院院士Michael Waterman教授，曾鼓勵我們借助組合數(shù)學(xué)的優(yōu)勢，開展生物信息學(xué)的研究。 天津大學(xué)張春霆院士和北京師范大學(xué)王梓坤院士，北京大學(xué)錢敏平教授，南開大學(xué)沈世鎰教授，,謝 謝 !,