or教案23_圖論-展示頁
2024-10-15 15:13本頁面
【正文】 = (v1,v2,v3,v4,v5,v6 ) 181。+。是聯(lián)結(jié) vs和 vt的一條鏈，定義鏈的方向是從 vs到 vt 。 如所有 fij=0， 零流。 流 : 定義在弧集 A上的一個(gè)函數(shù) f={f(vi ,vj )}，并稱 f(vi ,vj )為弧 (vi ,vj )上的流量。稱 D為一個(gè)容量網(wǎng) 絡(luò)。 問題：這個(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)。 第四節(jié) 網(wǎng)絡(luò)最大流問題 例 連接某產(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)輸線的最大通過能力 , 制定一個(gè)運(yùn)輸方案，使從 v1到 v6的產(chǎn)品數(shù)量最多。 弧旁數(shù)字： 運(yùn)輸能力。任意弧 (vi ， vj )∈ A，有 cij ≥0，稱為弧的容量。記為 D=（ V， A， C）。簡記 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)的凈輸出量。 可行流總是存在的 3. 增廣鏈 對(duì)可行流 f ={ fij }： 非飽和?。?fij cij 飽和?。?fij =cij 非零流?。?fij 0 零流?。?fij =0 鏈的方向：若 181。 前向?。夯〉姆较蚺c鏈的方向一致，記為 181。 后向?。夯〉姆较蚺c鏈的方向相反，記為 181。 v2 v5 v3 v1 v4 v6 181。+={(v1,v2) ,(v2,v3), (v3 , v4),(v5,v6)} 181。 是從 vs 到 vt 的一條鏈 ,若 181。 (vi , vj ) ∈ 181。+ 0≤ fij c
外語相關(guān)推薦
鄂ICP備17016276號(hào)-1