1、15.082 和和 6.855J網(wǎng)絡(luò)單純形動(dòng)畫網(wǎng)絡(luò)單純形動(dòng)畫計(jì)算生成樹(shù)流計(jì)算生成樹(shù)流136452713-6-4123有供應(yīng)和需求的樹(shù)有供應(yīng)和需求的樹(shù).(假設(shè)所有的其他弧假設(shè)所有的其他弧的流是的流是0)在弧在弧(4,3)中的流是中的流是什么？什么？計(jì)算生成樹(shù)流計(jì)算生成樹(shù)流136452713-6-4123為了計(jì)算流，向上為了計(jì)算流，向上迭代樹(shù)，尋找流能迭代樹(shù)，尋找流能唯一確定的弧唯一確定的弧.在弧在弧(5,3)中的流是中的流是什么？什么？2計(jì)算生成樹(shù)流計(jì)算生成樹(shù)流136452713-6-4123在弧在弧(3,2)中的流是中的流是什么？什么？23計(jì)算生成樹(shù)流計(jì)算生成樹(shù)流136452713-6-412

2、3在弧在弧(2,6) 中的流是中的流是什么什么?236計(jì)算生成樹(shù)流計(jì)算生成樹(shù)流136452713-6-4123在弧在弧(7,1)中的流是中的流是什么什么?2364計(jì)算生成樹(shù)流計(jì)算生成樹(shù)流136452713-6-4123在弧在弧(1,6)中的流是中的流是什么什么?23643計(jì)算生成樹(shù)流計(jì)算生成樹(shù)流136452713-6-4123注釋注釋: 有兩中不同的有兩中不同的方法計(jì)算在方法計(jì)算在(1,2)的流的流，兩種方法都給出流，兩種方法都給出流為為 4.這是巧合嗎？這是巧合嗎？236443計(jì)算生成樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子13645275-6-2-413這里是有弧代價(jià)的生這里是有弧代價(jià)的生成樹(shù)

3、成樹(shù).如何選擇結(jié)點(diǎn)勢(shì)如何選擇結(jié)點(diǎn)勢(shì)以便即約代價(jià)是以便即約代價(jià)是0呢呢？回想回想: (i,j)的即約代的即約代價(jià)是價(jià)是 cij - i + j13645275-6-2-413 1 可以被任意設(shè)置可以被任意設(shè)置.我們令我們令 i = 0. 結(jié)點(diǎn)結(jié)點(diǎn) 2 的單純形乘子的單純形乘子是什么？是什么？在最小代價(jià)流問(wèn)題中在最小代價(jià)流問(wèn)題中，有一個(gè)多余的限制，有一個(gè)多余的限制.0計(jì)算生成樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子13645275-6-2-413結(jié)點(diǎn)結(jié)點(diǎn) 7 的單純形乘子的單純形乘子是什么？是什么？0(1,2)的即約代價(jià)是的即約代價(jià)是c12 - 1 + 2

4、= 0.因此因此5 - 0 + 2 = 0.-5計(jì)算生成樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子13645275-6-2-413結(jié)點(diǎn)結(jié)點(diǎn) 3 的單純形乘子的單純形乘子是什么？是什么？0(7,1)的即約代價(jià)是的即約代價(jià)是c12 - 1 + 2 = 0.c71 - 7 + 1 = 0.因此因此 -6 - 7 +0 = 0.-5-6計(jì)算生成樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子13645275-6-2-413結(jié)點(diǎn)結(jié)點(diǎn) 6 的單純形乘子的單純形乘子是什么？是什么？0-5-6-2計(jì)算生成樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子13645275-6-2-413結(jié)點(diǎn)結(jié)點(diǎn) 4 的單純形乘子的單純形乘子是什么？是什么？0

5、-5-6-2-1計(jì)算生成樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子13645275-6-2-413結(jié)點(diǎn)結(jié)點(diǎn) 5 的單純形乘子的單純形乘子是什么？是什么？0-5-6-2-1-4計(jì)算生成樹(shù)的單純形乘子計(jì)算生成樹(shù)的單純形乘子13645275-6-2-413有單純形乘子和這棵有單純形乘子和這棵樹(shù)相關(guān)樹(shù)相關(guān).它們不依弧它們不依弧流，也不依賴非樹(shù)弧流，也不依賴非樹(shù)弧上的代價(jià)上的代價(jià).0-5-6-2-1-4-1網(wǎng)絡(luò)單純形算法網(wǎng)絡(luò)單純形算法124532-42, $44, $21, $45, $53, $5 4, $14, $23, $45-3最小代價(jià)流問(wèn)題最小代價(jià)流問(wèn)題TLU生成樹(shù)流生成樹(shù)流124532-41003

6、2 0135-3初始生成樹(shù)解初始生成樹(shù)解TLU單純形乘子和即約代價(jià)單純形乘子和即約代價(jià)124530-40?400 -2023-2初始單純形乘子和即約代價(jià)初始單純形乘子和即約代價(jià)TLUc45 = 2什么弧是違規(guī)的？什么弧是違規(guī)的？3添加違規(guī)弧到生成樹(shù)，創(chuàng)建圈添加違規(guī)弧到生成樹(shù)，創(chuàng)建圈124533,2 4,04,13,3弧弧(2,1) 添加到了樹(shù)中添加到了樹(shù)中TLU圈是什么，能圈是什么，能發(fā)送多少流？發(fā)送多少流？2, 14, 01, 05, 3u14, x14環(huán)繞圈發(fā)送流環(huán)繞圈發(fā)送流124533,0 4,24,33,3沿著圈發(fā)送沿著圈發(fā)送2 單位的流單位的流TLU下一個(gè)生成樹(shù)下一個(gè)生成樹(shù)是什么？是

