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

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

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

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

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

5、學(xué)生體會(huì)到事物是普遍聯(lián)系的。4. 歐拉環(huán)游與哈密爾頓圈課程目標(biāo)1、2、3、4歐拉環(huán)游哈密爾頓圈掌握歐拉圖定義及判定定理掌握哈密頓圖的定義及判定的一些條件了解此兩類圖的歷史背景及實(shí)際中的一些應(yīng)用1.課堂教學(xué)6學(xué)時(shí)課程思政：通過本章學(xué)習(xí)，能讓學(xué)生弄清歐拉環(huán)游和哈密爾頓問題的發(fā)展歷史，激發(fā)學(xué)生的文化自信與民族自豪感，培養(yǎng)學(xué)生的嚴(yán)謹(jǐn)思維。5. 對(duì)集課程目標(biāo)1、2、4對(duì)集偶圖的對(duì)集與覆蓋完美對(duì)集掌握對(duì)集的概念針對(duì)二部圖的定義，掌握二部圖匹配的特征了解完美匹配問題的充分必要條件1.課堂教學(xué)4學(xué)時(shí)課程思政：匹配理論在現(xiàn)實(shí)生活中有很強(qiáng)的實(shí)際背景和應(yīng)用價(jià)值。通過本章學(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é)時(shí)課程思政：了解圖的著色理論，可以讓學(xué)生理解從一般到特殊的數(shù)學(xué)抽象概括能力。激發(fā)學(xué)生的求知欲與對(duì)數(shù)學(xué)家的敬仰之情，培養(yǎng)學(xué)生的探究精神與創(chuàng)新思維。8. 頂點(diǎn)著色課程目標(biāo)1、2、4色數(shù)色多項(xiàng)式知道頂點(diǎn)著色的相關(guān)概念及重要結(jié)論會(huì)求著色多項(xiàng)式1.課堂教學(xué)2.課堂討論4學(xué)時(shí)課程思政：了解圖的著色理論，可以讓學(xué)生理解從一般到特殊的數(shù)學(xué)抽象概括能力。激發(fā)學(xué)生的求知欲與對(duì)數(shù)學(xué)家的敬仰之情，培養(yǎng)學(xué)生的探究精神與創(chuàng)新思維。9. 平面圖課程目標(biāo)1、2、4平面圖對(duì)偶圖歐拉

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