圖論及其應用(精)

1、圖論及其應用學時：40學分：2課程屬性：專業(yè)選修課開課單位：理學院先修課程：高等代數(shù)后續(xù)課程：無一、課程的性質(zhì)圖論及其應用是數(shù)學與應用數(shù)學專業(yè)的專業(yè)選修課程。二、教學目的通過教學，使學生掌握圖論及其算法的基本理論和基本技巧，初步掌握圖論及其算法的基本應 用手段、基本算法設計及編程，并能用所學理論解決一些應用問題。三、教學內(nèi)容1.圖的基本概念2.圖的連通性3.樹的基本性質(zhì)及其應用4.Euler Graphs and Hamilt on Graphs with Applicati ons5.平面圖性質(zhì)6.匹配，求最大匹配算法及應用7.圖的染色及應用8.極圖理論四、學時分配早課程內(nèi)容學時1圖的基本概

2、念42圖的連通性63樹的基本性質(zhì)及其應用64Euler Graphs and Hamilt on Graphs with Applicati ons45平面圖性質(zhì)66匹配，求最大匹配算法及應用6圖的染色及應用8極圖理論合計40五、教學方式本課程采用多媒體課堂講授，結(jié)合實際范例深入淺出講解討論。六、考核方式本課程考核采用平時與期末考核相結(jié)合的辦法，特別注重平時的考核，作業(yè)采用簡單練習、論 文等形式，期末考試采用簡單考題或論文形式。七、教材及教學參考書參考教材：1 J.A.Bondy and U.S.R.Murty. Graph Theory with Applications, The Macm

3、illan Press LTD,1976.2蔣長浩.圖論與網(wǎng)絡流.北京：中國林業(yè)出版社，2000.參考書目：1 Bela Bollobas.Modern Graph Theory（現(xiàn)代圖論，影印版）.北京：科學出版社，2001.2殷劍宏、吳開亞.圖論及其算法.合肥：中國科學技術(shù)大學出版社，2003.3謝金星、邢文訓.網(wǎng)絡優(yōu)化.北京：清華大學出版社.2000.4程理民、吳江、張玉林.運籌學模型與方法教程.北京：清華大學出版社，2000.5三味工作室.SPSS V10.0 for Windows實用基礎教程.北京：北京希望電子出版社2001.6孫魁明、張海彤.Mathematica工具軟件大全.北

4、京：中國鐵道出版社，1994.7樓順天、于衛(wèi)、閆華梁.MATLAB程序設計語言.西安：西安電子科技大學出版社，1997.八、教學基本內(nèi)容及要求第一章圖的基本概念1.教學基本要求掌握的圖的基本概念、特殊圖概念，了解最短路問題。2.教學具體內(nèi)容圖的基本概念，路和圈，最短路問題。重點：圖的概念；難點：最短路問題。第二章 圖的連通性 1教學基本要求掌握割點、橋、塊、連通度等概念，并了解連通圖的基本特征。2教學具體內(nèi)容割點、橋和塊，連通圖。 重點：連通度、連通圖等；難點：連通圖的特征描述。第三章 樹的基本性質(zhì)及其應用 1教學基本要求掌握樹的基本性質(zhì)、Cayley公式等，了解連線問題、圖的無圈子圖分解等。

5、2教學具體內(nèi)容樹的基本性質(zhì)，Cayley公式，連線問題，圖的無圈子圖分解。 重點：樹的基本性質(zhì)；難點：連線問題及無圈子圖分解。第四章 Euler Graphs and Hamilton Graphs with Applications 1教學基本要求掌握Euler圖、Hamilton圖等概念，了解中國郵遞員問題。2教學具體內(nèi)容Euler圖，Hamilton圖，中國郵遞員問題。重點：Euler圖、Hamilton圖；難點：應用。第五章 平面圖性質(zhì) 1教學基本要求掌握Euler公式，了解平面圖特征、不可平面圖特征。2教學具體內(nèi)容Euler公式，平面圖特征，不可平面圖。重點：Euler公式、平面圖特征；難點：平面圖特征、不可平面圖。第六章 匹配，求最大匹配算法及應用1教學基本要求掌握匹配、最大匹配、覆蓋等概念，掌握最大匹配算法及應用。2教學具體內(nèi)容匹配，最大匹配的算法，覆蓋，圖的支配集。 重點：匹配、最大匹配；難點：最大匹配算法。第七章 圖的染色及應用1教學基本要求掌握頂點染色、邊染色、面染色等概念，并能簡單應用。2教學具體內(nèi)容頂點染色，邊染色，面染色。重點：頂點染色；難點：