7、什么？2, 14, 01, 05, 3u14, x14旋轉(zhuǎn)旋轉(zhuǎn)(pivot)之后之后124533,0 4,24,33,3更新的生成樹(shù)更新的生成樹(shù)TLU在旋轉(zhuǎn)中，一條在旋轉(zhuǎn)中，一條弧加入到弧加入到 T， 而而另一條弧從另一條弧從 T 刪刪除除.2, 14, 01, 05, 3u14, x14更新乘子更新乘子12453當(dāng)前乘子和即約代價(jià)當(dāng)前乘子和即約代價(jià)TLU0-404400 -2023-23我們?nèi)绾问刮覀內(nèi)绾问筩p21 = 0 ，且，且讓其他樹(shù)弧有讓其他樹(shù)弧有 0 即約代價(jià)？即約代價(jià)？從從 T 刪除刪除 (2,1) 把把 T 分裂成兩部分分裂成兩部分12453添加添加 到樹(shù)的一側(cè)不影響任何到樹(shù)的

8、一側(cè)不影響任何樹(shù)弧的即約代價(jià)，除了樹(shù)弧的即約代價(jià)，除了 (2,1). 為什么為什么?TLU0-404400 -2023+-2+3應(yīng)該選擇什么應(yīng)該選擇什么樣的樣的 值，產(chǎn)值，產(chǎn)生即約代價(jià)生即約代價(jià) (2,1) = 0?更新的乘子和即約代價(jià)更新的乘子和即約代價(jià)12453更新的乘子和即約代價(jià)更新的乘子和即約代價(jià).TLU0-402202 0021-43這棵樹(shù)的解是這棵樹(shù)的解是最優(yōu)的嗎？最優(yōu)的嗎？添加一條違反弧到生成樹(shù)，創(chuàng)建圈添加一條違反弧到生成樹(shù)，創(chuàng)建圈12453添加弧添加弧 (3,4) 到生成樹(shù)到生成樹(shù)TLU3,0 4,24,33,32, 14, 01, 05, 3圈是什么，能圈是什么，能發(fā)送多少流

9、？發(fā)送多少流？沿圈發(fā)送流沿圈發(fā)送流12453沿圈發(fā)送沿圈發(fā)送1 個(gè)單位的流個(gè)單位的流.TLU3,0 4,24,23,22, 24, 01, 05, 3下一個(gè)生成樹(shù)下一個(gè)生成樹(shù)解是什么？解是什么？下一個(gè)生成樹(shù)解下一個(gè)生成樹(shù)解12453這是更新的生成樹(shù)解這是更新的生成樹(shù)解TLU3,0 4,24,23,22, 24, 01, 05, 3更新的乘子更新的乘子12453這是當(dāng)前乘子這是當(dāng)前乘子.TLU0-402202 0021-43我們?nèi)绾涡薷奈覀內(nèi)绾涡薷某俗樱砍俗樱扛碌某俗痈碌某俗?2453這是更新的乘子這是更新的乘子.TLU0-4 +02202 0021-43 應(yīng)該是什應(yīng)該是什么值么值?更新的乘

10、子更新的乘子12453這是更新的乘子這是更新的乘子.TLU0-6-24202 0001-43當(dāng)前生成樹(shù)解當(dāng)前生成樹(shù)解是最優(yōu)的嗎？是最優(yōu)的嗎？最優(yōu)解最優(yōu)解12453這是最優(yōu)解這是最優(yōu)解.TLU0-6-24202 0001-43沒(méi)有弧違反最沒(méi)有弧違反最優(yōu)條件優(yōu)條件.尋找圈尋找圈13610118791252使用深度和前驅(qū)使用深度和前驅(qū)13610118791252024depth(5) = 4;depth(3) = 2;用用 pred(5)替換結(jié)點(diǎn)替換結(jié)點(diǎn)5使用深度和前驅(qū)使用深度和前驅(qū)13610118791252023depth(9) = 3;depth(3) = 2;用用 pred(9)替換結(jié)點(diǎn)替換

11、結(jié)點(diǎn)9使用深度和前驅(qū)使用深度和前驅(qū)13610118791252022depth(2) = 2;depth(3) = 2;用用 pred(2)替換結(jié)點(diǎn)替換結(jié)點(diǎn)2;用用 pred(3)替換結(jié)點(diǎn)替換結(jié)點(diǎn)3使用深度和前驅(qū)使用深度和前驅(qū)13610118791252011depth(8) = 1;depth(7) = 1;用用 pred(8)替換結(jié)點(diǎn)替換結(jié)點(diǎn)8;用用 pred(1)替換結(jié)點(diǎn)替換結(jié)點(diǎn)7使用深度和前驅(qū)使用深度和前驅(qū)136101187912520結(jié)點(diǎn)結(jié)點(diǎn)3和和5的的最小共同祖最小共同祖先被找到先被找到.更新乘子：使用線和深度更新乘子：使用線和深度13610118791252假設(shè)弧假設(shè)弧 (1,8)將從樹(shù)中刪將從樹(shù)中刪除除.以結(jié)點(diǎn)以結(jié)點(diǎn)8為根的子樹(shù)為根的子樹(shù)是什么？是什么？跟隨從結(jié)點(diǎn)跟隨從結(jié)點(diǎn)8開(kāi)始的線開(kāi)始的線13610118791252什么是什么是thread(8)?跟隨從結(jié)點(diǎn)跟隨從結(jié)點(diǎn)8開(kāi)始的線開(kāi)始的線13610118791252什么是什么是thread(3)?跟隨從結(jié)點(diǎn)跟隨從結(jié)點(diǎn)8開(kāi)始的線開(kāi)始的線13610118791252什么是什么是thread(10)?跟隨