《圖論》課程教學(xué)大綱

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

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

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

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

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

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

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