设D是简单图G的一个无圈定向.若改变D中的一条弧的方向会产生有向圈,则称这条弧为D的相依边.用d（D）来表示D中相依边的条数,dmin（G）和dmax（G）分别表示G的所有无圈定向中相依边数的最小值和最大值.若对满足dmin（G）≤k≤dmax（G）的所有k,都存在G的无圈定向D使得d（D）=k,则称G是完全可定向的.图的完全可定向问题首先由Fisher, Fraughnaugh, Langley和West开始研究的.最近,台湾一些学者给出若干有趣的研究结果[8-10,12,13].本学位论文研究一些特殊图的完全可定向问题,如圈的平方、圈的立方、2-外平面图、无爪3-退化图等.本文共分5章.在第1章中,我们给出所用到的基本概念,简述了相关领域的研究现状并呈现了本文的主要研究结果.在第2章,我们证明了无爪3-退化图和不含K3（2）作为导出子图的2-外平面图是完全可定向的.在第3章,我们证明了：若dmax（G）≤6,则G是完全可定向的.在第4章,我们确定了dmin（Cn2）的值并证明了当n≥7时Cn2是完全可定向的.在第5章,我们确定了dmin（Cn3）的值并证明了当n≥9时Cn3是完全可定向的.
本文来源: https://www.lw50.cn/article/608d36b617120d5bd8a33e11.html