运筹学06图与网络分析PPT学习教案

1、会计学1 运筹学运筹学06图与网络分析图与网络分析 第1页/共115页 第2页/共115页 第3页/共115页 A B C D v 哥尼斯堡七桥问题：在图中 找一条经过每边一次且仅一 次的路欧拉回路。 A D B C 由点和边组成由点和边组成 第4页/共115页 第5页/共115页 第6页/共115页 第7页/共115页 1 v 2 v 3 v 4 v 1 e 2 e 3 e 4 e 5 e 6 e 7 e 第8页/共115页 1 v 2 v 3 v 4 v 1 e 2 e 3 e 4 e 5 e 6 e 5 v 第9页/共115页 第10页/共115页 第11页/共115页 第12页/共11

2、5页 第13页/共115页 第14页/共115页 v1 v2v3 v4 v5 a1 a2 a3 a4 a5 a6 a7 d-(v1)=1；d+(v1)=3 d-(v2)=1；d+(v2)=1 d-(v3)=1；d+(v3)=2 d-(v4)=3；d+(v4)=0 d-(v5)=1；d+(v5)=1 第15页/共115页 第16页/共115页 第17页/共115页 v1 v2 v3 v4 v5 终点 v1v2v3v4v5 起 点 v101100 v210011 v310001 v401001 v501110 第18页/共115页 终点 v1v2v3v4v5 起 点 v1032 v23054 v3

3、208 v4502 v54820 v1 v2 v3 v4 v5 4 2 3 2 5 8 第19页/共115页 终点 v1v2v3v4v5 起 点 v1032 v2054 v3608 v4 02 v5 0 v1 v2 v3 v4 v5 4 2 3 2 5 8 6 第20页/共115页 第21页/共115页 第22页/共115页 第23页/共115页 第24页/共115页 第25页/共115页 深探法 广探法 第26页/共115页 第27页/共115页 第28页/共115页 第29页/共115页 第30页/共115页 根 叶 分点枝 第一层 第三层 第二层 三叉树 第31页/共115页 第32页/

4、共115页 123243 3 6 5 第33页/共115页 123243 3 9 6 5 15 12 3 2 4 3 3 9 6 5 15 第34页/共115页 第35页/共115页 第36页/共115页 第37页/共115页 第38页/共115页 第39页/共115页 第40页/共115页 v4 v2 v1 v3v6 v5 v7 1 4 4 253 1 6 2 2 7 第41页/共115页 序号 与S关联边距离集合S标号 (0)d(v1)=0v1d(v1)=0 (1) (v1,v2) (v1,v3) k12=d(v1)+l(v1,v2)=0+1= 1 k13=d(v1)+l(v1,v3)=0

5、+4= 4 v1,v2 d(v2)=1 v1 (2) (v1,v3) (v2,v3) (v2,v4) (v2,v5) (v2,v6) k13=d(v1)+l(v1,v3)=0+4= 4 k23=d(v2)+l(v2,v3)=1+2= 3 k24=d(v2)+l(v2,v4)=1+4= 5 k25=d(v2)+l(v2,v5)=1+7= 8 k26=d(v2)+l(v2,v6)=1+5= 6 v1,v2, v3 d(v3)=3 v2 k24=d(v2)+l(v2,v4)=1+4= 5 k25=d(v2)+l(v2,v5)=1+7= 8 k26=d(v2)+l(v2,v6)=1+5= 6 k36=

6、d(v3)+l(v3,v6)=3+1= 4 第42页/共115页 序号 与S关联边 距离集合S标号 (4)(v2,v4) (v2,v5) (v6,v5) (v6,v7) k24=d(v2)+l(v2,v4)=1+4=5 k25=d(v2)+l(v2,v5)=1+7=8 k65=d(v6)+l(v6,v5)=4+3=7 k67=d(v6)+l(v6,v7)=4+6=1 0 1,2,3, 6,4 d(v4)=5 v2 (5)(v4,v5) (v2,v5) (v6,v5) (v6,v7) k45=d(v4)+l(v4,v5)=5+2=7 k25=d(v2)+l(v2,v5)=1+7=8 k65=d(

7、v6)+l(v6,v5)=4+3=7 k67=d(v6)+l(v6,v7)=4+6=1 0 1,2,3, 6,4,5 d(v5)=7 v4,v6 (6)(v5,v7) (v6,v7) k57=d(v5)+l(v5,v7)=7+2=9 k67=d(v6)+l(v6,v7)=4+6=1 0 1,2,3, 6,4,5,7 d(v7)=9 v5 v最短运输路线：(1)v1-v2-v4-v5-v7或(2)v1-v2-v3-v6-v5-v7 v最短距离=d(v7)=9 第43页/共115页 第44页/共115页 k1234567 10* 21*14 33*2586 4584*3 55*2710 67*4,

