§4.7 应 用 举 例 例1：比赛安排问题.ppt

§4.7 应 用 举 例 ;解：;例 2.线路铺设问题;解：求各边相通且总费用最少的方案，实际上求最小树，保证了各点之间连通且费用最少。;例3.设备更新问题;解：为解决好这一问题，建立下述网络模型，并用最短路法求解。;v4;例4.房屋设计问题;I;令所有边的权为1，为了使开的门尽可能少，就要使这个连通子图的生成子图的边尽可能少，即求图的最小生成树。;例5：选址问题;解：首先计算各点对间的最短路，每个学习者为使所走的路程最短，应走最短路。;V1 V2 V3 V4 V5 V6 ;;例 6：网络运输容量问题;仓库;增设一发点S，连接S与Ai，容量为Ai的供应量；增设一收点T，连接Bi与T，容量为Bi的需求量，得到如下的网络。 问题转化成求S到T的最大流问题。;S;例8：分派问题;用顶点A1，A2，A3，A4，A5表示5位副驾驶员； B1，B2，B3，B4，B5表示5位正驾驶员； 若正、副驾驶员可同机飞行，则在对应的点之间连一条弧，方向由A指向B； 增设一个起点S和终点T，得到下图，各弧的容量均为1。;S;fmax=4，知道最多能有4架飞机同时出航。 分配方案为： A2 - B1；A3 - B4 ; A4 - B2；A5 - B5;例9：桥梁切断问题;解：;B (A,1);例11:生产计划问题;解：构造网络图如下;Thanks！