Military information monitoring by radar station in communication network. It is very important that the network can still function well even if some nodes are destroyed during a period of time. In the following network node 1,6,13 and 15 are supposed to be four radar stations,and node 5 is a military command center. the network is named “k degree safe”between node x and y if x and y can still transmit information between each other while any k-1 nodes in the network are destroyed.
军事情报是依靠在通信网络中的雷达站来监测的。非常重要的一条是要保障即使某些节点在一段时间内被摧毁，网络仍然可以发挥良好的作用。在下面的网络中节点1,6,13和15被认为是4个雷达站，节点5是一个军事指挥中心。网络被命名为“ K可靠度”，如果节点X和Y之间仍然可以传递信息，即使任何K – 1个节点在网络中被摧毁。
Problem 1. Analysis safe degrees between radar station 6 and command center 5. Dotted lines represent candidate edges which can be added, and digitals beside the edges represent costs of the corresponding edges added. How can we increase one safe degree between 6 and 5 by increasing minimum number of edges? Which nodes should added to increase one safe degree between 6and 5, 1 and 5, 13 and 5, as well as 14 and 5 and with minimal total costs? Discuss safe degree problem model with general network.
问题1 。分析雷达站6和指挥中心5之间的安全度
。虚线代表可以增设的边，边上的数字代表补充边的费用。我们怎样才能在6和5之间，通过增加最低数量的边增加一个可靠度？
为了在6 和 5 ， 1和5， 13和5，以及14和5之间增加一个可靠度，应该增加哪些节点，以使得总费用最小？一般的网络模型上讨论可靠度问题。
Problem 2. If node 4,node 5 and node 10 are three data processing centers which can process multiple data contemporary, while other nodes can only receive data form one of its neighbor nodes at the same time .When information from radar station 1,6,13 and 15 must be delivered to node 2,5,7,11 and 12,and the sizes of information denoted by deliver time (unit:second) is listed as the following table (other time delay can be neglected).Suppose message deliver can be continued after disruption. Design the optimal information deliver order algorithm which results the minimum total completion time.
