摘要: 在许多实际问题中,需要判断给定线图是否为平面图。目前已有很多种判定可平面图的算法,路径嵌入法是一种公认的比较好的算法。本文在前人工作的基础上,分析了该算法的检验过程,用归纳法给出一种算法的完备性证明。以省机时、省内存,输入、输出简单、直观为目标,采用对边序列矢量进行直接加工的方法编制了路径嵌入法判定可平面图的源程序。最后给出了一些例题和它们的计算情况。