你的進度
0/ 28 節已標記完成
下一節: 樹與連通性
完成記錄儲存在此瀏覽器中。
這門課在網上
MATH3260 筆記裏的內容
數字只算這門課 28 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。
在網上定理卡 90 · 定義 56 · 反例 32 · 概念視角 20 · 證明透視 30
第 1 章 · 6 節
樹與連通性
以路徑和橋理解有限樹及其邊數。
- 1.1
樹與連通性
以路徑和橋理解有限樹及其邊數。
- 1.2
二分著色與奇圈證書
證明奇圈判準,並構造著色或反證。
- 1.3
基本圈與偶度邊集
從生成森林構造循環空間並計算其元素數目。
- 1.4
距離、直徑與樹的中心
尋找使最遠距離最小的頂點,並證明為甚麼逐輪同時刪除葉頂點能找出樹的中心。
- 1.5
標號樹的 Prüfer 編碼與 Cayley 公式
自成一體的 Prüfer 編碼章節:定義編碼及解碼算法,列明不變量,證明兩者互逆,並推導 Cayley 公式及指定度數的計數公式。
- 1.6
加權拉普拉斯矩陣與生成樹計數
由關聯矩陣的子式證明加權矩陣–樹公式,計算完全圖與完全二部圖的生成樹數目,並推導精確的邊包含概率與刪除–收縮恆等式。
第 2 章 · 2 節
Euler 遍歷
用閉跡拼接證明偶數度判別法。
- 2.1
歐拉迴路與奇偶性
用閉跡拼接證明偶數度判別法。
- 2.2
歐拉跡與歐拉迴路:奇偶條件和構造
證明每條邊恰走一次的度數判據,並以拼接閉跡的方法構造迴路。
第 3 章 · 2 節
平面性與著色
在平面嵌入中計數面,並用所得界證明非平面性。
- 3.1
平面圖、歐拉公式與著色
在平面嵌入中計數面,並用所得界證明非平面性。
- 3.2
細分與非平面性證據
辨認細分後的障礙,並證明它們為何能證實圖非平面。
第 4 章 · 2 節
Hamilton 條件
證明保證哈密頓圈存在的度數條件,並區分充分條件和必要條件。
- 4.1
哈密頓圈與度數條件
證明保證哈密頓圈存在的度數條件,並區分充分條件和必要條件。
- 4.2
哈密頓閉包與度序列判據
證明度和加邊引理、與加邊次序無關的閉包,以及完整的單調度序列條件,並給出構造性的圈還原方法和否定性檢驗的明確局限。
第 5 章 · 2 節
有向圖
區分弱連通與強連通,並證明有向歐拉迴路判別法。
- 5.1
有向圖、可達性與歐拉迴路
區分弱連通與強連通,並證明有向歐拉迴路判別法。
- 5.2
競賽圖與有向路徑
構造有向哈密頓路徑,並理解競賽圖中的圈與可達性。
第 6 章 · 2 節
匹配
透過交錯路徑證明匹配的最優性,推出 Hall 條件,並由同一次搜尋構造最小頂點覆蓋。
- 6.1
增廣路徑、Hall 定理與 König 定理
透過交錯路徑證明匹配的最優性,推出 Hall 條件,並由同一次搜尋構造最小頂點覆蓋。
- 6.2
奇分支、Tutte 條件與匹配虧量
透過飽和障礙結構證明一般圖的完美匹配判別準則,推導未匹配頂點個數的精確公式,並解釋為何奇分支取代了二部圖中的鄰域。
第 7 章 · 1 節
流與割
證明增廣流算法的正確性與整數最大流最小割定理,解釋反向殘餘弧,並由二部圖匹配復原匹配與覆蓋的證書。
- 7.1
殘餘路徑、整數流與最小割
證明增廣流算法的正確性與整數最大流最小割定理,解釋反向殘餘弧,並由二部圖匹配復原匹配與覆蓋的證書。
第 8 章 · 2 節
圖的表示
表示有限簡單圖並比較重新標號後的結構。
- 8.1
圖的表示與同構
用鄰接矩陣和鄰接表記錄有限圖,並以頂點重命名理解同構及其不變量。
- 8.2
可圖化的度序列與 Havel–Hakimi 定理
判斷有限整數列能否成為帶標號簡單圖的度列,並完整證明 Havel–Hakimi 定理及其構造算法。
第 9 章 · 3 節
連通性
區塊、割點與 Menger 型連通性定理。
- 9.1
塊與塊割森林
把割點與容許重疊的穩健部分組織成森林,讀出每一次單頂點分離。
- 9.2
透過 Menger 定理研究邊連通度與頂點連通度
利用整數流證明有限無向圖中兩種路徑–分隔集等式,並明確說明抵銷、流分解以及端點不相鄰這項假設。
- 9.3
全局頂點連通度與扇引理
將端點不相鄰的 Menger 定理推廣至 k-連通圖中的所有頂點對,證明扇引理及其逆命題,並區分度、邊韌性與頂點韌性。
第 10 章 · 6 節
著色與極值圖論
色多項式、邊著色、Ramsey 與 Turán 型結果。
- 10.1
色多項式與刪除–收縮
以包含與排除原理及刪除–收縮計算正常著色數目,證明樹、圈與割點公式,並從多項式係數中讀出邊數和三角形數。
- 10.2
二部圖的邊著色與交錯修復
透過正則補全與構造性的雙色修復兩種方法,證明二部圖邊著色的最大度數緊界,並討論平行邊、運行時間與奇圈障礙。
- 10.3
扇、雙色修復與一般邊著色上界
證明每個有限簡單圖都存在一種邊著色,所用顏色數至多比最大度多一種。證明利用完整的扇不變量、交替路徑的情形分析以及明確的實現代價。
- 10.4
退化度、收縮與平面圖的五色定理
證明按退化序的著色,得到平面圖的線性六著色構造,並透過收縮兩個不相鄰的鄰點證明五色定理。
- 10.5
有限 Ramsey 界與隨機著色
證明有限的二色與多色團保證、三角形的精確閾值以及基於第一矩的下界,並將普遍性保證、存在性結論與充分的概率檢驗區分開來。
- 10.6
無團極值圖與均衡部分
證明排除團所需的精確整數邊數閾值,包括完整的等號情形分類,並將其轉移到獨立數有界的最少邊圖上。