The connectivity of hypergraph and the design of fault-tolerant multibus systems

摘要

The authors introduce hypergraph as the mathematical model of multibus systems. The fault-tolerance problem of the multibus system is transformed into the connectivity problem of hypergraph. First, an important inequality related to all hypergraphs is stated and proved, and when equality takes place, the hypergraph with the best connectivity is defined. Second, to find the hypergraph with the best connectivity, BIB (balanced incomplete block) design is borrowed from combinatorics and at least W (weak) BIB is generalized. The designs obtained by this theory are better than the existing results under the same condition. The main goal of this study is to bridge these three fields: multibus system design, hypergraph, and BIB design.