C(us)=3 T(e)=4 C(t)=1 T(e,)=3es T(cs)=6)c(v)=1 T(e2)=3|e T(e4)= v C(v1)=1T(e)=5c(v)=2 图9B1文件传输网络的例子 顶点从VV2…J表示计算机,边e1,e2…em表示(由边的端点表示的计算机 之间要传输的文件。T(e)表示传输文件乙所需的时间,C(,)表示计算机V,同 时能传输多少个文件的容量。文件传输包括占用有关计算机为传输该文件所需的 全部时间。 C(,)=1表示计算机V,一次只能传输一个文件 我们有兴趣的是以最优的方式安排传输,即使得传输完所有的文件所用的总 时间最小。这个最小总时间称为接通时间( makespan)。请为你们的公司考虑以下 三种情形: 情形A 你们公司有28个部门。每个部门有一台计算机,在图94B-2中每合计算机 用顶点表示。每天必须传输27个信息,在图94B-2中用边来表示。对于这个网 络,对所有的xyT(e2)=1,C()=1.试找出该网络的最优安排以及接通时 间。你们能向你们的主管人员证明你们对该网络求得的接通时间是最小可能(最 优)的吗?叙述你们求解该问题的方法。你们的方法适用于一股情形吗,即是否适 用干了T(e2),C(V)以及图结构都是任意的情形?顶点从 V1，V2VM 表示计算机，边 m e ,e ,e 1 2 表示(由边的端点表示的计算机 之间)要传输的文件。 ( ) x T e 表示传输文件乙所需的时间， ( ) C Vy 表示计算机 Vy 同 时能传输多少个文件的容量。文件传输包括占用有关计算机为传输该文件所需的 全部时间。 ( ) C Vy ＝1 表示计算机 Vy 一次只能传输一个文件。 我们有兴趣的是以最优的方式安排传输，即使得传输完所有的文件所用的总 时间最小。这个最小总时间称为接通时间(makespan)。请为你们的公司考虑以下 三种情形： 情形 A； 你们公司有 28 个部门。每个部门有一台计算机，在图 94B-2 中每合计算机 用顶点表示。每天必须传输 27 个信息，在图 94B-2 中用边来表示。对于这个网 络，对所有的 x,y ( ) x T e ＝1， ( ) C Vy ＝1 ．试找出该网络的最优安排以及接通时 间。你们能向你们的主管人员证明你们对该网络求得的接通时间是最小可能(最 优)的吗?叙述你们求解该问题的方法。你们的方法适用于一股情形吗，即是否适 用干了 ( ) x T e ， ( ) C Vy 以及图结构都是任意的情形?