《淺談組合數(shù)學(xué)》ppt課件-全文預(yù)覽
【正文】 ， 使得集合{1， 2， … ， N}的每一個(gè) σ N 長(zhǎng)的子集都包含 k 長(zhǎng)的等差級(jí)數(shù)。asi et ，任意兩個(gè)網(wǎng)頁(yè)間的鏈接最多為 19次。寄信的規(guī)則很簡(jiǎn)單，就是任何收信者只能把信寄給自己熟識(shí)的人。 ? 在 《 不列顛百科全書(shū) 1992年鑒 》 的數(shù)學(xué)評(píng)論中，該成果被列為世界上當(dāng)年六項(xiàng)數(shù)學(xué)成果首項(xiàng)。這使得貝爾公司不僅要拉新線，增加服務(wù)網(wǎng)點(diǎn)，而且還要減少收費(fèi)。 23Pollak－ Gilbert猜想 ? Pollak－ Gilbert猜想 起源于在美國(guó)貝爾電話公司發(fā)生的一個(gè)富有戲劇性的事件。 ? 如果不允許增加任何額外的點(diǎn)作為網(wǎng)絡(luò)的頂點(diǎn)，這種最短網(wǎng)絡(luò)稱為 最小生成樹(shù) 。 ? 這樣得到的網(wǎng)絡(luò)不僅比原來(lái)節(jié)省材料，而且穩(wěn)定性也更好。 最短網(wǎng)絡(luò)問(wèn)題 ? 如何用最短的線路將三部電話連起來(lái)？ ? 此問(wèn)題可抽象為設(shè)△ ABC為等邊三角形，連接三頂點(diǎn)的路線（稱為網(wǎng)絡(luò)）。 最小全一問(wèn)題 ? 求操作次數(shù)最少的解稱為 最小全一問(wèn)題 。 棧排序問(wèn)題 (Knuth, 1960’s) ? 模式 : 對(duì)任意一個(gè)排列 π , 最小的元素用１代替，次小的元素用２代替 …… 以此類推，這樣得到的排列叫 π的模式。 ? 用圖論匹配理論中 GaleShapley算法，可以找到一種婚姻的安排方法，使得沒(méi)有上述的不穩(wěn)定情況出現(xiàn)。 ? 1970年， Edmonds和 Karp 對(duì)標(biāo)號(hào)程序加以改進(jìn)，使之成為一個(gè)好的算法 。這就是一個(gè)網(wǎng)絡(luò)最大流問(wèn)題。 ? 吳文俊教授還將其方法推廣到微分幾何定理的機(jī)器證明上。此兩步中，一般第二步更為困難。s和 Szekeres） ：若 a, b ∈ N，n=ab+1，且 x1, … , x n是任一 n個(gè)實(shí)數(shù)的序列，則這個(gè)序列包含一個(gè)有 a+1項(xiàng)的單調(diào)遞增（遞減）的子序列，或一個(gè)有 b+1項(xiàng)的單調(diào)遞減（遞增）的子序列。 Erd246。 ? 用 6個(gè)頂點(diǎn)表示 6個(gè)人，用紅色連線表示兩者相識(shí)，用藍(lán)色連線表示兩者不相識(shí)。 ?? )(\)( *)(GEGEeew貨郎擔(dān)問(wèn)題 ? 一個(gè)貨郎要去若干城鎮(zhèn)賣(mài)貨，然后回到出發(fā)地，給定各城鎮(zhèn)之間所需的旅行時(shí)間后，應(yīng)怎樣計(jì)劃他的路線，使他能去每個(gè)城鎮(zhèn)恰好一次而且總時(shí)間最短？ 貨郎擔(dān)問(wèn)題 ? 用圖論的術(shù)語(yǔ)說(shuō)，就是在一個(gè)賦權(quán)完全圖中，找出一個(gè)具有最小權(quán)的 Hamilton 圈（包含圖 G的每個(gè)頂點(diǎn)的圈 )。那么如何選擇一條盡可能短的路線。 ? 此后數(shù)學(xué)家 Heawood 花費(fèi)了畢生的精力致力于四色研究，于 1890年證明了五色定理（ 每個(gè)平面圖都是 5頂點(diǎn)可著色的 ）。 四色問(wèn)題 ? 在日常生活中我們常?？梢杂龅浇M合數(shù)學(xué)的問(wèn)題。 ? Tutte 從德軍的兩條情報(bào)密碼出發(fā)，用組合數(shù)學(xué)的方法，重建了敵人的密碼機(jī)，確定了德軍密碼的內(nèi)部結(jié)構(gòu)，從而獲得了極為重要的情報(bào)。 K246。nigsberg城的七座橋，要求每座橋通過(guò)一次且僅通過(guò)一次。這在現(xiàn)在被稱為 tiling問(wèn)題。 上圖為三階洛書(shū) 幻方問(wèn)題 ? 組合數(shù)學(xué)中有許多象幻方這樣精巧的結(jié)構(gòu)。 組合數(shù)學(xué)概述 ? 吳文俊 院士指出，每個(gè)時(shí)代都有它特殊的要求，使得數(shù)學(xué)出現(xiàn)一個(gè)新的面貌，產(chǎn)生一些新的數(shù)學(xué)分支，組合數(shù)學(xué)這個(gè)新的分支也是在時(shí)代的要求下產(chǎn)生的。 ? 計(jì)算機(jī)出現(xiàn)以后，由于離散對(duì)象的處理是計(jì)算機(jī)科學(xué)的核心，研究離散對(duì)象的組合數(shù)學(xué)得到迅猛發(fā)展 。 組合數(shù)學(xué)的歷史 ? 傳說(shuō)在公元前 23世紀(jì)大禹治水的時(shí)候，在黃河支流洛水中，浮現(xiàn)出一個(gè) 大烏龜，甲上背有 9種花點(diǎn)的圖案，人們將圖案中的花點(diǎn)數(shù)了一下，競(jìng)驚奇地發(fā)現(xiàn) 9種花點(diǎn)數(shù)正巧是 1—9這 9個(gè)數(shù)，各數(shù)位置的排列也相當(dāng)奇妙，橫的 3行、縱的 3列以及兩對(duì)角線上各自的數(shù)字之和都為 15。 阿基米德手稿 ? 在論文中阿基米德是在計(jì)算把 14條不規(guī)則的
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1