圖論及其應(yīng)用

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

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

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

第十七頁，共四十三頁，編輯于2023年，星期五第十章NP–完全問題

優(yōu)化問題

P類和NP類

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

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

/

/////wireless//

//

第二十五頁，共四十三頁，編輯于2023年，星期五網(wǎng)上資源：文章、論文、圖書IEE,IEEE,IEICE/

SCI,EIVillage///第二十六頁，共四十三頁，編輯于2023年，星期五網(wǎng)上資源：專利////http://www.jpo.go.jp/第二十七頁，共四十三頁，編輯于2023年，星期五北京九章圖書有限公司/北京海淀西大街31號(hào)海淀圖書城籍海樓二層北京九章圖書有限公司郵編：100080

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

E-mail:

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

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

歸納法原理一

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