摘要：BDD是布尔函数的图形表示形式，被广泛应用到网络可靠度的分析计算中。为了提升网络可靠度BDD分析算法的性能，本文根据边扩展图实例，识别两类无效边扩展路径：冗余节点型无效扩展路径和ST非连通型无效扩展路径，然后基于基本的网络可靠度BDD分析算法，实现了两类无效扩展路径的消除技术。实验结果表明，两种无效扩展路径消除技术能够提前识别无效扩展路径，避免无效扩展，有效减少中间子网的数量，缩减分析时间；通过把两种技术结合起来，可以有效地消除边扩展图中的这两类无效扩展路径，从而极大提升可靠度分析的性能。

关键词：二进制决策图 网络可靠度 边扩展路径 

单位：浙江师范大学数理与信息工程学院 浙江金华321004