跳到正文

MATH3260

圖論

樹與連通性、Euler 圖與 Hamilton 圖、平面性與著色、有向圖、匹配、流與割,以及極值圖論,附證明及例題。

10 章 · 28 節EN · 繁 · 简
我的課程筆記

你的進度

0/ 28 節已標記完成

下一節: 樹與連通性

完成記錄儲存在此瀏覽器中。

這門課在網上

MATH3260 筆記裏的內容

定理卡
90
定義
56
反例
32
概念視角
20
思想史
0
證明透視
30

這門課的概念視角還沒有記錄到網上。

在知識圖譜中打開這門課

數字只算這門課 28 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。

在網上定理卡 90 · 定義 56 · 反例 32 · 概念視角 20 · 證明透視 30

這門課的概念視角還沒有記錄到網上。

在知識圖譜中打開這門課

數字只算這門課 28 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。

第 1 章 · 6 節

樹與連通性

以路徑和橋理解有限樹及其邊數。

定理 24 · 定義 13反例 8視角 4證明透視 7

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 1.1

    樹與連通性

    以路徑和橋理解有限樹及其邊數。

  2. 1.2

    二分著色與奇圈證書

    證明奇圈判準,並構造著色或反證。

  3. 1.3

    基本圈與偶度邊集

    從生成森林構造循環空間並計算其元素數目。

  4. 1.4

    距離、直徑與樹的中心

    尋找使最遠距離最小的頂點,並證明為甚麼逐輪同時刪除葉頂點能找出樹的中心。

  5. 1.5

    標號樹的 Prüfer 編碼與 Cayley 公式

    自成一體的 Prüfer 編碼章節:定義編碼及解碼算法,列明不變量,證明兩者互逆,並推導 Cayley 公式及指定度數的計數公式。

  6. 1.6

    加權拉普拉斯矩陣與生成樹計數

    由關聯矩陣的子式證明加權矩陣–樹公式,計算完全圖與完全二部圖的生成樹數目,並推導精確的邊包含概率與刪除–收縮恆等式。

第 2 章 · 2 節

Euler 遍歷

用閉跡拼接證明偶數度判別法。

定理 5 · 定義 2反例 1視角 1證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 2.1

    歐拉迴路與奇偶性

    用閉跡拼接證明偶數度判別法。

  2. 2.2

    歐拉跡與歐拉迴路:奇偶條件和構造

    證明每條邊恰走一次的度數判據,並以拼接閉跡的方法構造迴路。

第 3 章 · 2 節

平面性與著色

在平面嵌入中計數面,並用所得界證明非平面性。

定理 6 · 定義 5反例 3視角 1證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 3.1

    平面圖、歐拉公式與著色

    在平面嵌入中計數面,並用所得界證明非平面性。

  2. 3.2

    細分與非平面性證據

    辨認細分後的障礙,並證明它們為何能證實圖非平面。

第 4 章 · 2 節

Hamilton 條件

證明保證哈密頓圈存在的度數條件,並區分充分條件和必要條件。

定理 6 · 定義 3反例 2視角 1證明透視 3

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 4.1

    哈密頓圈與度數條件

    證明保證哈密頓圈存在的度數條件,並區分充分條件和必要條件。

  2. 4.2

    哈密頓閉包與度序列判據

    證明度和加邊引理、與加邊次序無關的閉包,以及完整的單調度序列條件,並給出構造性的圈還原方法和否定性檢驗的明確局限。

第 5 章 · 2 節

有向圖

區分弱連通與強連通,並證明有向歐拉迴路判別法。

定理 9 · 定義 5反例 3視角 1證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 5.1

    有向圖、可達性與歐拉迴路

    區分弱連通與強連通,並證明有向歐拉迴路判別法。

  2. 5.2

    競賽圖與有向路徑

    構造有向哈密頓路徑,並理解競賽圖中的圈與可達性。

第 6 章 · 2 節

匹配

透過交錯路徑證明匹配的最優性,推出 Hall 條件,並由同一次搜尋構造最小頂點覆蓋。

