When each edge in a network system has random multistate capacities depending on the degree of failure, the probability of successfully transmitting the required amount of information between two specified vetices is evaluated by backtracking search and decomposition algorithm. Doulliez and Jamoulle analyzed the problem using decomposition principle and the Ford-Fulkerson algorithm. However, they didn't introduce the notion of minimal path vector, and Ford-Fulkerson algorithm cannot be efficiently adopted to the present problem. This thesis develops a systematic procedure using the concept of minimal path vectors to overcome this difficulty. Furthermore, there has been no works on the edge importance when a network has random edge capacity. This thesis adopts the importance measure used in multistate system analysis, and points out several difficulties when this measure is adopted to this problem.
본 연구에서는 다단계 고장을 가지는 각 간선(edge)들로 구성된 네트워크 체계에서 임의의 두 점 사이에 요구된 량이 흐를 수 있는 확률값을 구하는 문제를 다루었다. 본 연구는 최대 흐름의 최소 컷(cut) 공리를 이용하여 문제를 수식화 하였고, 이에 Backtracking Search 와 Decomposition 원리를 적용하여 해결하였다. Doulliez 와 Jamoulle는 수정된 Ford-Fulkerson 알고리즘을 이용하여 문제를 해결하였으나, 이는 계산상으로 효율적이지 못하다. 따라서, 본 논문에서는 최소 컷과 패스벡터의 개념을 이용한 체계적인 방법을 개발하였다. 또한 본 논문의 문제와 같은 물리적 구조를 하는 네트워크 체계에서 각 간선의 중요성을 구별하는 적당한 기준이 없음을 상기하여, 신뢰도 이론에서 사용된 기준을 도입하였고 이 기준이 갖는 장단점에 대해 연구하였다.
