算法合集之淺析最大最小定理在信息學(xué)競(jìng)賽中的應(yīng)用(編輯修改稿)
2024-11-12 20:32 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 * 對(duì)于一個(gè) 平面圖，我們對(duì)其進(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*的路徑，就對(duì)應(yīng)了一個(gè) st割！ ?更進(jìn)一步，如果我們令每條邊的長(zhǎng)度等于它的容量，那么最小割的容量就等于最短路的長(zhǎng)度！ ?分析一下時(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)號(hào)構(gòu)造一個(gè)最大流 ?[定理 ] ?可以在 O(nlog2n)的時(shí)間內(nèi)求出 st平面圖上的最大流。 小結(jié) ?回顧 ?得到簡(jiǎn)單的最大流模型 ?利用最大流 — 最小割定理進(jìn)行模型轉(zhuǎn)化 ?根據(jù)平面圖的性質(zhì)解決最小割問(wèn)題 ?構(gòu)造得到最大流 最大 — 最小定理 ?對(duì)比以上兩個(gè)定理 ?[定義 ] ?最大 — 最小定理 是一類(lèi)描述同一個(gè)對(duì)象上的一個(gè)最大化問(wèn)題的解和一個(gè)最小化問(wèn)題的解之間的關(guān)系的定理。 最大 — 最小定理 ?共同點(diǎn) ?考察的兩個(gè)最優(yōu)化問(wèn)題互為對(duì)偶問(wèn)題 ?證明的過(guò)程 ?最大化問(wèn)題 M的任何一個(gè)解 m的值都不超過(guò)最小化問(wèn)題 N的任何一個(gè)解 n的值 ?可以找到 M的一個(gè)解 p和 N的一個(gè)解 q，且它們的值相等 ?p和 q分別為各自問(wèn)題的一個(gè)最優(yōu)解 ?簡(jiǎn)潔的最優(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. Br
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1