《圖論》課程教學大綱

1、圖論課程教學大綱 一、課程信息課程名稱（COURSE TITLE）圖論課程性質（COURSE CHARACTER）專業(yè)選修課（考查）課程代碼（COURSE CODE）316B1009學分（CREDIT）2學時（CONTACT HOURS）32先修課程（PRE-COURSE）中學數學 計算機及程序設計課程負責人（COURSE COORDINATOR）適用專業(yè)數學與應用數學（師范）課程簡介：圖論是數學中一個既古老又年輕的分支。歐拉1736年關于哥尼斯堡七橋問題的論文標志著圖論的誕生。近幾十年來，由于運籌學、計算科學等學科的促進，圖論正經歷著一個蓬勃發(fā)展的時期，它在計算機科學、運籌學、電網絡分析、化

2、學、物理學以及社會科學等方面已取得豐富的成果。 圖論具有直觀、清晰、易懂的特點，技巧性較強，有廣泛的應用。通過本課程的學習，要求學生了解或掌握路和圈、樹、平面圖、匹配、圖染色等方面的基本概念、基本理論和基本方法。加強學生的感性與理性認識，培養(yǎng)學生理論聯(lián)系實際，分析和解決問題的能力。二、課程目標通過本課程的學習，學生應具備以下幾方面的目標：1.通過本課程學習，學生掌握圖論的基本概念、基本理論和基本方法，具備解決圖論問題的基本知識的能力。2.通過本課程學習，學生理解圖論的思想方法，提高分析問題和解決問題的能力，從而培養(yǎng)學生的數學素養(yǎng)。3.通過本課程學習，學生能夠掌握圖論問題分析與論證技巧，解決實際

3、中的問題。4.通過本課程學習，學生具備處理中學教學中的相關問題的能力，具有終身學習和職業(yè)發(fā)展意識。畢業(yè)要求畢業(yè)要求指標點課程目標1課程目標2課程目標3課程目標4畢業(yè)要求3畢業(yè)要求指標點3.2MMLL畢業(yè)要求4畢業(yè)要求指標點4.1LLLL課程目標對畢業(yè)要求的支撐關系表三、教學內容與預期學習成效知識單元對應課程目標知識點預期學習成效實現環(huán)節(jié)學時1. 圖與子圖課程目標1、2、31.圖與簡單圖2.圖的同構3.關聯(lián)與鄰接矩陣4.子圖5.頂點度6.路和連通7.圈1.掌握圖與子圖的相關概念2.掌握圖的相關度、關聯(lián)鄰接陣、同構相關概念3.知道圖的頂點與邊的一些關聯(lián)關系1.課堂教學2.課堂討論6學時課程思政：通

4、過對圖論的基本概念的介紹，讓學生了解具體到抽象的變化，從而體會到數學的魅力，引發(fā)學生借助數學方法描述和解決實際生活中具體問題的興趣。2. 樹課程目標1、2、3樹割邊與鍵Cayley公式掌握樹的基本概念和基本結論知曉割邊的概念及相關結論了解鍵、Cayley公式的定義，并會計算生成樹1.課堂教學4學時課程思政：樹是一類最小連通圖，具有一些較好的性質，在圖論中具有特殊的地位。通過本章學習，能讓學生弄清楚簡單與復雜之間的辯證關系。3. 連通度課程目標1、2連通性塊熟練判斷一個圖的頂點與邊連通度了解塊的定義及塊的思想1.課堂教學2學時課程思政：通過本章學習，能讓學生弄清楚一個圖的頂點與邊連通度的關系，讓

5、學生體會到事物是普遍聯(lián)系的。4. 歐拉環(huán)游與哈密爾頓圈課程目標1、2、3、4歐拉環(huán)游哈密爾頓圈掌握歐拉圖定義及判定定理掌握哈密頓圖的定義及判定的一些條件了解此兩類圖的歷史背景及實際中的一些應用1.課堂教學6學時課程思政：通過本章學習，能讓學生弄清歐拉環(huán)游和哈密爾頓問題的發(fā)展歷史，激發(fā)學生的文化自信與民族自豪感，培養(yǎng)學生的嚴謹思維。5. 對集課程目標1、2、4對集偶圖的對集與覆蓋完美對集掌握對集的概念針對二部圖的定義，掌握二部圖匹配的特征了解完美匹配問題的充分必要條件1.課堂教學4學時課程思政：匹配理論在現實生活中有很強的實際背景和應用價值。通過本章學習，培養(yǎng)學生的創(chuàng)新思維能力。6. 邊著色課程

6、目標1、2邊著色數Vizing定理了解圖的色類與邊著色的相關概念與著色的思想了解Vizing定理中的關于邊色數的相關結構1.課堂教學2.課堂討論2學時課程思政：了解圖的著色理論，可以讓學生理解從一般到特殊的數學抽象概括能力。激發(fā)學生的求知欲與對數學家的敬仰之情，培養(yǎng)學生的探究精神與創(chuàng)新思維。8. 頂點著色課程目標1、2、4色數色多項式知道頂點著色的相關概念及重要結論會求著色多項式1.課堂教學2.課堂討論4學時課程思政：了解圖的著色理論，可以讓學生理解從一般到特殊的數學抽象概括能力。激發(fā)學生的求知欲與對數學家的敬仰之情，培養(yǎng)學生的探究精神與創(chuàng)新思維。9. 平面圖課程目標1、2、4平面圖對偶圖歐拉

7、公式掌握平面圖的定義及其特殊圖的判斷方法了解對偶圖定義，會計算一個圖的面會證明歐拉公式，了解其在平面圖著色中的作用1.課堂教學4學時課程思政：平面理論的歷史發(fā)展，凸顯了數學的內在美和和諧美，讓學生充分認識數學對社會的作用。成績評定及考核方式知識單元對應課程目標考核方式成績評定1、 圖與子圖課程目標1、2、4平時表現+課堂訓練+學期總結成績評定方法如下： （1）平時作業(yè)依據作業(yè)態(tài)度，占總學期成績的10%； （2）平時表現依據課堂的積極性，是否玩手機，聽課態(tài)度，考勤等占總學期成績的40%； （3）筆記學期結束上交，依據其記錄的態(tài)度、完整性，占總學期成績的20%。（4） 學期總結（可就某課題綜述，或測試）占30%2、樹課程目標1、2、3平時表現+課堂訓練+學期總結3、連通度課程目標1、2平時表現+課堂訓練+學期總結4、歐拉環(huán)游與哈密爾頓圈課程目標1、2、4平時表現+課堂訓練+學期總結5、對集課程目標1、2平時表現+課堂訓練+學期總結6、邊著色課程目標1、2、4平時表現+課堂訓練+學期總結8、頂點著色課程目標1、2、4平時表現+課堂訓練+學期總結9、平面圖課程目標1、2平時表現+課堂訓練+學期總結五、課程建議教材及主要參考資料1. 建議教材 J.A.