On Computing the Edge-Connectivity of an Uncertain Graph

作者:Gao, Y (Gao, Yuan)^{[ 1 ]} ; Qin, ZF (Qin, Zhongfeng)^{[ 2 ]} 

Uncertain graphs are employed to describe graph models with imprecise expert data. In uncertain graphs, due to the existence of uncertain edges, edge-connectivity is essentially an uncertain variable. Different from that in a deterministic graph, it is more suitable to investigate the possibility (uncertain measure) that an uncertain graph is k-edge-connected, which is the main aim of this paper. We first deduce a theoretical formula to calculate the uncertain measure, and on this basis, we then propose an algorithm, which is derived from maximum flow algorithms, to numerically calculate the uncertain measure. The proposed algorithm is also proved to be a polynomial time algorithm, and its effectiveness and efficiency are illustrated by numerical examples.