图论应用

---

最小生成树

image.png

最小生成树算法有很多，其中最经典的克鲁斯卡尔（Kruskal）算法和 普里姆（Prim）算法

• 克鲁斯卡尔（Kruskal）
  在所有线中，找图中最小的边，并且不形成环形

image.png

总长：2+3+3+4+5+6 = 23

最短路径

• 例子1

image.png

解法：
从S点触发，计算到每个节点的最短路径，一直结算到T，然后根据T的最小值反推出路径的走法。

image.png

• 例子2:

image.png

解法：

image.png

网络与最大流量

下图标出了某地区的运输网，各节点之间的运输能力如下表所示。那么，从节点1到节点6的最大运输能力 (流量) 可以达到多少万吨/小时?

image.png

解法：
先把表格转换为图，如下，并标上流量

表格转换后的图

找到到达节点6的路线，并减去其中最小的值。

image.png 直到无法到达

把所有减掉的值加载一起：10+6+5+1+1 = 23 就是答案

运筹规划

---

线性规划

image.png

解答：

image.png

动态规划

image.png image.png

排队论

image.png
设8点前已排队等候的人数为A，每分钟可以来Z人，每个入口每分钟能进Y人。
1式: 8*60*Y=60*Z+A
2式: 10*40*Y=40*Z+A

1式减2式得:
3式: 80Y=20Z
把3式代入1式得:
4式: A=240Y
所以要20分钟消除排队现象则有：（假设需要开口X个）X*20*Y=20*Z+A
把3式和4式带入，则是：X*20*Y=20*(4Y)+240Y
求得X=16。
所以8:00应开入口16个，而8:20由于消除了排队，开口数量只需要4个就行了依据:80Y=20Z。

博弈论

image.png

状态转义矩阵

image.png
解答

• 第二题

  
  image.png
  解答

不确定决策

image.png

• 等可能

  
  image.png

• 后悔值

  
  image.png

决策树

image.png
解答

匈牙利指派法

问题
1
2 3


非标准形式的指派问题