优雅图猜想

对于图G(p,q),如果存在一个单射f:V(G)→[0,1,2,…,q],使得f(E(G))={f(uv)=(f(u)+f(v))mod(q+1)|uv∈E(G)}=[1,…,q],则称图G为优雅图.采用剪枝与预判函数相结合的方式,设计了递归回溯算法,对9个点内的所有简单连通图进行了优雅性验证,得到9个点内所有优雅图和非优雅图.根据实验结果,验证了当3≤p≤9时,所有的树图、单圈图几乎都是优雅的,证明了当3≤q≤9且q≠1(mod 4)时,图G(p,q)是优雅的.最后给出猜想:绝大多数的图是优雅的.

双圈图优雅性猜想

采用剪枝与预判函数相结合的方式,设计了递归回溯算法,对16个点内的所有双圈图进行优雅性验证,得到16个点内所有优雅图和非优雅图。根据实验结果,当4≤p≤16且p+1=1(mod 4)时,双圈图C_((m,n))是非优雅图,非优雅图的个数为■,除此之外的所有双圈图都是优雅图。最后给出猜想:双圈图几乎都是优雅图。