查看: 3217|回复: 4

讨论!!!

字体大小: 正常放大

Yang168

14 主题	3 听众	55 积分

升级 52.63%

TA的每日心情

	开心 2013-4-6 00:12

签到天数: 1 天

[LV.1]初来乍到

电梯直达

1^#

发表于 2009-1-15 16:04 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

Radar station problem

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.

问题2 。如果节点4，5和10是三个数据处理中心，可以同时处理多个数据，而其他节点在同一时间只能从相邻的一个节点接受数据。当信息需要从雷达站1,6,13和15发送到2,5,7,11和12 ，数据量的大小通过传输时间来衡量（单位：秒），将数据列为下表（其他时间延迟可以忽略不计）
。假设信息传输可以在中断之后继续。设计最佳的信息传送顺序算法，以达到最短的完成时间。