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