圖論及其應(yīng)用第1頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月主要內(nèi)容圖論前言數(shù)學(xué)預(yù)備知識(shí)第2頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月前言課程目標(biāo)學(xué)時(shí)和學(xué)分教學(xué)大綱教材和主要參考資料課程考核第3頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月圖論學(xué)科簡(jiǎn)介（1）哥尼斯堡七橋問(wèn)題歐拉（1707~1782）：根據(jù)幾何位置的解題方法，這是圖論領(lǐng)域的第一篇論文，1736年，被尊稱為圖論和拓?fù)渲笀D論是組合數(shù)學(xué)的一個(gè)分支，它交叉運(yùn)用了拓?fù)鋵W(xué)、群論、數(shù)論等學(xué)科，有時(shí)將其歸為離散數(shù)學(xué)的一個(gè)分支第4頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月圖論學(xué)科簡(jiǎn)介（2）19世紀(jì)末期，圖論應(yīng)用于電網(wǎng)絡(luò)方程組和有機(jī)化學(xué)中的分子結(jié)構(gòu)20世紀(jì)中葉，由于計(jì)算機(jī)的發(fā)展，圖論用來(lái)求解生產(chǎn)管理、軍事、交通運(yùn)輸、計(jì)算機(jī)和網(wǎng)絡(luò)通信等領(lǐng)域中的離散性問(wèn)題物理學(xué)、化學(xué)、運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、電子學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、社會(huì)科學(xué)、管理科學(xué)等領(lǐng)域應(yīng)用第5頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月課程目標(biāo)通過(guò)本課程學(xué)習(xí)，要求學(xué)生掌握?qǐng)D論的基本理論及推理方法，為通信網(wǎng)絡(luò)、電路輔助設(shè)計(jì)、信息工程、密碼學(xué)等打下理論基礎(chǔ)。掌握?qǐng)D論的基本理論與基本方法，并用這些理論與方法解決一些實(shí)際問(wèn)題，了解圖論在現(xiàn)代信息科學(xué)和現(xiàn)代通信系統(tǒng)中的應(yīng)用。本課程特別強(qiáng)調(diào)理論與工程實(shí)踐相結(jié)合，以提高學(xué)生的學(xué)習(xí)知識(shí)、運(yùn)用知識(shí)能力。第6頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月學(xué)時(shí)和學(xué)分學(xué)時(shí)數(shù)

54學(xué)分?jǐn)?shù)

3第7頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月教學(xué)大綱（共11章）通過(guò)教學(xué)，使學(xué)生掌握該課程的基本理論與方法，培養(yǎng)對(duì)離散對(duì)象的抽象思維與解決實(shí)際問(wèn)題的能力，并為學(xué)習(xí)相關(guān)課程及將來(lái)從事科學(xué)研究創(chuàng)新和工程實(shí)踐奠定理論基礎(chǔ)，及培養(yǎng)學(xué)生理論與實(shí)踐相結(jié)合的能力。第8頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月第一章圖的基本概念圖和簡(jiǎn)單圖同構(gòu)子圖頂點(diǎn)的度路和連通性圈最短路問(wèn)題第9頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月第二章樹(shù)樹(shù)割邊和鍵割點(diǎn)連線問(wèn)題第10頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月第三章連通度連通度塊可靠通信網(wǎng)建設(shè)問(wèn)題第11頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月第四章Euler環(huán)游和Hamilton圈Euler環(huán)游Hamilton圈旅行售貨員問(wèn)題第12頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月第五章匹配匹配偶圖的匹配和覆蓋完美匹配人員分派問(wèn)題最優(yōu)匹配問(wèn)題第13頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月第六章著色問(wèn)題邊色數(shù)Vizing定理點(diǎn)著色 色數(shù)Brooks定理圍長(zhǎng)和色數(shù)第14頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月第七章平面圖平圖和平面圖對(duì)偶圖Euler公式Kuratowski定理五色定理和四色猜想平面性算法第15頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月第八章有向圖有向圖有向路有向圈第16頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月第九章網(wǎng)絡(luò)流割最大流最小割定理Menger定理

第17頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月第十章NP–完全問(wèn)題

優(yōu)化問(wèn)題

P類和NP類

Cook定理六個(gè)基本NPC問(wèn)題第18頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月第十一章圖論的應(yīng)用圖論在現(xiàn)代網(wǎng)絡(luò)設(shè)計(jì)和流量分析中的應(yīng)用圖論在信息安全中的應(yīng)用圖論在信號(hào)處理中的應(yīng)用第19頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月教材和主要參考資料（1）《圖論及其應(yīng)用》，孫惠泉，科學(xué)出版社，2004年9月。

