[工學(xué)]圖論第01講(編輯修改稿)
2024-11-14 23:51 本頁面
【文章內(nèi)容簡介】 Hamilton）提出了所謂環(huán)球旅行問題： 在正 12面體上的 20個(gè)頂點(diǎn)分別表示 20個(gè)城市，兩點(diǎn)間的連線表示城市間的道路。 要求旅行者從某個(gè)城市出發(fā)，到達(dá)各個(gè)城市一次且僅一次，最后返回出發(fā)城市。 注意！！ 不是所有圖都能 找到這樣的路線！ 三、哈密頓回路問題到貨郎問題 兩個(gè)問題： （ 1）經(jīng)過每個(gè)頂點(diǎn)一次且僅一次； （ 2）代價(jià)最小的 Hamilton回路。 (目前無有效的方法求解 ) 貨郎問題（ Traveling Salesman Problem） 一個(gè)貨郎到各村去賣貨，要求每個(gè)村子至少去一次，最后返回出發(fā)點(diǎn)，為其設(shè)計(jì)一種銷售路線，使總耗時(shí)最短。 求解方法：把路線全排列，求其中最小的。 這類問題稱為 NPC問題。 哈密頓回路和七橋問題的區(qū)別 ? Hamilton回路： 側(cè)重 頂點(diǎn) （一次行遍頂） ； ? 七橋問題： 側(cè)重 邊 （一次行遍橋 /邊） 。 ? 兩者相似，但在難度上不是同一級(jí)別的問題。 四色問題是世界近代三大數(shù)學(xué)難題之一 。 四色問題的內(nèi)容是：任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色 。 它的提出來自英國 。 1852年 ，畢業(yè)于倫敦大學(xué)的弗南西斯 格思里 (Guthrie)發(fā)現(xiàn)了一種有趣的現(xiàn)象： “ 看來 ， 每幅地圖都可以用四種顏色著色 ， 使得有共同邊界的國家都被著上不同的顏色 。 ”這個(gè)現(xiàn)象能不能從數(shù)學(xué)上加以嚴(yán)格證明呢 ？ 三、四色問題 1872年 ， 英國當(dāng)時(shí)最著名的數(shù)學(xué)家凱利正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出了這個(gè)問題 ， 于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問題 。 1878～ 1880年兩年間 ， 著名的律師兼數(shù)學(xué)家 肯普和泰勒 兩人分別提交了證明四色猜想的論文 ， 宣布證明了四色定理 ， 大家都認(rèn)為四色猜想從此也就解決了 。 1890年 ， 在牛津大學(xué)就讀的年僅 29歲的赫伍德以自己的精確計(jì)算指出了 肯普 在證明上的漏洞 。 不久 ，泰勒 的證明也被人們否定了 。 后來 ， 人們開始認(rèn)識(shí)到 ，這個(gè)貌似容易的題目 ， 其實(shí)是一個(gè)可與 費(fèi)馬猜想 相媲美的難題 。 進(jìn)入 20世紀(jì)以來 ， 科學(xué)家們對(duì)四色猜想的證明基本上是按照肯普的想法在進(jìn)行 。 后來美國數(shù)學(xué)家富蘭克林 于 1939年證明了 22國以下的地圖都可以用四色著色 。 1950年 ， 有人從 22國推進(jìn)到 35國 。1960年 ， 有人又證明了 39國以下的地圖可以只用四種顏色著色；隨后又推進(jìn)到了 50國 。 1976年 6月 ， 美國伊利諾大學(xué) 哈肯 與 阿
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1