《淺談組合數(shù)學》ppt課件 (2)-預覽頁
【正文】 四色問題 ? 在日常生活中我們常?？梢杂龅浇M合數(shù)學的問題。 ? 此后數(shù)學家 Heawood 花費了畢生的精力致力于四色研究，于 1890年證明了五色定理（ 每個平面圖都是 5頂點可著色的 ）。五色定理。那么如何選擇一條盡可能短的路線。 ? 五個點的則不然。 Ramsey數(shù) R(p,q) p,q 3 4 5 6 7 8 9 3 6 9 14 18 23 28 36 4 18 25 35–41 49–61 56–84 69–115 5 43–49 58–87 80–143 101–216 121–316 6 102–165 111–298 127–495 169–780 7 205–540 216–1031 232–1713 8 282–1870 317–3583 9 565–6588 Ramsey數(shù)的計算 ? Ramsey數(shù)的計算是對人類智力的挑戰(zhàn)！例如 R(4,5)=25 (1993年計算機 11年的計算量 ) ? Erd246。s ? 1997年 Fulkerson獎得主 Kim ? 1998年 Fields獎得主 Gowers ? 1999年 Wolf獎得主 Lovasz ? 2022年 Steele獎得主 Graham ? 2022年 G246。 ? 古人在滿天的星斗中發(fā)現(xiàn)野獸和眾神群集于天空的圖形，以為是造物主的杰作。 穩(wěn)定的婚姻問題 ? 組合數(shù)學中有一個著名定理：如果一個村子里每一個女孩都恰好認識 k個男孩，并且每一個男孩也恰好認識 k個女孩，那么每一個女孩都可以嫁給她認識的一個男孩，并且每一個男孩都可以娶一個他認識的女孩。 穩(wěn)定的婚姻問題 ? 這種組合數(shù)學的方法有一個實際的用途：美國的醫(yī)院在確定錄取住院醫(yī)生時，他們將考慮申請者的志愿的先后次序，同時也給申請者排序。 ? 例如 914的模式為： 312 37925 的模式為： 24513 棧排序問題 (Knuth, 1960’s) ? 避免３１２排列 ：一個排列是避免３１２的，當且僅當它的任意子序列中沒有３１２模式。 ? Tutte 從德軍的兩條情報密碼出發(fā)，用組合數(shù)學的方法，重建了敵人的密碼機，確定了德軍密碼的內(nèi)部結(jié)構(gòu)，從而獲得了極為重要的情報。 應用促進理論發(fā)展 ? 36個軍官問題這個純粹來自智力游戲的題目孕育著艱深的數(shù)學問題 。 Fisher的試驗設計是一股巨大的推動力量，把一種數(shù)學游戲變成了節(jié)約人力物力的具有重大價值的科學方法。其本質(zhì)就是如何將一個集合中的元素組合成一定的子集系以滿足一定的要求。 網(wǎng)絡流問題 ? 隨著中國經(jīng)濟快速的增長，城市化是未來中國的發(fā)展方向。 網(wǎng)絡流問題 ? 1956年 Ford 和 Fulkerson 提出了關于網(wǎng)絡流問題的一個重要定理。 網(wǎng)絡可靠性問題 ? 一個通訊網(wǎng)絡怎樣布局穩(wěn)定性最好，而且費用最節(jié)??？ ? 美國的貝爾實驗室和 IBM公司都有世界一流的組合數(shù)學家在研究這個問題，這個問題直接關系到巨大的經(jīng)濟利益。最短新路徑之長 N比原來只連三點的最短路徑 O要短。寄信的規(guī)則很簡單，就是任何收信者只能把信寄給自己熟識的人。asi et ，任意兩個網(wǎng)頁間的鏈接最多為 19次。 ? 如果將基因看作網(wǎng)絡中的頂點，將他們之間的作用看作網(wǎng)絡中的邊，那么每一次大規(guī)模實驗將給我們帶來關于基因交互作用網(wǎng)絡的一些信息。 ? “ 二、九、四；七、五、三；六、一、八 ” 《 大戴禮記 此外，他還構(gòu)造出了五階、六階、七階、八階、九階和十階幻方 (百子圖 )。 楊輝三角 ? 楊輝（南宋）著 《 詳解九章算法 》 (1261年 )中曾引賈憲（北宋）的 “ 開方作法本源 ”圖。s 1303 Identity Implies Bombieri39。sKoRado定理 ? FranklGraham： Erd246。 ? Erd246。 中國郵遞員問題 ? 管梅谷（ 1960）： 郵遞員從郵局出發(fā)送信，要求對轄區(qū)內(nèi)每條街都至少通過一次再回郵局，怎樣選擇一條最短路線 ? ? 現(xiàn)實生活中很多問題可以轉(zhuǎn)化為中國郵遞員問題。 GilbertPollak猜想 ? 1990年，堵丁柱和黃光明合作證明了 GilbertPollak猜想 (1968)。 機器證明 —— 吳消元法 ? 1976年 吳文俊 教授開始進行研究幾何定理的機器證明，并在很短的時間內(nèi)取得重大突破。 ? 吳方法不僅可證明已有的幾何定理，而且可以自動發(fā)現(xiàn)新的定理。 ——當符合要求的安排并非顯然存在或不存在時，首要的問題是證明或否定它的存在 . ——當符合要求的安排顯然存在，或者已證明它存在時，求出這類安排的各抒己見，或者把它分類 . （組合設計） ——把滿足某種條件的安排構(gòu)造出來 . ——給出最優(yōu)標準，找出滿足給定條件的最優(yōu)安排 . 組合數(shù)學的分支 ? 組合分析 ? 代數(shù)組合 ? 極值集論 ? 圖 論 ? 組合設計 ? 組合優(yōu)化 ? 組合算法
教學課件相關推薦
鄂ICP備17016276號-1