蕪湖一中周冬max_zd@163com(編輯修改稿)
2024-11-16 10:18 本頁面
【文章內(nèi)容簡介】 對于一個 平面圖，我們對其進行如下改造：刪去 *和 t*之間的邊 1 2 3 4 5 6 7 8 1* 3* 2* 4* 5* 7* 6* 8* s t s* t* 利用最短路求最小割 ?一條從 s*到 t*的路徑，就對應了一個 st割！ ?更進一步，如果我們令每條邊的長度等于它的容量，那么最小割的容量就等于最短路的長度！ ?分析一下時間復雜度 ?新圖中的點數(shù)和邊數(shù)都是 O(n)的 ?使用二叉堆優(yōu)化的 Dijkstra算法求最短路，時間復雜度為 O(nlog2n) 1 2 3 4 5 6 7 8 1* 3* 2* 4* 5* 7* 6* 8* s t s* t* 利用最短路求最大流 ?我們可以利用最短路算法得到的距離標號構(gòu)造一個最大流 ?[定理 ] ?可以在 O(nlog2n)的時間內(nèi)求出 st平面圖上的最大流。 小結(jié) ?回顧 ?得到簡單的最大流模型 ?利用最大流 — 最小割定理進行模型轉(zhuǎn)化 ?根據(jù)平面圖的性質(zhì)解決最小割問題 ?構(gòu)造得到最大流 最大 — 最小定理 ?對比以上兩個定理 ?[定義 ] ?最大 — 最小定理 是一類描述同一個對象上的一個最大化問題的解和一個最小化問題的解之間的關(guān)系的定理。 最大 — 最小定理 ?共同點 ?考察的兩個最優(yōu)化問題互為對偶問題 ?證明的過程 ?最大化問題 M的任何一個解 m的值都不超過最小化問題 N的任何一個解 n的值 ?可以找到 M的一個解 p和 N的一個解 q，且它們的值相等 ?p和 q分別為各自問題的一個最優(yōu)解 ?簡潔的最優(yōu)性證明 總結(jié) K246。nig定理 最大流 — 最小割定理 最大 — 最小定理 最大匹配 最小覆蓋 最大流 最小割 最大 最小 完全矛盾 互相轉(zhuǎn)化 注意總結(jié)、積累 勇于探索 參考文獻 I. Introduction to Graph Theory, Second Edition by Douglas B. West II. Network Flows: Theory, Algorithms and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin III. Introductory Combinatorics, Third Edition by Richard A. Bru
教學課件相關(guān)推薦
鄂ICP備17016276號-1