上海交通大學 圖與網絡 普通話 簡體中文 DVD 只於電腦播放

一、課程基本信息1.先修課程：線性代數（行列式，矩陣與線性方程組，線性空間Fn，歐氏空間Rn，特徵值與矩陣的對角化，實對稱矩陣與二次型）,高等數學（一元微積分，空間解析幾何，無窮級數，常微分方程），計算機基礎知識。2.面向對象：全校的機、電、材、管理、生命和物理、力學諸大學科類，以及人文學科等需要的專業。3.推薦教學參考書：《圖和網絡及其應用》（費培之）（四川出版社）；《圖論與代數結構》戴一奇等編（清華大學出版社）；《GraphTheorywithApplications》（BondyandMurty）(有中譯本)《圖論及其算法》，中國科學技術大學出版社，2003。二、課程的性質和任務《圖與網絡》是理工研究生的專業基礎課。人們常用圖形和網絡來描述某些對象（或事物）之間的特定關係，如工藝流程圖、交通圖、電路圖，互聯網絡等，圖形中的點表示對象，兩點之間的有向或無向連線表示兩對象之間是否有聯繫，由此產生了數學上的圖的概念。研究圖的基本概念和性質、圖的基本理論及其應用構成了圖論的基本內容。《圖與網絡》是理工研究生的專業基礎課。圖論與網絡是研究圖的組合關係及結構的一個數學分支。圖論在物理，化學，計算機科學，通訊科學，電氣工程等學科有著廣泛的應用.圖論的發展與計算機技術和電子技術的發展密切相關.通過本課程的學習,使學生掌握圖與網絡的基本概念和基本理論及其應用。討論如何把實際問題轉化為圖論和網絡問題來解決。討論圖和網絡的基本算法。通過本課程學習可以從整體上提高學生的數學修養與素質。三、教學內容和要求《圖和網絡》圖和網絡的教學內容分為十部分，對不同的內容提出不同的教學要求。(數字表示供參考的相應的學時數)第一章圖的基本概念（10）1．主要介紹圖和網絡發展。（2）2．圖的定義和子圖及其運算（2）3．圖的基本性質（2）4．圖的代數表示（4）。要求：掌握圖論的一?┗靖拍詈突拘災剩饕莆佔虻ネ嫉男災省?第二章樹及其應用（8）1．樹的定義與性質（2）2．割點與橋（2）3．塊的定義和性質（2）4．樹的一些應用，如Huffman二元樹，最短路問題，最小生成樹問題（2）要求：理解樹的定義與割點和橋的概念。掌握樹的性質。第三章匹配及其應用(10)1．最大匹配的定義及其性質（2）2．完美匹配（2）3．二部圖的匹配（2）4．應用-人員分配匈牙利算法（4）要求：理解最大匹配，完美匹配，二部圖的匹配的定義；熟練掌握幾個基本定理例如二部圖的匹配與覆蓋（Hall定理，Koenig定理等）。第四章平面圖及其應用（6）1．平面圖和可平面圖（2）2．歐拉公式（2）3．和Kuratowski定理以及應用。（2）要求理解平面圖、平圖的概念，了解圖在球面和其他曲面上的嵌入，了解對偶圖的概念和基本性質。掌握Euler公式、Kratowski定理，了解5色定理和4色問題。了解平面性算法。第五章歐拉圖和哈密頓圖（6）1．歐拉圈和歐拉圖（2）2．哈密頓圈和哈密頓圖（2）3．和一筆劃問題（2）要求：理解Euler圖的定義，掌握有關充要條件。理解Hamilton圖的概念，掌握有關的必要條件和各種不同的充分條件。了解“中國郵遞員”問題和“旅行售貨員”問題，知道相關的結論。第六章有向圖及其應用（6）1．向圖的概念和性質；（2）2．應用--計算機鼓輪設計等（4）要求：掌握有向圖的概念（強連通性、有向路、有向圈等）及相關結論。了解計算機鼓輪設計。第七章網絡及其應用（8）1．網絡和網絡流概念（2）2．最大流和最小割；（2）應用-最大流問題與算法（4）要求：理解流的定義及守恆條件，掌握最大流最小割定理及相關結論。了解求最大流的標號算法及相關結論。掌握各種形式的Menger定理。四．實驗（上機）內容和基本要求本課程無實驗和上機的教學安排，但要求學生結合本專業的特點和所研究的課題，選擇部分算法自己上機實現。要求學生熟悉至少一門數學軟件平台（Mathematica/matleb/Maple）和至少一種編程語言。五．對學生能力培養的要求本課程採用“引出問題，啟發思路，重點分析，課堂討論，課外探索，自行歸納”的教學方式，使學生在掌握最優化基本知識的基礎上，力求活躍其數學思想，從而培養學生運用較高層次的數學觀點和數學知識，能對實際問題進行分析、歸納、提煉和解決，提高他們的數學素質和數學修養，提升他們開展科技活動和社會實踐的能力以及開展科研工作的能力。另一方面，希望在教師引導下，學生逐步學會自己從前人研究的問題、分析問題的過程、演繹推導的結果中，體會和領悟這些人類高級心智文明的成果，使學生自己真正學懂數學，而不是被“教會”數學；同時希望學生通過研究式的鑽研、探索乃至犯錯誤的過程中，培養從錯縱複雜的現象事理中和繁雜無序的結果數據中，尋找與總結內在關係和規律的能力，並且體會科
朗读