《圖論導(dǎo)引》，DouglasB.West著，李建中、駱吉洲譯，機(jī)械工業(yè)出版社，2006年2月?！秷D論簡(jiǎn)明教程》，F(xiàn)redBuckley,MartyLewinter著，李慧霸、王鳳芹譯，清華大學(xué)出版社，2005年1月。第20頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月教材和主要參考資料（2）《圖論及其應(yīng)用》，J.A.邦迪及U.S.R默蒂，科學(xué)出版社。（原書(shū)：GraphTheorywithApplications,J.A.Bondy&U.S.R.Murty)IntroductiontoGraphTheory,SecondEdition,DouglasB.West.AFriendlyIntroductiontoGraphTheory,FredBuckley,MartyLewinter.第21頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月學(xué)習(xí)方法目的明確態(tài)度端正理論和實(shí)踐相結(jié)合充分利用資源逐步實(shí)現(xiàn)從知識(shí)到能力到素質(zhì)的深化和升華第22頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月課程考核平時(shí)成績(jī)（10%）圖論應(yīng)用的小論文（60%）開(kāi)卷考試（30%）第23頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月幾點(diǎn)建議做人：厚德博學(xué)敬業(yè)樂(lè)群讀書(shū)：博與精薄與厚創(chuàng)新：IPR(IntellectualPropertyRights)職業(yè)定位：CEO、CTO、CFO、首席科學(xué)家、董事長(zhǎng)技術(shù)管理？技術(shù)專家理想與價(jià)值體現(xiàn)：修身、齊家、治國(guó)、平天下個(gè)人價(jià)值？社會(huì)價(jià)值身心健康，全面發(fā)展：IQ、EQ、AQ第24頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月網(wǎng)上資源：標(biāo)準(zhǔn)/home/index.html

/

/////wireless//

//

第25頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月網(wǎng)上資源：文章、論文、圖書(shū)IEE,IEEE,IEICE/

SCI,EIVillage///第26頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月網(wǎng)上資源：專利////http://www.jpo.go.jp/第27頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月北京九章圖書(shū)有限公司/北京海淀西大街31號(hào)海淀圖書(shū)城籍海樓二層北京九章圖書(shū)有限公司郵編：100080

電話：（010）62639894、62539135、62559881（均可收傳真）

E-mail:

chaoh@第28頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月名人名言智者，善假于物也學(xué)貴有恒，人貴有志貴我、通今：橫盡虛空，山河大地?zé)o一可恃，可恃惟我；數(shù)盡來(lái)劫，前后左右無(wú)一可據(jù)，可據(jù)惟今！生當(dāng)作人杰，死亦為鬼雄！第29頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月一副對(duì)聯(lián)、一句勉勵(lì)上聯(lián)：做人做事做第一下聯(lián)：創(chuàng)新創(chuàng)業(yè)創(chuàng)世界橫批：眾志成城千里之行，始于足下，興趣是最好的老師，將興趣升華為愛(ài)好，將愛(ài)好升華為技能，將技能升華為素質(zhì)，將素質(zhì)升華為成功。。。。。。第30頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月數(shù)學(xué)預(yù)備知識(shí)集合論數(shù)理邏輯歸納法原理組合分析與計(jì)數(shù)鴿巢原理（鴿舍原理、抽屜原理）等價(jià)關(guān)系與同余第31頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月集合論

自然數(shù)集、整數(shù)集、有理數(shù)集、實(shí)數(shù)集并集，交集，差集，補(bǔ)集，對(duì)稱差集集合的計(jì)數(shù)：cardA=n自然數(shù)集的計(jì)數(shù)：實(shí)數(shù)集的計(jì)數(shù)：第32頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月數(shù)理邏輯（1）全稱量詞存在量詞否定合取析取條件命題雙條件命題第33頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月數(shù)理邏輯（2）條件命題逆命題逆否命題：第34頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月數(shù)理邏輯（3）雙條件命題第35頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月引理、定理、推論引理（lemma):希臘語(yǔ)意為前提定理(theorem):希臘語(yǔ)意為待證的論題推論(corollary):拉丁語(yǔ)，意為贈(zèng)品，是從定理或命題出發(fā)無(wú)需太多額外工作即可得出的論斷第36頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

歸納法原理一

對(duì)每個(gè)自然數(shù)，設(shè)P(n)是一個(gè)數(shù)學(xué)命題。如果下面的性質(zhì)a和b成立，則P(n)對(duì)每個(gè)自然數(shù)n均為真a)P(1)為真；b)對(duì)于，如果P(k)為真，則P(k+1)為真；第37頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月歸納法原理二對(duì)每個(gè)自然數(shù)，設(shè)P(n)是一個(gè)數(shù)學(xué)命題。如果下面的性質(zhì)a和b成立，則P(n)對(duì)每個(gè)自然數(shù)n均為真a)P(1)為真；b)對(duì)于，如果對(duì)所有P(t)為真，則P(k+1)為真；第38頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月組合分析與計(jì)數(shù)映射雙射冪集、子集的個(gè)數(shù)計(jì)數(shù)第39頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月鴿巢原理（鴿舍原理、抽屜原理）平均值總是介于最大值和最小值之間如果對(duì)象多于kn的一個(gè)集合被劃分為n個(gè)類，則必有一個(gè)包含的對(duì)象多于k個(gè)第40頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月等價(jià)關(guān)系與同余（1）集合S上的一個(gè)