or教案23_圖論(已修改)
2024-10-17 15:13 本頁(yè)面
【正文】 第四節(jié) 網(wǎng)絡(luò)最大流問(wèn)題 例 連接某產(chǎn)品產(chǎn)地 v1和銷地 v6的交通網(wǎng)如下： v2 v5 3 4 8 v3 v1 v4 v6 5 10 6 11 17 3 5 ?。?vi， vj）：從 vi到 vj的運(yùn)輸線， 弧旁數(shù)字：這條運(yùn)輸線的最大通過(guò)能力 , 制定一個(gè)運(yùn)輸方案，使從 v1到 v6的產(chǎn)品數(shù)量最多。 弧旁數(shù)字： 運(yùn)輸能力。 問(wèn)題：這個(gè)運(yùn)輸網(wǎng)絡(luò)中，從 v1到 v6的最大輸送量是多少？ v2 v5 3 1 3 v3 v1 v4 v6 1 5 3 6 2 2 2 一、基本概念與定理 1. 網(wǎng)絡(luò)與流 定義 1 給定一個(gè)有向圖 D=（ V， A），在 V中指定 一點(diǎn) vs 稱為發(fā)點(diǎn)，指定另一點(diǎn) vt 稱為收點(diǎn)， 其余點(diǎn)稱中間點(diǎn)。任意弧 (vi ， vj )∈ A，有 cij ≥0，稱為弧的容量。稱 D為一個(gè)容量網(wǎng) 絡(luò)。記為 D=（ V， A， C）。 流 : 定義在弧集 A上的一個(gè)函數(shù) f={f(vi ,vj )}，并稱 f(vi ,vj )為弧 (vi ,vj )上的流量。簡(jiǎn)記 f = {fi ,j } 弧旁數(shù)字： 容量 (a)圖是一個(gè)網(wǎng)絡(luò) v2 v5 3 4 8 v3 v1 v4 v6 5 10 6 11 17 3 5 v2 v5 3 1 3 v3 v1 v4 v6 1 5 3 6 2 2 2 弧旁數(shù)字： 流量 cij? fij vi vj v2 v5 v3 v1 v4 v6 2. 可行流與最大流 定義 2 滿足下述條件的流 f 稱為可行流 : 1)容量限制條件 : 對(duì)每一弧 (vi , vj )∈ A 0≤fij ≤cij 2)平衡條件 : 對(duì)中間點(diǎn) vi (i≠s,t ),有 0 A),(A),(?? ???? ijji vvjivvij ff)V( : A),(A),(fffvsjjs vvjsvvsjs ?? ????)V( : A),(A),(fffvtjjt vvjtvvtjt ??? ????V( f ) 稱為可行流 f 的流量 ,即發(fā)點(diǎn)的凈輸出量。 如所有 fij=0， 零流。 可行流總是存在的 3. 增廣鏈 對(duì)可行流 f ={ fij }： 非飽和?。?fij cij 飽和?。?fij =cij 非零流弧： fij 0 零流?。?fij =0 鏈的方向：若 181。是聯(lián)結(jié) vs和 vt的一條鏈，定義鏈的方向是從 vs到 vt 。 前向?。夯〉姆较蚺c鏈的方向一致，記為 181。+。 后向?。夯〉姆较蚺c鏈的方向相反，記為 181。 v2 v5 v3 v1 v4 v6 181。 = (v1,v2,v3,v4,v5,v6 ) 181。+={(v1,v2) ,(v2,v3), (v3 , v4),(v5,v6)} 181。 ={(v5,v4)} v2 v5 v3 v1 v4 v6
外語(yǔ)相關(guān)推薦
鄂ICP備17016276號(hào)-1