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

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