第六章图与网络分析学习教案

《第六章图与网络分析学习教案》由会员分享，可在线阅读，更多相关《第六章图与网络分析学习教案（100页珍藏版）》请在装配图网上搜索。

1、会计学1第六章图与网络分析第六章图与网络分析第一页，共100页。ABCDF哥尼斯堡七桥问题哥尼斯堡七桥问题F在图中找一条经过在图中找一条经过(jnggu)每边一次且每边一次且仅一次的路仅一次的路欧拉回路。欧拉回路。ADBC由点和边组成(z chn)第1页/共100页第二页，共100页。F“中国邮路问题中国邮路问题”F在图中找一条经过每边的最短路在图中找一条经过每边的最短路类似类似(li s)带权的欧拉回路。带权的欧拉回路。F“货郎担问题货郎担问题”F在图中找一条在图中找一条(y tio)经过每个点一次且仅经过每个点一次且仅一次的最短路一次的最短路带权的哈密尔顿回路。带权的哈密尔顿回路。第2页/

2、共100页第三页，共100页。第3页/共100页第四页，共100页。V=v1，v2，v3，v4 E=e1，e2，,e7e1=v1,v2e2=v1,v2, ,e7=v4,v41v2v3v4v1e2e3e4e5e6e7e第4页/共100页第五页，共100页。v1v2v3v4v5例：右图V=v1，v2,v5A=a1，a2,a7a1=v1,v5,a2=v5,v4,a7=v1,v4第5页/共100页第六页，共100页。第6页/共100页第七页，共100页。1v2v3v4v1e2e3e4e5e6e5v孤立(gl)点悬挂(xungu)边12( )3, ()3d vd v第7页/共100页第八页，共100页。

3、qvdVv2)(qvdvdvdVvVvVv2)()()(21偶数(u sh)偶数偶数第8页/共100页第九页，共100页。n例：右图),.,(1211kkkiiiiiivevvevkiivv1kiiivvv,.,21121,.,kiiivvv1v2v3v4v1e2e3e4e5e6e7e无重复(chngf)点,无重复(chngf)边有重复(chngf)点,无重复(chngf)边第9页/共100页第十页，共100页。的图.第10页/共100页第十一页，共100页。方向(fngxing)可以不同第11页/共100页第十二页，共100页。, n多重有向图: 有多重弧.),.,1112211kkkiii