8、610 79*5 11 11111 11111 11111 11111 11111 11111 11111 最短运输路线:(1)1-2-4-5-7;(2)1-2-3-6-5-7 最短距离:d=9 第45页/共115页 第46页/共115页 第47页/共115页 v1v2v3v4v5v6v7 v1014 v2102475 v34201 v4402 v572032 v651306 v7260 第48页/共115页 v1v2v3v4v5v6v7 0v1014 v2102475 v34201 v4402 v572032 v651306 v7260 v(2)找到起始点v1，第1行标号0，划去第1列 第4

9、9页/共115页 v1v2v3v4v5v6v7 0v1014 1v2102+14+17+15+1 v34201 v4402 v572032 v651306 v7260 第50页/共115页 v1v2v3v4v5v6v7 0v1014 1v2103586 3v34201+3 v4402 v572032 v651306 v7260 第51页/共115页 v1v2v3v4v5v6v7 0v1014 1v2103586 3v34204 v4402 v572032 4v6513+406+4 v7260 第52页/共115页 v1v2v3v4v5v6v7 0v1014 1v2103586 3v34204

10、5v4402+5 v572032 4v6517010 v7260 第53页/共115页 v1v2v3v4v5v6v7 0v1014 1v2103586 3v34204 5v4407 7v572032+7 4v6517010 v7260 第54页/共115页 v1v2v3v4v5v6v7 0v1014 1v2103586 3v34204 5v4407 7v572039 4v6517010 9v7260 第55页/共115页 第56页/共115页 第57页/共115页 第58页/共115页 v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7 v1 014 v1 013

11、585 v2 102475v2 1024639 v3 420 1v3 3206417 D(0)= v4 402 D(1)= v4 5460254 v5 72032v5 8642032 v6 51306v6 5315305 v7 260v7 974250 111 1111111111111111111111111 111 111111111111111111111111 v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7 v1 0135749v1 0135749 v2 1024638v2 1024638 v3 3206416v3 3206416 D(2)= v4 5

12、460254D(3)= v4 5460254 v5 7642032v5 7642032 v6 4315305v6 4315305 v7 9864250v7 9864250 第59页/共115页 12 3 4 5 6 7 2 2 2 3 34 4 4 5 6 7 7 1 第60页/共115页 03470345711 13 303243032458 430574305569 D(0)= 72026D(1)= 5250236 4520147452013 710211563102 642013896320 111 1111111111111111111111 111 11111111111111111

13、1111 0345781003457810 30324573032457 43055684305568 D(2)= 5250235D(3)= 5250235 74520137452013 85631028563102 1078532010785320 第61页/共115页 1 2 3 4 5 6 7 8 9 10 7 2 8 6 12 12 2 4 2 4 5 6 5 10 4 6 2 6 8 8 4 第62页/共115页 12345678910 10886 2042 301072 408 D(0)=560212 604 71205 8064 96204 1050 111111 111 111

14、 111 111 111 111 111 111 111 111 第63页/共115页 12345678910 10886151010 2041411627 313010726 40812 D(1)=561002861816 604108 718121405119 81289064 9629604 10175100 111111 111 111 111 111 111 111 111 111 111 111 第64页/共115页 12345678910 10886151010142018 20414116271311 313010721561210 40821121816 D(2)=56101

15、802861210 616250134108 7182217121305119 827122189064 92762129604 102327221718510160 111111 111 111 111 111 111 111 111 111 111 111 第65页/共115页 12345678910 10886151010142018 20414116271311 313010721561210 43943033821121816 D(3)=56101802861210 6313516250134108 7182217121305119 82731122189064 9273162129

16、604 102327221718510160 111111 111 111 111 111 111 111 111 111 111 111 第66页/共115页 12345678910 10886151010142018 20414116271311 313010721561210 43943033821121816 D(4)=56101802861210 6313516250134108 7182217121305119 82731122189064 9273162129604 102327221718510160 111111 111 111 111 111 111 111 111 111

17、 111 111 第67页/共115页 12345678910 108818151010142018 2200414116271311 31613010721561210 461414021816121816 D(4)=5246101802861210 622303016250134108 723182217121305119 8182626122189064 912202062129604 10282327221718510160 111111 111 111 111 111 111 111 111 111 111 111 第68页/共115页 12345678910 10881815101

