1、圖論及其應(yīng)用Graph Theory and Its Applications,主要內(nèi)容,圖論前言 數(shù)學(xué)預(yù)備知識(shí),前言,課程目標(biāo) 學(xué)時(shí)和學(xué)分 教學(xué)大綱 教材和主要參考資料 課程考核,圖論學(xué)科簡介 （1）,哥尼斯堡七橋問題 歐拉（17071782）：根據(jù)幾何位置的解題方法，這是圖論領(lǐng)域的第一篇論文，1736年， 被尊稱為圖論和拓?fù)渲?圖論是組合數(shù)學(xué)的一個(gè)分支，它交叉運(yùn)用了拓?fù)鋵W(xué)、群論、數(shù)論等學(xué)科，有時(shí)將其歸為離散數(shù)學(xué)的一個(gè)分支,圖論學(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ò)通信

2、等領(lǐng)域中的離散性問題 物理學(xué)、化學(xué)、運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、電子學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、社會(huì)科學(xué)、管理科學(xué)等領(lǐng)域應(yīng)用,課程目標(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í)能力。,學(xué)時(shí)和學(xué)分,學(xué)時(shí)數(shù) 54 學(xué)分?jǐn)?shù) 3,教學(xué)大綱 （共11章）,通過教學(xué)，使學(xué)生掌握該課程的基本理論與方法，培養(yǎng)對離散對象的抽象思維與解決實(shí)際問題的能力，并為學(xué)習(xí)相關(guān)課程及

3、將來從事科學(xué)研究創(chuàng)新和工程實(shí)踐奠定理論基礎(chǔ)，及培養(yǎng)學(xué)生理論與實(shí)踐相結(jié)合的能力。,第一章 圖的基本概念,圖和簡單圖 同構(gòu) 子圖 頂點(diǎn)的度 路和連通性 圈 最短路問題,第二章 樹,樹 割邊和鍵 割點(diǎn) 連線問題,第三章 連通度,連通度 塊 可靠通信網(wǎng)建設(shè)問題,第四章 Euler環(huán)游和Hamilton圈,Euler環(huán)游 Hamilton圈 旅行售貨員問題,第五章 匹配,匹配 偶圖的匹配和覆蓋 完美匹配 人員分派問題 最優(yōu)匹配問題,第六章 著色問題,邊色數(shù) Vizing定理 點(diǎn)著色 色數(shù) Brooks定理 圍長和色數(shù),第七章 平面圖,平圖和平面圖 對偶圖 Euler公式 Kuratowski定理 五色定

4、理和四色猜想 平面性算法,第八章 有向圖,有向圖 有向路 有向圈,第九章 網(wǎng)絡(luò),流 割 最大流最小割定理 Menger定理,第十章 NP 完全問題,優(yōu)化問題 P類和NP類 Cook定理 六個(gè)基本NPC問題,第十一章 圖論的應(yīng)用,圖論在現(xiàn)代網(wǎng)絡(luò)設(shè)計(jì)和流量分析中的應(yīng)用 圖論在信息安全中的應(yīng)用 圖論在信號(hào)處理中的應(yīng)用,教材和主要參考資料 （1）,圖論及其應(yīng)用，孫惠泉，科學(xué)出版社，2004年9月。 圖論導(dǎo)引，Douglas B.West 著，李建中、駱吉洲譯，機(jī)械工業(yè)出版社，2006年2月。 圖論簡明教程，F(xiàn)red Buckley,Marty Lewinter 著，李慧霸、王鳳芹譯，清華大學(xué)出版社，2

5、005年1月。,教材和主要參考資料 （2）,圖論及其應(yīng)用，J.A. 邦迪 及 U.S.R 默蒂，科學(xué)出版社。 （原書：Graph Theory with Applications, J.A. Bondy & U.S.R. Murty) Introduction to Graph Theory, Second Edition , Douglas B. West. A Friendly Introduction to Graph Theory, Fred Buckley,Marty Lewinter.,學(xué)習(xí)方法,目的明確 態(tài)度端正 理論和實(shí)踐相結(jié)合 充分利用資源 逐步實(shí)現(xiàn)從知識(shí)到能力到素質(zhì)的深化和

6、升華,課程考核,平時(shí)成績 （10%） 圖論應(yīng)用的小論文 （60%） 開卷考試 （30%）,幾點(diǎn)建議,做人：厚德博學(xué) 敬業(yè)樂群 讀書：博與精 薄與厚 創(chuàng)新：IPR (Intellectual Property Rights) 職業(yè)定位：CEO、CTO、CFO、 首席科學(xué)家、 董事長 技術(shù)管理？技術(shù)專家 理想與價(jià)值體現(xiàn)：修身、齊家、治國、 平天下 個(gè)人價(jià)值？社會(huì)價(jià)值 身心健康，全面發(fā)展：IQ、EQ、AQ,網(wǎng)上資源：標(biāo)準(zhǔn),/home/index.html / / http:/www.etsi.

7、org/ / /wireless/ / / /,網(wǎng)上資源：文章、論文、圖書,IEE,IEEE,IEICE / SCI,EI Village ,網(wǎng)上資源：專利, / / / http:/www.jpo.go.jp/,

8、北京九章圖書有限公司, 北京海淀西大街31號(hào) 海淀圖書城 籍海樓二層 北京九章圖書有限公司 郵編： 100080電話：（010） 62639894、62539135、62559881 （均可收傳真）E-mail:,名人名言,智者，善假于物也 學(xué)貴有恒，人貴有志 貴我、通今：橫盡虛空，山河大地?zé)o一可恃，可恃惟我；數(shù)盡來劫，前后左右無一可據(jù)，可據(jù)惟今！ 生當(dāng)作人杰，死亦為鬼雄！,一副對聯(lián)、一句勉勵(lì),上聯(lián)： 做人做事做第一 下聯(lián)： 創(chuàng)新創(chuàng)業(yè)創(chuàng)世界 橫批： 眾志成城 千里之行，始于足下， 興趣是最好的老師，將興趣升華為愛好，將愛好升華為技能，將技能升華為素質(zhì)，將素質(zhì)升華為成功。,數(shù)學(xué)預(yù)備知識(shí),集合論

9、數(shù)理邏輯 歸納法原理 組合分析與計(jì)數(shù) 鴿巢原理（鴿舍原理、抽屜原理） 等價(jià)關(guān)系與同余,集合論,自然數(shù)集、整數(shù)集、有理數(shù)集、實(shí)數(shù)集 并集，交集，差集，補(bǔ)集，對稱差集 集合的計(jì)數(shù)：card A=n 自然數(shù)集的計(jì)數(shù)： 實(shí)數(shù)集的計(jì)數(shù)：,數(shù)理邏輯 （1）,全稱量詞 存在量詞 否定 合取 析取 條件命題 雙條件命題,數(shù)理邏輯 （2）,條件命題 逆命題 逆否命題：,數(shù)理邏輯 （3）,雙條件命題,引理、定理、推論,引理（lemma) : 希臘語意為前提 定理 (theorem):希臘語意為待證的論題 推論 (corollary): 拉丁語，意為贈(zèng)品，是從定理或命題出發(fā)無需太多額外工作即可得出的論斷,歸納法原理一,對每個(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)為真；,歸納法原理二,對每個(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)為真；,組合分析與計(jì)數(shù),映射 雙射 冪集、子集的個(gè)數(shù)計(jì)數(shù),鴿巢原理（鴿舍原理、抽屜原理）,平均值總是介于最大值和最小值之間 如果對象多于kn的一個(gè)集合被劃分為n個(gè)類，