4、iiiivavavav（kiivv1),(1tttiiivva1ivkiv方向(fngxing)相同第12页/共100页第十三页，共100页。12,nVv vv()ijAa10ijaij或权值，若(v ,v ) E或 ，否则第13页/共100页第十四页，共100页。GG第14页/共100页第十五页，共100页。第15页/共100页第十六页，共100页。第16页/共100页第十七页，共100页。第17页/共100页第十八页，共100页。第18页/共100页第十九页，共100页。第19页/共100页第二十页，共100页。第20页/共100页第二十一页，共100页。深探法广探法第21页/共100页第

5、二十二页，共100页。TvvijjiwTw,)(第22页/共100页第二十三页，共100页。)()(min*TwTwT第23页/共100页第二十四页，共100页。F有向树：有向树：F根树：有向树根树：有向树T，恰有一个，恰有一个(y )结点入次为结点入次为0，其余各点，其余各点入次为入次为1，则称，则称T为根树。为根树。FM叉树：叉树：F二叉树：结点的出度都小于二叉树：结点的出度都小于等于等于2。根叶分点枝第一层第三层第二层三叉树第24页/共100页第二十五页，共100页。F最优二叉树（最优二叉树（ Huffman树）：总权数树）：总权数(qunsh)最小最小的二叉树的二叉树F算法步骤：算法步

6、骤：Huffman算法算法F将将s个叶子按权由小到大排列，个叶子按权由小到大排列，F将两个最小的叶子合并为一个分枝点，其权为两者之将两个最小的叶子合并为一个分枝点，其权为两者之和，将新的分枝点作为一个叶子，转上一步，直到结和，将新的分枝点作为一个叶子，转上一步，直到结束。束。), 2 , 1( ,silisiiilpTm1)(第25页/共100页第二十六页，共100页。123243365第26页/共100页第二十七页，共100页。123243396515123243396515第27页/共100页第二十八页，共100页。第28页/共100页第二十九页，共100页。0.050.450.050.0

7、80.120.25一等品一等品五等品五等品四等品四等品三等品三等品二等品二等品等外品等外品0.100.300.180.551.0测试(csh)顺序第29页/共100页第三十页，共100页。第30页/共100页第三十一页，共100页。)()(min0PwPwP的最短路到的最短路到isjsvvisvvjisvvvvv,.,.,.,则最短路则最短路(dunl)问题为：问题为：第31页/共100页第三十二页，共100页。( ) ( ) ()0sssT vvvvsvvv 第32页/共100页第三十三页，共100页。011122330 1 ()0 ()0 () ()1 () ()1 . . iSvkP v

8、vT vvT vv 99 () ()1T vv 第33页/共100页第三十四页，共100页。12112222131133331411444( ,):( )066() ()6 ()1 ( ,):( )033() ()3 ()1 ( ,):( )011() ()v vP vwT vT vvv vP vwT vT vvv vP vwT vT v 423456789411441 ()1min (), (), (), (), (), (), (), ()() 1 , ()1 4vT vT vT vT vT vT vT vT vT viSv vP vk第34页/共100页第三十五页，共100页。3 3)(

9、 , 2 )()(),( ),(),(),(),(),( min4)( 11)( )(11101)(: ),(334123987653266646464kvPvvvSivTvTvTvTvTvTvTvTvvTvTwvPvv第35页/共100页第三十六页，共100页。2 5)( , 3 )()(),(),( ),(),(),( min3)( 5)( 6)(523)(: ),(223413298765222232323kvPvvvvSivTvTvTvTvTvTvTvvTvTwvPvv第36页/共100页第三十七页，共100页。252255555678954143255(,):()5 16() ()6

10、 ()2min (), (), (), (), ()() 4 , ()6 5v vP vwT vT vvT vT vT vT vT vT viSv v v v vP vk 第37页/共100页第三十八页，共100页。7 9)( , 5 )()(),(),( ),(min5)( 12)( )(1266)(: ),( 5)( 9)( )(936)(: ),( 5)( 10)( )(1046)(: ),(77523415798768845858577757575610656565kvPvvvvvvSivTvTvTvTvTvvTvTwvPvvvvTvTwvPvvvvTvTwvPvv第38页/共100页

11、第三十九页，共100页。7877888856896614325766(,):()9413( )12 ( ) =12 ( )min (), ( ), ()() 6 , ()10 6v vP vwT vT vvvT vT vT vT viSv v v v v v vP vk第39页/共100页第四十页，共100页。6689871432576888899,min (),()() 7 , ()12 8,min () () . vST vT vT viSv vv vv vvvP vkvST vT v 无指向不属于的点 转向 无指向不属于 的点 转向算法终止第40页/共100页第四十一页，共100页。Mv

12、vTvvPvvPvvPvvPvvPvvPvvPvvP)( )(5)( 12)(5)( 9)(5)( 10)(2)( 6)(1)( 1)(1)( 3)(3)( 5)(0)( 0)(998877665544332211第41页/共100页第四十二页，共100页。 ),(: ),(:jijjkjijjkvSvEvvvSvAvv的点且考察修改为的点且考察算法修改第42页/共100页第四十三页，共100页。第43页/共100页第四十四页，共100页。第44页/共100页第四十五页，共100页。称为可行流的流量有对有对有对平衡条件（对容量限制条件)()( :)( :0:,:)20 ),:) 1),(),(

13、),(),(),(),(fvfvffvfvffvfftsivcfAvvAvvjtAvvtjtAvvjsAvvsjsAvvjiAvvijiijijjitjjtsjjsijji流入量=流出量流出量流入量第45页/共100页第四十六页，共100页。tifvfftsiffsifvffAvvcffvAvvjtAvvtjAvvjiAvvijAvvjsAvvsjjiijijtjjtijjisjjs )(, 0 )( ),( 0)(max),(),(),(),(),(),(第46页/共100页第四十七页，共100页。其全体记为后向弧反弧的方向与链的方向相其全体记为前向弧致弧的方向与链的方向一网络中的一条链非零

14、流弧零流弧非饱和弧饱和弧- ),.,( 0 0 tsijijijijijijvvffcfcfijff 第47页/共100页第四十八页，共100页。非零流弧对后向弧非饱和弧对前向弧ijijijijcfcf0:0:TSVTS,可增加(zngji)流量的链第48页/共100页第四十九页，共100页。.),(,),( _11_11_11称为截集则把弧集且和被分为两个非空集合若对网络VVVvVvVVVCAVDts),(),(_11_11_11_11),( :),(,),( VVvvijjicVVcVVcVV即记为简称截量集的容量为截中所有弧的容量之和称把截集第49页/共100页第五十页，共100页。最小

15、截集容量最大流量最大流量最小截集定理的增广链不存在关于是最大流可行流 : ) 3 2),()( ) 1*_11ffVVcfv第50页/共100页第五十一页，共100页。第51页/共100页第五十二页，共100页。., .,),(min)( :),(,( 0,),(),(min)( :),(,( ,),()(,), 0( 停止则已得到最大流没有得到标号若进入调整过程已找到一条增广链已标号若其中标号给非零流弧后向弧对其中标号给非饱和弧若前向弧对标号未检查点对一般地标上给ttjiijjijjiijijijijjijijijjiisvvfvlvlvlvvfvvfcvlvlvlvvcfvvvv第52页/

16、共100页第五十三页，共100页。第53页/共100页第五十四页，共100页。Avvijijjifbfb),()(min第54页/共100页第五十五页，共100页。ijijbbfbfb)()(0 0 ijijijjiijijijijijijffbwcfcfbw第55页/共100页第五十六页，共100页。),( ),( ),( )(min),(minmin)1()1()1()1()1(jikijjikijjikijkijkijkijijvvfvvfvvffffc第56页/共100页第五十七页，共100页。初初始始网网络络数数值值VsV1 V2 V3 Vt 第57页/共100页第五十八页，共100

17、页。(4,10)(1, 8)(2, 4)(1, 7)(2, 5)(6, 2)(4,10)bij Cij初初始始网网络络数数值值VsV1 V2 V3 Vt 第58页/共100页第五十九页，共100页。取初始取初始(ch sh)可行流可行流f (0) =0V1 V2 V3 Vs Vt 第59页/共100页第六十页，共100页。(4,0)(1, 0)(2, 0)(1, 0)(2, 0)(6, 0)(4,0)取初始取初始(ch sh)可行流可行流f (0) =0V1 V2 V3 Vs Vt bij fij第60页/共100页第六十一页，共100页。(4,0)(1, 0)(2, 0)(1, 0)(2,

18、0)(6, 0)(4,0)取初始取初始(ch sh)可行流可行流f (0) =0构造赋构造赋权图权图W(f (0)V1 V2 V3 Vs Vt 0 0 ijijijjiijijijijijijffbwcfcfbw第61页/共100页第六十二页，共100页。(4,0)(1, 0)(2, 0)(1, 0)(2, 0)(6, 0)(4,0)取初始取初始可行可行(kxng)流流f (0) =0构造赋构造赋权图权图W(f (0)V1 V2 V3 Vs Vt 第62页/共100页第六十三页，共100页。(4,0)(1, 0)(2, 0)(1, 0)(2, 0)(6, 0)(4,0)取初始取初始可行可行(k

19、xng)流流f (0) =0构造赋构造赋权图权图W(f (0)( + , 0 )V1 V2 V3 Vs Vt 第63页/共100页第六十四页，共100页。(4,0)(1, 0)(2, 0)(1, 0)(2, 0)(6, 0)(4,0)在初始在初始(ch sh)赋权图赋权图W(f (0)上求出上求出最短路最短路V1 V2 V3 Vs Vt 第64页/共100页第六十五页，共100页。(4,0)(1, 5)(2, 0)(1,5)(2, 5)(6, 0)(4,0)在最短在最短路上路上(l shng)增增加流量加流量V1 V2 V3 Vs Vt ),( ),( ),( )(min),(minmin)0

20、()0()0()1()0()0(jiijjiijjiijijijijijvvfvvfvvffffc第65页/共100页第六十六页，共100页。(4,0)(2, 0)(6, 0)(4,0)在最短在最短路上路上(l shng)增增加流量加流量原流量原流量如图所如图所示示V1 V2 V3 Vs Vt (1, 0)(1, 0)(2, 0)第66页/共100页第六十七页，共100页。(4,0)(2, 0)(6, 0)(4,0)求求增增加加的的流流量量V1 V2 V3 Vs Vt 8 - 0 5 - 0 7 - 0最小最小f (0) (1, 0)(1, 0)(2, 0)第67页/共100页第六十八页，共1

21、00页。(4,0)(1, 5)(2, 0)(1,5)(2, 5)(6, 0)(4,0)在最短在最短路上增路上增加流量加流量(liling) = 5得到新得到新的流量的流量(liling)f (1)=5V1 V2 V3 Vs Vt 第68页/共100页第六十九页，共100页。(4,0)(1, 5)(2, 0)(1,5) (2, 5)(6, 0)(4,0)依据依据(yj)新新的流量的流量构造又构造又一赋权一赋权图图W(f (1)*只对增只对增广链广链V1 V2 V3 Vs Vt 80 0 ijijijjiijijijijijijffbwcfcfbw第69页/共100页第七十页，共100页。(4,0

22、)(2, 0)(1,5) (2, 5)(6, 0)(4,0)赋赋权权图图W(f (1)的构造的构造(guzo)*只对只对增广链增广链V1 V2 V3 Vs Vt 8(-1, 5)(1, 5)第70页/共100页第七十一页，共100页。(4,0)(2, 0)(1,5)(2, 5)(6, 0)(4,0)赋赋权权图图W(f (1)的构造的构造(guzo)*只对增只对增广链广链V1 V2 V3 Vs Vt 8 5(-1, 5)(1, 5)0 0 ijijijjiijijijijijijffbwcfcfbw第71页/共100页第七十二页，共100页。(4,0)(2, 0)(1,5)(6, 0)(4,0)

23、赋赋权权图图W(f (1)的构造的构造(guzo)*只对增只对增广链广链V1 V2 V3 Vs Vt 8 5(-2, 5) 7(-1,5)(-1, 5)(1, 5)第72页/共100页第七十三页，共100页。(4,0)(2, 0)(1,5)(6, 0)(4,0)构造构造(guzo)的的赋权赋权图图W(f (1)*只对增只对增广链广链V1 V2 V3 Vs Vt (-2, 5)(-1,5)(-1, 5)(1, 5)第73页/共100页第七十四页，共100页。(4,0)(2, 0)(1,5)(6, 0)(4,0)在赋在赋权图权图W(f (1)上求出上求出最短路最短路(dunl)V1 V2 V3 V

24、s Vt (-2, 5)(-1,5)(-1, 5)(1, 5)第74页/共100页第七十五页，共100页。Vs (4,0)(1, 5)(2, 0)(1,5)(2, 5)(6, 0)(4,0)在最短在最短路上路上(l shng)增增加流量加流量V1 V2 V3 Vs Vt 7 - 5 = 2 10 - 0 最小最小第75页/共100页第七十六页，共100页。Vs (4,2)(1, 5)(2, 0)(1,7)(2, 5)(6, 0)(4,0) = 2得到得到(d do)新新的流量的流量f (2)=7新的流新的流量图如量图如图所示图所示V1 V2 V3 Vs Vt 第76页/共100页第七十七页，共

25、100页。依据依据(yj)新新的流量的流量构造又构造又一赋权一赋权图图W(f (2)*只对只对增广链增广链V1 (4,0)(1, 5)(2, 0)(1,5)(6, 0)(4,0)V1 V2 V3 Vs Vt (-1, 5)(-2, 5)(-1,5)第77页/共100页第七十八页，共100页。对最短对最短路上路上(l shng)求求新的权新的权值值V1 (4,2)(1, 5)(2, 0)(1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-1, 5)(-2, 5) 100 0 ijijijjiijijijijijijffbwcfcfbw第78页/共100页第七十九页，共100页。赋赋

26、权权图图的构造的构造(guzo)W(f (2)*只对增只对增广链广链V1 (4,2)(1, 5)(2, 0)(1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-1, 5)(-2, 5)(-4,2)0 0 ijijijjiijijijijijijffbwcfcfbw第79页/共100页第八十页，共100页。赋赋权权图图的构造的构造(guzo)W(f (2)*只对增只对增广链广链V1 (4,2)(-1, 5)(2, 0)(1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (1, 5)(-2, 5) 7(-4,2)0 0 ijijijjiijijijijijijffbwcfc

27、fbw第80页/共100页第八十一页，共100页。赋赋权权图图的构造的构造(guzo)W(f (2)*只对增只对增广链广链V1 (4,2)(2, 0)(-1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-2, 5)(-4,2)(-1, 5)(1, 5)第81页/共100页第八十二页，共100页。新新赋赋权权图图W(f (2)*只对增只对增广广(zn un)链链V1 (4,2)(2, 0)(-1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-2, 5)(-4,2)(-1, 5)(1, 5)第82页/共100页第八十三页，共100页。在赋在赋权图权图W(f (2)上求出

28、上求出最短路最短路(dunl)V1 (4,2)(2, 0)(-1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-2, 5)(-4,2)(-1, 5)(1, 5)第83页/共100页第八十四页，共100页。(4,2)(1, 5)(2, 0)(1,7)(2, 5)(6, 0)(4,0)在最短在最短路上路上(l shng)增增加流量加流量 = 3V1 V2 V3 Vt 8 - 5 = 3 最小最小 10 - 0 4 - 0第84页/共100页第八十五页，共100页。(4,2)(1, 8)(2, 3)(1,7)(2, 5)(6, 0)(4,3)在最短在最短路上路上(l shng)增增加流

29、量加流量 = 3得到新得到新的流量的流量f (3)=10V1 V2 V3 Vt 第85页/共100页第八十六页，共100页。依据依据(yj)新新的流量的流量构造又构造又一赋权一赋权图图W(f (3)*只对只对增广链增广链V1 (4,2)(2, 3)(-1,7)(6, 0)(4,3)V1 V2 V3 Vs Vt (-2, 5)(-1,5)(-4,2)(1, 8) 8 10 4第86页/共100页第八十七页，共100页。赋赋权权图图W(f (3)的构造的构造(guzo)*只对增只对增广链广链V1 (4,2)(2, 3)(-1,7)(6, 0)(4,3)V1 V2 V3 Vs Vt (-2, 5)(

30、-1,5)(-4,2)(-1, 8)(-4,3)(-2, 3)第87页/共100页第八十八页，共100页。在赋权在赋权图图W(f (3)上求出上求出最短路最短路(dunl)V1 (4,2)(2, 3)(-1,7)(6, 0)(4,3)V1 V2 V3 Vs Vt (-2, 5)(-1,5)(-4,2)(-1, 8)(-4,3)(-2, 3)第88页/共100页第八十九页，共100页。在初始在初始(ch sh)赋权图赋权图W(f (0)上求出上求出最短路最短路V1 (4,2)(2, 3)(-1,7)(6, 0)(4,3)V1 V2 V3 Vs Vt (-2, 5)(-1,5)(-4,2)(-1,

31、 8)(-4,3)(-2, 3)第89页/共100页第九十页，共100页。(4,2)(1, 8)(2, 3)(1,7)(2, 5)(6, 0)(4,3)在最短在最短路上路上(l shng)增增加流量加流量V1 V2 V3 Vt 5 最小最小 10 - 3 4 - 3 = 1 10 - 2 第90页/共100页第九十一页，共100页。(4,3)(1, 8)(2, 4)(1,7)(2, 4)(6, 0)(4,4)在最短在最短路上路上(l shng)增增加流量加流量 = 1得新的得新的流量流量f (4) =11V1 V2 V3 Vt 第91页/共100页第九十二页，共100页。(4,3)(1, 8)

32、(2, 4)(1,7)(2, 4)(6, 0)(4,4)*注意注意(zh y)在负向在负向弧上减弧上减去增量去增量值值V1 V2 V3 Vt 5 - 1 第92页/共100页第九十三页，共100页。上一次上一次的赋权的赋权图图*依据依据新新流量流量(liling)在最在最短路径短路径上上对此重对此重求求赋权值赋权值V1 (4,2)(2, 3)(-1,7)(6, 0)(4,3)V1 V2 V3 Vs Vt (-2, 5)(-4,2)(-1, 8)(-4,3)(-2, 3)第93页/共100页第九十四页，共100页。依据新依据新的流量的流量(liling)构造又构造又一赋权一赋权图图W(f (4)

33、*只对增只对增广链广链V1 (4,3)(2, 4)(-1,7)(6, 0)(4,4)V1 V2 V3 Vs Vt (2, 4)(1, 8) 10 5 10 4 0 0 ijijijjiijijijijijijffbwcfcfbw第94页/共100页第九十五页，共100页。依据新依据新的流量的流量构造构造(guzo)又又一赋权一赋权图图W(f (4)*只对增只对增广链广链V1 (4,3)(-2, 4)(-1,7)(6, 0)(3,4)V1 V2 V3 Vs Vt (-2, 4)(-4,3)(-1, 8)(-3,4)(2, 4)第95页/共100页第九十六页，共100页。没有最短路，没有最短路，算法结束，算法结束，所得所得(su d)为最小费用为最小费用最大流最大流V1 (4,3)(-2, 4)(-1,7)(6, 0)(3,4)V1 V2 V3 Vs Vt (-2, 4)(-4,3)(-1, 8)(-3,4)(2, 4)第96页/共100页第九十七页，共100页。第97页/共100页第九十八页，共100页。第98页/共100页第九十九页，共100页。第99页/共100页第一百页，共100页。