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