问题 单项选择题

某省A城市至J城市之间的通信网络如图所示,其中各线段旁标示的数字为该段线路相应时段可供分配的最大实际通信流量,单位为Mbps。从A城市至J城市单位时刻的最大通信流量为()Mbps。

A.75

B.41

C.30

D.26

答案

参考答案:C

解析:

从图论上看,本题就是求节点A到节点J单位时刻的最大通信流量,其算法类似于求最短路径的方法。采用倒推标记方法进行推算的解题步骤如下。

①先找出离终点J只有一步的节点H、I,由于26<30,因此选择路径I-J,并标记出节点I到达终点J的流量。同时,删除前往节点H只有一步的节点E、F、G之间的路径。

②再找出前往节点I只有一步的节点E、F、G,对其中每个节点,找出其到终点J单位时刻的最大通信流量,分别将其路径与流量标记出来。例如,节点E到达节点J单位时刻的最大通信流量取决于路径E-I的通信流量28Mbps;同理,节点F到达节点J单位时刻的最大通信流量取决于路径I-J的通信流量30Mbps。由于28(E-I-J)<30(F-I-J或G-I-J),因此选择路径F-I-J和路径G-I-J。同时,删除前往节点E只有一步的节点B、C、D之间的路径。

③再找前往节点F、G只有一步的节点B、C、D,对其中每个节点,找出其到终点J单位时刻的最大通信流量,分别将其路径与流量标记出来。由于后续路径的通信流量已经标记出来,因此应利用它们来简化计算。例如,节点C到达节点J可选的路径及单位时刻最大通信流量值如下:C-F-I-J(22),C-G-I-J(30),由于30>22,因此选择路径C-G-I-J。依此类推,节点B、C、D分别到达终点J的路径以及单位时刻最大通信流量值如下:B-F-I-J(30),B-G-I-J(30),C-G-I-J(30),D-G-I-J(30)。

④最后,找出节点A分别通过节点B、C、D一直到终点J的路径中单位时刻最大通信流量的路径,并标记出来,即A-C-G-I-J(30)和A-D-G-I-J(30),如下图所示。

综上所述,从A城市至J城市的单位时刻最大通信流量值为30Mbps,共有两条路径:A-C-G-I-J和A-D-G-I-J。

多项选择题
单项选择题