劉汝佳黑書學習指導.ppt

算法藝術與信息學競賽 教學幻燈片,算法圖論 學習指導,聲明,本系列教學幻燈片屬于劉汝佳、黃亮著算法藝術與信息學競賽配套幻燈片 本幻燈片可從本書blog上免費下載，即使您并未購買本書. 若作為教學使用，歡迎和作者聯(lián)系以取得技術支持，也歡迎提供有不同針對性的修改版本，方便更多人使用 有任何意見，歡迎在blog上評論 Blog地址：,內(nèi)容介紹,一、基本概念 二、圖搜索 (重點) 三、DAG 四、連通性問題 (重點, 中難) 五、道路和回路 六、最短路 (重點, 中難) 七、最小生成樹 (重點) 八、最大流問題 (重點, 偏難) 九、最小費用流 (重點, 偏難) 十、匹配 (重點, 偏難) 十一、圖論難解問題 (偏難),一、基本概念,圖的基本概念(1),圖、簡單圖、圖形表示 結點、弧、鄰接、關聯(lián)、度數(shù) 子圖、導出子圖 平面圖、歐幾里得圖、三角形不等式 同構 路徑、圈、不相交路、邊不相交路 連通、連通分量 樹和森林 完全圖和補圖、團 稀疏圖和稠密圖,圖的基本概念(2),二分圖(二部圖) 相交圖、區(qū)間圖 有向圖、DAG 帶權圖、網(wǎng)絡 圖的ADT, 圖IO的ADT 鄰接矩陣、鄰接表和前向星表示 圖例 : 了解即可 : 需要深入理解 : 需要非常熟悉, 能寫出程序,二、圖搜索,圖搜索,寬度優(yōu)先遍歷: 全部內(nèi)容應熟練掌握. 深度優(yōu)先遍歷 基本的DFS-VISIT: 顏色和時間戳 嵌套區(qū)間定理: 推導+直觀理解 (重點) 白色路徑定理: 直觀理解 (可選, 較難) 邊分類規(guī)則: 直觀理解 邊分類算法: 程序?qū)崿F(xiàn)和復雜度分析 (重點) 無向圖只有T邊和B邊: 證明和分類算法 使用pre和post數(shù)組的DFS實現(xiàn)(重點),三、DAG的算法,DAG的算法,DAG的充要條件: 無B邊 (證明和直觀理解) 拓撲排序 (熟練掌握) 基于DFS的算法 基于隊列的算法 關鍵路徑 PT圖 PERT圖 本講內(nèi)容比較簡單, 建議全部理解,四、連通性問題,連通性問題,提醒: 本講比較難, 但算法非常巧妙 SCC劃分 G和GT的SCC相同: 證明和直觀理解 SCC構成DAG: 證明和直觀理解 Kosaraju算法: 按f遞減順序DFS轉置圖(重點) Tarjan/Gabow: 用棧保留結點, 延遲輸出(難) Tarjan算法: 用LOW測試輸出條件 Gabow算法: 用棧保留當前路徑,連通性問題,割頂和橋的判定(重點) 無向圖的LOW函數(shù) 割頂條件和割頂判定算法 橋條件和橋判定算法 BCC劃分,五、道路和回路,道路和回路,歐拉回路和道路 充要條件 套圈算法及其簡潔實現(xiàn) 中國郵路問題 主算法: 倍邊+歐拉回路 權值: SSSP預處理 配對: 二分圖最佳匹配預處理,六、最短路,最短路,SSSP問題 一般SSSP算法, 包括正確性證明 (重難點) dijkstra算法的堆實現(xiàn) (重點) Bellman-ford算法和差分約束系統(tǒng) (重點) Gabow的變尺度算法 (了解即可) APSP問題 矩陣乘法算法 floyd-warshall算法, 包括路徑輸出 (重點) Johnson算法, 包括正確性證明 (重點),七、最小生成樹,最小生成樹,一般MST算法: 正確性證明 經(jīng)典MST算法 Boruvka算法 Prim算法 Kruskal算法 其他問題 (了解) MST唯一性判定 瓶頸生成樹,八、最大流問題,最大流問題,基本概念 流網(wǎng)絡定義、流的三個性質(zhì) 結點集的流記號、運算和凸性 相反方向的流取消操作、循環(huán)流、流分解定理 Ford-Fulkerson方法 殘量網(wǎng)絡、增廣路、切割與流的關系 最大流的兩個等價條件和證明 基本的Ford-Fulkerson方法和復雜度分析 Edmond-Karp算法 (重點) 關于d值的單調(diào)性引理、關鍵弧引理及其證明 (難點) Edmond-Karp算法的時間復雜度及其證明,最大流問題,預流推進算法 預流的定義, push和relabel過程 高度函數(shù)中st的值和性質(zhì): 起點不能太高 (重點) push、relabel和初始化的算法步驟 正確性證明 引理1: 兩個操作至少一個能執(zhí)行 引理2、3: h函數(shù)維持性質(zhì)且每次relabel至少增加1 引理4: 殘量網(wǎng)絡中s到t始終不存在通路 時間復雜度分析(難) discharge操作和relabel-to-front算法 (難) 最高標號預流推進算法,最大流問題,應用舉例 多源多匯問題 頂點容量 有環(huán)轉無環(huán) 無向變有向 可行流 二分圖最大匹配,九、最小費用流問題,最小費用流問題,最小費