定理 6 · 定義 3反例 2視角 2證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 6.1

    增廣路徑、Hall 定理與 König 定理

    透過交錯路徑證明匹配的最優性,推出 Hall 條件,並由同一次搜尋構造最小頂點覆蓋。

  2. 6.2

    奇分支、Tutte 條件與匹配虧量

    透過飽和障礙結構證明一般圖的完美匹配判別準則,推導未匹配頂點個數的精確公式,並解釋為何奇分支取代了二部圖中的鄰域。

第 7 章 · 1 節

流與割

證明增廣流算法的正確性與整數最大流最小割定理,解釋反向殘餘弧,並由二部圖匹配復原匹配與覆蓋的證書。

定理 3 · 定義 2反例 1視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 7.1

    殘餘路徑、整數流與最小割

    證明增廣流算法的正確性與整數最大流最小割定理,解釋反向殘餘弧,並由二部圖匹配復原匹配與覆蓋的證書。

第 8 章 · 2 節

圖的表示

表示有限簡單圖並比較重新標號後的結構。

定理 6 · 定義 7反例 3視角 1證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 8.1

    圖的表示與同構

    用鄰接矩陣和鄰接表記錄有限圖,並以頂點重命名理解同構及其不變量。

  2. 8.2

    可圖化的度序列與 Havel–Hakimi 定理

    判斷有限整數列能否成為帶標號簡單圖的度列,並完整證明 Havel–Hakimi 定理及其構造算法。

第 9 章 · 3 節

連通性

區塊、割點與 Menger 型連通性定理。

定理 8 · 定義 8反例 3視角 2證明透視 3

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 9.1

    塊與塊割森林

    把割點與容許重疊的穩健部分組織成森林,讀出每一次單頂點分離。

  2. 9.2

    透過 Menger 定理研究邊連通度與頂點連通度

    利用整數流證明有限無向圖中兩種路徑–分隔集等式,並明確說明抵銷、流分解以及端點不相鄰這項假設。

  3. 9.3

    全局頂點連通度與扇引理

    將端點不相鄰的 Menger 定理推廣至 k-連通圖中的所有頂點對,證明扇引理及其逆命題,並區分度、邊韌性與頂點韌性。

第 10 章 · 6 節

著色與極值圖論

色多項式、邊著色、Ramsey 與 Turán 型結果。

定理 17 · 定義 8反例 6視角 6證明透視 6

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 10.1

    色多項式與刪除–收縮

    以包含與排除原理及刪除–收縮計算正常著色數目,證明樹、圈與割點公式,並從多項式係數中讀出邊數和三角形數。

  2. 10.2

    二部圖的邊著色與交錯修復

    透過正則補全與構造性的雙色修復兩種方法,證明二部圖邊著色的最大度數緊界,並討論平行邊、運行時間與奇圈障礙。

  3. 10.3

    扇、雙色修復與一般邊著色上界

    證明每個有限簡單圖都存在一種邊著色,所用顏色數至多比最大度多一種。證明利用完整的扇不變量、交替路徑的情形分析以及明確的實現代價。

  4. 10.4

    退化度、收縮與平面圖的五色定理

    證明按退化序的著色,得到平面圖的線性六著色構造,並透過收縮兩個不相鄰的鄰點證明五色定理。

  5. 10.5

    有限 Ramsey 界與隨機著色

    證明有限的二色與多色團保證、三角形的精確閾值以及基於第一矩的下界,並將普遍性保證、存在性結論與充分的概率檢驗區分開來。

  6. 10.6

    無團極值圖與均衡部分

    證明排除團所需的精確整數邊數閾值,包括完整的等號情形分類,並將其轉移到獨立數有界的最少邊圖上。

Vercel 瀏覽統計與公開頁面效能量度均須分別取得同意,兩者均非使用網站的必要條件。

網站功能儲存(按需使用)

安全、登入及你選擇的偏好會按需使用儲存,與可選統計分開處理。

撤回會停止後續統計;需要卸載已載入的統計程式時,頁面會重新載入。已傳送的資料不會因此刪除。

查看 Cookie 與儲存詳情