Abstract
給一評估網路績效之測度，若某組聯結滿足給定的限制條件，且將它從網 路中移去會使網路之績效降低最多，則該組聯結稱為網路的關鍵聯結。在 網路規劃的實務中，聯結之可用性扮演著重要的角色。關鍵聯結問題之目 的在評估聯結可用性的重要程度。因此，它提供有關網路維護與破壞所需 的資訊。此外，本文也考慮一個更一般化的問題，稱為阻撓問題。該問題 是經由提高網路聯結之權數以降低網路績效。當問題的決策變數為二元變 數時，則稱為二元阻撓問題。換言之，二元阻撓問題之目的在決定應破壞 那些聯結。而當聯結遭破壞時，它的權數將增加一給定數量﹔否則，聯結 的權數維持不變。若所增加的聯結權數為足夠大時，則該問題變成一個關 鍵聯結問題。 Given a network performance measure, the most vital edges problem is to find a set L* of edges whose removal from the network results in the greatest decrease of the performance. Furthermore, L* satisfies a set of specified constraints. The availability of edges plays a key role in the design of network systems. The most vital edges problem provides a means by which the importance of edge's availability can be measured. Thus, it can be used in network maintenance and network interdiction. In addition to the most vital edges problem, it is natural to consider a generalized problem in which the performance of a network is reduced via increasing (or decreasing) the edge weights. Such a problem is called an interdiction problem. When the decision variables of an interdiction problem are binary, it is called a binary interdiction problem. In other words, the purpose of a binary interdiction problem is to determine which edges should be interdicted. Moreover, when an edge is interdicted, its weight is increased (or decreased) by a specified value. If the specified values are sufficiently large, then the problem is reduced to the most vital edges problem.