《集合論與圖論（下）》是哈爾濱工業大學提供的慕課課程，授課教師是姜守旭 、 陳建文 、 劉峰 、 吳少川 、 李君寶。
基本介紹
- 中文名：集合論與圖論（下）
- 類別：慕課
- 提供院校：哈爾濱工業大學
- 授課老師：姜守旭 、 陳建文 、 劉峰 、 吳少川 、 李君寶
課程簡介,課程大綱,參考教材,
課程簡介
本課程的目標是通過理論學習，使學生正確地理解概念，正確地使用概念進行推理，養成一個好的思維習慣，理解理論與實踐的關係。引導學生觀察生活、社會和大自然，分析事物間的聯繫，建立系統的模型，提出和解決其中的複雜工程問題。
本課程主要包含二部分內容：集合論與圖論。集合論是整個數學的基礎，也是計算機科學的基礎，計算機科學領域中的大多數基本概念和理論，幾乎均採用集合論的有關術語來描述和論證，而圖論的基本知識則將始終陪伴著每一個計算機工作者的職業生涯。
計算學科以抽象、理論、設計為其學科形態，以數學方法和系統方法為其學科方法，本課程的核心目標就是在抽象和理論的基礎上提供數學方法，因此，本課程是整個專業的基礎課程，是計算機專業最重要的課程之一。
課程大綱
第1講 圖的基本概念
1.1 課前準備-圖論
1.2 簡史
1.3 圖
1.4 圖的表示
1.5 圖模型
1.6 子圖
1.7 度
1.8 正則圖
1.9 同構
第2講 連通圖、補圖、偶圖
2.1 路、圈
2.2 連通圖
2.3 判定是否連通
2.4 幾類證明方法
2.5 判定是否有圈
2.6 關於路和圈的一個定理
2.7 補圖
2.8 雙圖
2.9 圖蘭定理
2.10 極圖理論
第3講 歐拉圖
3.1 歐拉圖、歐拉定理
3.2 歐拉定理的擴展
第4講 哈密頓圖
4.1 背景
4.2 哈密頓圖
4.3 哈密頓圖判定的必要條件
4.4 哈密頓圖判定的充分條件
第5講 圖的表示、帶權圖
5.1 鄰接矩陣
5.2 鄰接表
5.3 關聯矩陣
5.4 圖解
5.5 帶權圖
第6講 樹、割集
6.1 樹的定義
6.2 樹的性質
6.3 極小連通圖
6.4 樹的中心
6.5 生成樹
6.6 最小生成樹
6.7 割點
6.8 割點的性質
第7講 圖的連通度
7.1 背景
7.2 頂點連通度和邊連通度
7.3 頂點連通度和邊連通度的關係
7.4 n連通
7.5 明格爾定理
7.6 柯尼希定理
7.7 網路流問題
第8講 匹配問題
8.1 獨立集
8.2 偶圖的匹配
8.3 偶圖匹配的條件
8.4 相異代表系
第9講 平面圖
9.1 背景
9.2 平面圖的定義
9.3 歐拉公式
9.4 例題
9.5 非哈密頓平面圖
第10講 圖的頂點著色問題
10.1 圖的頂點著色
10.2 色數的上、下界
10.3 四色定理 vs 五色定理
第11講 有向圖的基本概念
11.1 有向圖的表示
11.2 有向圖中頂點的度
11.3 有向完全圖
11.4 有向圖的同構
11.5 有向路、有向圈
11.6 鄰接矩陣
第12講 有根樹、有序樹、比賽圖
12.1 有根樹、有序樹
12.2 比賽圖
參考教材
1.《離散數學引論》（修訂版），王義和編著，哈爾濱工業大學出版，2016.
2.《離散數學教程》，耿素雲等編著，北京大學出版社，2015。
3.《離散數學》，左孝凌等編著，上海科技文獻出版社，2016。
