圖的可靠度

Abstract

近十年來，機率圖模型已被廣泛的應用在計算機和通訊網路的可靠度分析上。本論文討論圖的可靠問題中，假設所有的邊都是完好的，而每個節點都有各自獨立損壞的機率。更精確的說，假設 是一連通圖，其中有一給定的目標集 ，而且每一 中的節點v有一好的機率 ；圖G的可靠度是使T在T及所有 中好的節點所誘導出來子圖中同一連通子圖的機率，也就是 本論文主要在證下列圖類可靠度的演算法：區塊圖、仙人掌圖、圈及並串聯圖。

Probability graph models have been widely used for the last few decades as models for reliability analysis of computer and communication networks. In this thesis, we study a reliability problem for graphs in which the links are perfectly reliable and the vertices fail independently with known probabilities. More precisely, suppose is a graph with a given target set and each vertex has a working probability . The reliability of G is the probability that T is in a component of the subgraph induced by T and the working vertices. Formally, the reliability is The main results of this thesis is to design efficient algorithms for the problems in block graphs, cactus graphs, and series-parallel graphs.