近20年来,为了解决结构日益复杂的VLSI电路的测试问题,可测试性设计技术得到了迅速发展.在可测试性设计中,如何针对不同的对象及测试需求进行优化设计,以尽可能降低总体设计代价,是一个非常重要且亟待解决的问题.文章应用图论对可测试性设计中的两种典型优化问题进行了数学描述,并构造了相应的可行求解算法. In the recent 20 years, to solve the increasingly complex structure of the VLSI circuit test problems, testability design techniques have been rapidly developed in the design of testability, how to optimize the design for different objects and test requirements to minimize the overall Design cost is a very important and urgent problem to be solved.This paper describes the two typical optimization problems in testability design by using graph theory and constructs the corresponding feasible solution algorithm.