图的交叉数、应用及算法研究

图的交叉数在ＣＡＤ中有广泛的应用，如草图的识别与重画、电路板的设计等。它是ＮＰ困难总是，研究它对解决一般ＮＰ困难问题很有意义。本课题更要研制好的图的交叉数算法，并以此研究图的平均交叉数、具有最大交叉数的图的特征等对于实际应用有重要意义的问题。