18、0142018 280414116271311 3412010721461210 4-622094481412 D(4)=5126101802861210 610181816250134108 711181917121305119 861414122189064 908861529604 10162324221718510160 111111 111 111 111 111 111 111 111 111 111 111 第69页/共115页 第70页/共115页 第71页/共115页 第72页/共115页 第73页/共115页 第74页/共115页 第75页/共115页 第76页/共115页

19、 第77页/共115页 第78页/共115页 第79页/共115页 1 2 3 4 5 6 4 4 82 2 1 4 6 7 9 第80页/共115页 序号 V1V2c(u,v)fiY Vf (1)12,3,4,5,6 c(1,2)=4；c(1,3)=8 12 8 (2) 1,23,4,5,6c(2,3)=4；c(2,4)=4 c(2,5)=1；c(1,3)=8 17 (3) 1,32,4,5,6c(1,2)=4；c(3,4)=2 c(3,5)=2 8 Y (4) 1,2,34,5,6c(2,4)=4；c(2,5)=1 c(3,4)=2；c(3,5)=2 9 (5) 1,2,3,45,6c(2

20、,5)=1；c(3,5)=2 c(4,6)=7 10 (6) 1,2,3,54,6c(2,4)=4；c(3,4)=2 c(5,4)=6；c(5,6)=9 21 (7) 1,2,3,4,5 6c(4,6)=7；c(5,6)=9 16 第81页/共115页 ABCDEFGH 1 From To Captio n FlowNodes NetFlow Conditio n 2124418 3138420 0 4234030 0 5244440 0 6251050 0 734226-8 83522 94677 105461 115691 =SUMIF($A$2:$A$11,F2,$D$2:$D$11)-

21、 SUMIF($B$2:$B$11,F2,$D$2:$D$11) 第82页/共115页 第83页/共115页 第84页/共115页 第85页/共115页 第86页/共115页 vs v2v3 vtv1 (4,10) (1,8) (2,5) (1,7) (6,2) (3,10) (2,4) 第87页/共115页 vs v2v3 vtv1 4 1 2 1 6 3 2 W(f(0) vs v2v3 vtv1 0 5 5 5 0 0 0 f(1),v(f(1)=5 第88页/共115页 vt vs v2v3 v1 2 5 5 7 0 0 0 f(2),v(f(2)=7 vs v2v3 vtv1 4 1

22、 -2 1 6 3 2 W(f(1) -1 -1 第89页/共115页 vt vs v2v3 v1 2 8 5 7 0 3 3 f(3),v(f(3)=10 vs v2v3 vtv1 4 1 -2 6 3 2 W(f(2) -1 -1 -4 第90页/共115页 vt vs v2v3 v1 3 8 4 7 0 4 4 f(4),v(f(4)=11 vs v2v3 vtv1 4 -2 6 3 2 W(f(3) -1 -1 -4 -2 -3 第91页/共115页 vs v2v3 vtv1 4 -2 6 3 W(f(4) -1 -1 -4 -2 -3 2 第92页/共115页 ABCDEFGHI 1

23、 From To Captio n Flow CostNodes NetFlow Conditio n 2vsv11034vs1111 3vsv2881v100 4v1v3206v200 5v1vt771v300 6v2v1542vt-11 7v2v31043 8v3vt442 955 (1)Max (2)Min 第93页/共115页 第94页/共115页 vs v2v3 vtv1 (10,4) (8,1) (5,2) (7,1) (2,6) (10,3) (4,2) (0,-4) (0,-1) (0,-2) (0,-3) (0,-6) (0,-1) (0,-2) 第95页/共115页 vs

24、v2v3 vtv1 (10,4) (3,1) (0,2) (2,1) (2,6) (10,3) (4,2) (0,-4) (5,-1) (5,-2) (0,-3) (0,-6) (5,-1) (0,-2) 第96页/共115页 vs v2v3 vtv1 (8,4) (3,1) (0,2) (0,1) (2,6) (10,3) (4,2) (2,-4) (5,-1) (5,-2) (0,-3) (0,-6) (7,-1) (0,-2) 第97页/共115页 vs v2v3 vtv1 (8,4) (0,1) (0,2) (0,1) (2,6) (7,3) (1,2) (2,-4) (8,-1) (5,-2) (3,-3) (0,-6) (7,-1) (3,-2) 第98页/共115页 vs v2v3 vtv1 (7,4) (0,1) (1,2) (0,1) (2,6) (6,3) (0,2) (3,-4) (8,-1) (4,-2) (4,-3) (0,-6) (7,-1) (4,