组合线路多故障最小测试集

本文提出了一个新的求多故障最小测试集的算法。其中包括任意组合线路的分树及扇出点的分级,这样大大减少了求星展式的工作量,本文中的算法对冗余和非冗余线路不必区分,可统一处理。本文得到的结果较文献〔4〕,〔5〕,〔7〕,〔10〕等为优。     

哈米尔顿图及其最佳解

本文通过对邻接矩阵的研究得到了判断哈米尔顿图的一种条件,并由此提出求哈米尔顿图的所有哈米尔顿回路及最佳哈米尔顿回路的算法。     

组合线路中的桥接故障及二极管短路故障

组合线路中的桥接故障及二极管短路故障均可分成两种类型:组合型和反馈型。根据可测试性,反馈型故障本身又可划分成三类:组合可测,时序可测,振荡可测。所有上述故障可测的充要条件都得到证明。并提出了组合型故障的完整测试集公式及反馈型的组合,时序,振荡可测等故障的完整测试集公式。本文比文献〔1〕,〔2〕,〔3〕,〔4〕更具有普遍性,所以本文结论能包含上述文献的大多数结论。因线或桥接及二级管短路故障和线与桥接及二极管短路故障的结论完全相似,所以本文只给出了线与故障的结论。     

有向欧拉图和时序机最小功能测试序列

本文提出了一种判别有向图是否欧拉图的充分必要条件,并给出了在有问欧拉图中找一条欧拉巡回的新的算法。除此还给出了在非有向欧拉图中找一条最短欧拉道路的算法。利用上述结果可以得到时序机的最小功能测试序列。因而使时序机最小功能测试问题得到解决(参考文献〔2〕p76),并证明对于给定时序机的状态图而言算法是多项式复杂性的。