可能性最小生成樹問題之單一關鍵聯結

On the Single Most Vital Arc of Possibilistic Minimum Spanning Tree Problems

若某個聯結被從網路移去時會導致網路績效下降最大，則該聯結稱為網路的單一關鍵聯結。當聯結權數為模糊數或隨機變數時，網路使用者之決策模式會影響其決策，進而影響各個聯結之重要程度。因此，在這兩種情況下，對於關鍵聯結問題，必須依網路使用者之決策模式是否為已知分別進行討論。本文首先針對網路使用者之決策模式為已知且是採用期望值模式選取生成樹的情況，探討聯結權數為模糊數之最小生成樹的單一關鍵聯結問題。由於實務上經常無法事先得知決策者的特性，因此本文提出一個能同時求得各種決策者特性所對應之單一關鍵聯結的方法。接著，針對網路使用者之決策模式為未知的情況，利用林高正與陳茂生所提出的概念設計出聯結權重為模糊數之最小生成樹的單一關鍵聯結解法。

An arc, whose removal from the network will lead to the maximum decrease in network performance, is called a single most vital arc. In this paper, it is pointed out that the problem of finding a single most vital arc in a network with possibilistic or stochastic arc weights should be divided into two situations. One situation is that the decision model of the network user is known in advance. Here, it is assumed that the user selects a spanning tree using the expected value model. However, in practice, the characteristic of the user usually can’t be known in advance. Therefore, we propose a parametric analysis method for the single most vital arc in this situation. The other situation is that the decision model of the network user is not known. For this situation, we use Lin and Chern’s approach to propose an algorithm for finding a single most vital arc.