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