网络与现实生活中的数问题研究
网络与现实生活中的数问题研究
拓扑学上的网络通常是在各地理位置间画出连接线所形成的．网络的每一段弧线可给予一数字，代表结点间的距离、经过两点所需的时间或连接两点间的电话线路数目等．对有些问题可以用这种方法找到实用而且具有商业价值的答案．本课题即探讨解决这类问题的多种方法．
最短距离的连接
把数字当作距离(千米)，点当作城镇，找出煤气公司铺设连接所有城镇的煤气管道的最短长度．这个问题是要决定哪一段弧线可以不在网络内，但任何城镇并不被孤立在外，同时弧线的总长度是最短的．
这个例子的最佳答案如图所示．你的答案是否相同？更重要的是要知道如何求解，你是否了解其策略？是否可以用这种策略来解决类似的问题？
巡查街道
把弧线当作警察巡逻区域内的街道路线，弧线上的数字当作走完每条街道所需的时间(分钟)．如果警察自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点的用户同时通话的最大数目．