最小生成树

image.png

最短路径：n - 1 => 9-1=8    只需要八条路径就可连接全部
先从成本最小的开始连，连完之后看是否有环路，有环路的路径去掉，连完八条路径后就是最小的路径

image.png

从最短的距离开始找

最短路径

image.png

依次求取A->B, A-C,A->D,A->E的最短路径，最终求取A->F 的最短路径
A->B: 11
A->C: (1) A直接到C，从图中可得 16
        （2）A->B + B->C ==>11+13=24
           ===> A->C的最短路径为A直接到C，为16
A->D: (1) A直接到D，从图中可得 24
        （2）A->B + B->D ==>11+16=27
        （3）A->C + C->D ==>16+14=30
           ===> A->C的最短路径为A直接到D，为24
A->E: (1) A直接到E，从图中可得 36
        （2）A->B + B->E ==>11+21=32
        （3）A->C + C->E ==>16+17=33
        （4）A->D + D->E ==>24+14=38
          ===> A->C的最短路径为（2）A->B + B->E ，为32
A->F: (1) A直接到F，从图中可得 54
        （2）A->B + B->F ==>11+29=40
        （3）A->C + C->F ==>16+22=38
        （4）A->D + D->F==>24+17=41
        （5）A->E + E->F ==>32+15=47
          ===> A->C的最短路径为（3）A->C + C->F ，为38

网络与最大流量

image.png

• 解答：

  
  
  image.png
  
  
  image.png

（0）把所有运输能力标注在图中
（1）先走1->3->5->6 这条路，10、14、21最小值为10 ，每个路径都减10 ，等于0的路就断掉，断掉1->3 => 这条路运输能力为10
（2）走1->2->5->6,  6、7、11，最小值为6，都减去6，断掉1->2 ，=>这条路运输能力为6
（3）走1->4->6,  5、10，最小值为5，都减去5，断掉4->6， =>这条路运输能力为5
（4）走1->4->3->5->6,  5、1、4、5，最小值为1，都减去1，断掉3->4， =>这条路运输能力为1
（4）走1->4->2->5->6,  4、4、1、4，最小值为1，都减去1，断掉2->5， =>这条路运输能力为1
结论： 最大运输能力 10+6+5+1+1 = 23

image.png

B->M->X , 运10，B->M, M->X断掉
B->N->Y,  运10, B->N 断掉
A->M->Y, 运5， M->Y断掉
A->M->N-Y, 运10，A-M，M-N，N-Y断掉
C->N->Z,运20，C-N断掉
结论 10+10+5+10+20 = 55

线性规划

image.png

image.png

• 解答：

  
  
  image.png