双圈图的优美性

针对双圈图, 设计一种图的优美性判定算法, 并对17个点内的所有双圈图进行优美性验证, 得到了该范围内所有的优美图和非优美图. 结果表明, 在17个顶点范围内, 除∞ 型双圈图C_(m,n)外, 其余所有双圈图都是优美的, 其中(m+n)(mod 4)={1,2}. 最后给出该类图的非优美证明, 并进一步猜测当顶点数大于17时, 该结论仍成立.     

图(n≤9)的优美性

设计了一种递归回溯算法,采用了剪枝函数与预判函数相结合的算法优化策略,实现了对有限点内任意图的优美性验证。利用该算法,对9个点内的所有简单连通图进行了优美性验证,得到该范围内所有优美图和非优美图的数量。结果表明,在该范围内绝大多数的图是优美的。并且根据实验数据,文中还得出以下结果:Kn-m(由完全图减去m条边所得的图)是非优美图的确定下界;当p、q满足一定条件时,这类(p,q)图(p为顶点数,q为边数)中的所有图全部是优美的;当q(mod 4)={0,3},且q≤[3.7p-9.3]时,(p,q)图中几乎所有的图都是优美的。且进一步猜测,当p9时,相关结论成立。