论文部分内容阅读
作为图论中的一个重要分支,图的标号问题研究历史久远.其中,图的染色问题就是一种特殊的图的标号问题,它不仅在图论中有着重要的理论价值,而且和许多实际问题有着密切的联系,例如化学制品的存放问题,通讯系统的频道分配问题,高校排课系统的排课冲突问题等.图的标号问题本质是图的点集或边集到其他集合的映射（这里我们考虑整数集合）,无向图的反魔幻标号就是一种典型的图的标号问题,是图的边集到一个整数集合的特殊双射.近年来,关于无向图是否存在反魔幻标号是一个普遍关注的问题.1990年,Hartsfield和Ringel提出了无向图反魔幻标号的概念并给出了除K2之外的每个连通图都是反魔幻的猜想.随着对无向图反魔幻标号研究的不断深入,2010年,Hefetz,M¨utze和Schwartz给出了有向图的反魔幻标号的概念（见第5页）,他们认为关于有向图的反魔幻标号问题的研究,需要考虑每一个图的反魔幻定向的存在性,并提出如下猜想:每个连通图都存在一个反魔幻定向（反魔幻标号和反魔幻定向的定义见1.2节）.本文围绕这个猜想展开研究,对几个图类论证这个猜想的正确性.我们利用图类的特点和内部结构性质,借助于图顶点集的划分,结合数学归纳法及图的算法理论,分别论证了不连通偶正则图和四类连通图的反魔幻定向的存在性问题.论文结构如下:第一章是绪论,主要介绍了本文的相关背景知识,给出了本文用到的基本概念和记号,综述了本文的主要工作和结论.第二章给出了完全k叉树的相关性质及结构特点,并根据k的奇偶性,分别对k=2t和k=2t+1（t≥1）证明了完全k叉树存在反魔幻定向的结论,因此证明了每个连通图都存在反魔幻定向的猜想对完全k叉树是成立的.第三章考虑了完全二叉树的三种变异图类的反魔幻定向,分别解决了广义同胎树,超树和X-树的反魔幻定向的存在性问题,扩大了猜想成立的图类.第四章改进了已有的关于不连通2d-正则图最多包含两个奇分支时存在反魔幻定向的结论,得到了2d-正则图G包含k（k≥3）个奇分支时存在反魔幻定向的一个充分条件,并证明了两个结果:（1）当3≤k≤5d+4时,图G一定存在反魔幻定向;（2）当k≥5d+5时,如果每个奇分支的顶点数量均至少为2·(（?）k-（5d+4）/（2d-2）（?）+5,那么图G一定存在反魔幻定向.第五章对本文进行了总结,并给出了进一步的研究方向.