网络与现实生活中的数问题研究


 

  拓扑学上的网络通常是在各地理位置间画出连接线所形成的.网络的每一段弧线可给予一数字,代表结点间的距离、经过两点所需的时间或连接两点间的电话线路数目等.对有些问题可以用这种方法找到实用而且具有商业价值的答案.本课题即探讨解决这类问题的多种方法

  最短距离的连接

  把数字当作距离(千米),点当作城镇,找出煤气公司铺设连接所有城镇的煤气管道的最短长度.这个问题是要决定哪一段弧线可以不在网络内,但任何城镇并不被孤立在外,同时弧线的总长度是最短的.

  这个例子的最佳答案如图所示.你的答案是否相同?更重要的是要知道如何求解,你是否了解其策略?是否可以用这种策略来解决类似的问题?

  巡查街道

  把弧线当作警察巡逻区域内的街道路线,弧线上的数字当作走完每条街道所需的时间(分钟).如果警察自A点出发,应该如何走才能以最少的时间走过每条街道?

  如果网络具有穿程性(即可以不重复地走完每一段弧线),则求解就比较容易,但图中的网络不具有穿程性.不过求解时还是要先了解穿程性所要求的条件,可重复几段弧线而有效地将网络转化为具有穿程性的网络.

   本例所需的最少时间为65分钟,路线如下:

  A→G→B→C→B→A→C→D→A→D→E→F→G→E→A

  7 11 4 4 5 2 4 3 3 7 3 2 4 6

  推销员的旅行问题

 

  有一位住在B的推销员想要拜访所有的客户(以网络上的结点表示).弧线上的数字代表各路线的旅行时间(小时).你如何建议这位推销员在最短的时间内走完访问行程?有4种方法可以用32小时走完访问行程.你能否提出一般性的策略来解决这一类问题?

  最短的路径及最长的路径

  对如上所述的简单网络,求取网络上结点间的最短路径是相当明显的问题.但在较复杂的网络中,尤其是在有些弧线上有方向箭头标示“单向”时,求解就变得耐人寻味了.

  我们可以用结点来表示在某段时间发生的事件,如学校音乐会的筹备活动,箭头上的数字表示所需时间(周),如从预订服装至送到的时间,那么筹备此音乐会的复杂过程就可以用有方向性的网络来表示,所需的最长路径称为临界路径 (critical path),可以由此算出筹备音乐会所需的最少时间.

  最大流量

  假设第一个网络的结点为电话交换机,弧线上的数字是交换机之间的线路数,探讨G点的用户可以与C点的用户同时通话的最大数目.