圖論及其應(yīng)用

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

54學(xué)分數(shù)

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

第十七頁，共四十三頁，2022年，8月28日第十章NP–完全問題

優(yōu)化問題

P類和NP類

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

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

/

第二十五頁，共四十三頁，2022年，8月28日網(wǎng)上資源：文章、論文、圖書IEE,IEEE,IEICE

SCI,EIVillage第二十六頁，共四十三頁，2022年，8月28日網(wǎng)上資源：專利第二十七頁，共四十三頁，2022年，8月28日北京九章圖書有限公司北京海淀西大街31號海淀圖書城籍海樓二層北京九章圖書有限公司郵編：100080

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

E-mail:

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

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

歸納法原理一

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