《圖論及其應用》課程教學大綱

PAGEPAGE4圖論及其應用GraphTheorywithApplications【課程編號】XZ25163【課程類別】專業(yè)限選課【學分數(shù)】3.5【適用專業(yè)】信息與計算科學【適用專業(yè)】信息與計算科學【先修課程】線性代數(shù)、高級語言程序設(shè)計一、教學目的、任務圖論是本科信息與計算科學專業(yè)的限定選修課程，它在運籌學、計算機科學、通信等許多領(lǐng)域有重要應用。圖論是一門概念性和實踐性都很強的專業(yè)基礎(chǔ)課程。它涉及到圖的基本知識，圖論的基本概念、理論、算法及其應用，建立圖的重要矩陣與線性空間，論述計算復雜度理論中的NP完全性問題等方面的內(nèi)容。通過本課程的學習，使學生在掌握圖論知識的基礎(chǔ)上，了解圖論在計算機科學的應用，并能通過把相關(guān)實際問題通過圖論結(jié)構(gòu)來解決問題，并能根據(jù)算法圖論的算法設(shè)計程序解決相關(guān)問題，并為學習其他相關(guān)內(nèi)容奠定良好的算法圖論程序編制基礎(chǔ)。二、課程教學的基本要求本課程主要介紹圖論的基本概念，圖論的經(jīng)典方法，圖論的基本理論，介紹圖論知識在其它課程中的作用和在一些科技領(lǐng)域中的應用。具體要求如下：1、熟練掌握圖、完全圖、二部圖、子圖的基本概念；2、熟練掌握圖的運算、E圖、H圖、連通圖等概念，并能解決一些實際問題；3、熟練掌握樹、生成樹、最優(yōu)樹、割集、連通度、邊連通度等概念，具有用樹的理論解決圖論問題的能力；4、熟練掌握關(guān)聯(lián)矩陣、鄰接矩陣、圈矩陣等概念，理解對同一概念不同表達方式的意義與作用；5、了解平面圖、網(wǎng)絡的理論、了解平面圖的一些研究方法和現(xiàn)實意義；6、了解圖論的基本理論與方法在其它領(lǐng)域內(nèi)的應用，如在計算機科學和經(jīng)濟學等領(lǐng)域中的應用。三、教學內(nèi)容和學時分配（一）第一章圖6學時（課堂講授學時）主要內(nèi)容：(1)圖研究的發(fā)展-哥尼斯堡七橋問題(2)圖的基本概念(3)軌道和圈(4)求最短軌長度的算法教學要求：了解：圖的基本概念理解：最短軌長度的算法其它教學環(huán)節(jié)：實驗設(shè)計:編寫程序?qū)崿F(xiàn)最短軌長度的算法（二）第二章樹10學時（課堂講授學時+課程實驗學時）主要內(nèi)容：(1)樹的定義與性質(zhì)(2)生成樹的個數(shù)(3)求牛成樹的算法(4)求最優(yōu)樹的算法(5)有序二元樹(6)n頂有序編碼二元樹的數(shù)目教學要求：了解：樹在計算機領(lǐng)域中的應用。理解：樹、生成樹、有向樹、根樹、最優(yōu)樹的概念。掌握：最小生成樹的算法，求最優(yōu)樹的算法，前綴碼的求法。其它教學環(huán)節(jié)：實驗設(shè)計:編寫程序?qū)崿F(xiàn)最小生成樹的算法，最優(yōu)樹的算法（三）第三章平面圖6學時（課堂講授學時+課程實驗學時）主要內(nèi)容：(1)平面圖及其平面嵌入(2)平面Euler公式(3)極大平面圖(4)平面圖的充要條件教學要求：理解：平面圖,極大平面圖的概念；平面Euler公式。掌握：平面Euler公式；平面圖的充要條件（四）第四章匹配理論及其應用9學時（課堂講授學時+課程實驗學時）主要內(nèi)容：(1)匹配與許配(2)匹配定理(3)匹配的應用(4)圖的因子分解教學要求：理解：匹配,許配的概念,匹配算法,圖的因子分解的定義。掌握：匹配的算法及其應用,圖的因子分解的求解。其它教學環(huán)節(jié)：實驗設(shè)計:編寫程序?qū)崿F(xiàn)匹配的算法（四）第五章著色理論6學時（課堂講授學時+課程實驗學時）主要內(nèi)容：(1)圖的邊著色(2)圖的頂著色(3)顏色多項式(4)Ramsey數(shù)教學要求：了解：圖的邊著色，圖的頂著色，Ramsey數(shù)的定義理解：圖的邊著色，圖的頂著色，顏色多項式以及Ramsey數(shù)的定義。（五）第六章Euler圖和Hamilton圖4學時（課堂講授學時+課程實驗學時）(1)Euler圖(2)中國郵遞員問題(3)Hamilton圖教學要求：了解：它們在圖論發(fā)展中的作用理解：歐拉回路與歐拉圖、漢密爾頓回路與漢密爾頓圖、平面圖等的概念及性質(zhì)掌握：對歐拉圖、漢密爾頓圖的判定方法（六）第七章有向圖3學時（課堂講授學時+課程實驗學時）(1)弱連通、單連通與強連通(2)循環(huán)賽圖和有向軌教學要求：理解：弱連通、單連通、強連通、循環(huán)賽圖與有向軌的概念掌握：循環(huán)賽圖和有向軌的應用（七）第八章最大流的算法12學時（課堂講授學時+課程實驗學時）(1)2F算法(2)Dinic分層算法(3)有上下界網(wǎng)絡最大流的算法(4)有供需要求的網(wǎng)絡流算法教學要求：理解：最大流與最小流的概念掌握：各種網(wǎng)絡流算法其它教學環(huán)節(jié)：實驗設(shè)計:編寫程序?qū)崿F(xiàn)各種網(wǎng)絡流的算法（八）第九章連通度2學時（課堂講授學時+課程實驗學時）(1)頂連通度(2)邊連通度教學要求：理解與掌握：頂連通度與邊連通度的概念與求解（九）第十章圖的線性空間與矩陣2學時（課堂講授學時+課程實驗學時）(1)圖的線性空間(2)圖的矩陣教學要求：理解：圖的線性空間的概念,圖的各種矩陣表示的概念掌握：圖的表示方法四、教學重點、難點及教學方法教學重點：圖、完全圖、二部圖、子圖的基本概念；圖的運算、E圖、H圖、連通圖等概念；握樹、生成樹、最優(yōu)樹、割集、連通度、邊連通度等概念；網(wǎng)絡的理論及其算法。教學難點：圖各類算法。建議：圖論是一門理論性課程，主要采用講授法、研究探索法講授，講授圖的運算、圖論的應用等內(nèi)容時可以采用多媒體教學。在教學過程中要注意以下幾點：1、講授概念要注意介紹其作用與意義。2、要精講、重點講主要概念與理論，多讓學生思考一些圖論問題，從而培養(yǎng)學生圖論思維方式。3、要注意介紹圖論知識在其它領(lǐng)域中的應用，如在計算機科學、通信等領(lǐng)域中的應用。五、考核方式及成績評定方式閉卷考試;平時30-40%，期末60-70%六、教材及參考書目教