基于图因子分解的几个问题

论文摘要

图的因子理论是图论的重要分支之一,是图论研究中的最活跃的课题之一.特别是图的因子分解研究是一个引人注目的课题,它在网络设计和计算机科学中有着广泛的应用.目前,关于图的因子分解已有很多结论.本文主要基于图的因子分解的如下几个问题作了一些工作.　1.完全图的因子分解问题.本文研究了完全图的分支因子分解,分别给出了完全图K2n的{K2, Sn-1}因子分解、2ùS n-1因子分解和当n=r′m为合数时的{K2r, Kr, （m-1）r}或{K2m, Km, （r-1）m}因子分解、A2r n或A2m n因子分解,以及完全图K2n+1的H2n+1因子分解和当n=r′m为合数时的B2 r n+1或B2 m n+1因子分解.　2.　图中具有推广的正交（g, f ）因子分解—r正交（g, f ）因子分解的子图问题.本文在已有结论的基础上作了进一步研究并改进了结果,证明了每个（mg+kr, mf-kr）图G含有一个子图R,使得R有一个（g, f ）因子分解r正交于G的任意给定的有kr条边的子图,其中m,k和r是正整数且k < m,g≥r-1.本文还介绍了寻找（mg+kr, mf- kr）图中具有r正交（g, f ）因子分解的子图的多项式算法.3.有向图的因子问题.一方面,本文考虑了允许每个顶点上至多关联一条环但不含有重弧的有向图,讨论了此类有向图的最小出入度条件与[a, b]因子、带[a, b]界的（ f-; f+）因子以及k因子的存在性问题,并且举例说明在一定条件下所得结果是最好的;另一方面,本文运用网络流知识讨论了有向图含有（g-, f-; g+, f+）因子、（ f-; f+）因子的充要条件,并且给出了求有向图中的（g-, f-; g+, f+）因子、（ f-; f+）因子的多项式算法.4.无向图的定向问题.本文运用网络流方法研究了图的定向问题,给出了图有（g-, f-; g+, f+）定向（定向图）、（ f-; f+）定向（定向图）的充要条件,并且给出复杂性为O（n2m）的多项式算法求出图的（g-, f-; g+, f+）定向的,或者判断出该图无（g-, f-; g+, f+）定向.

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 图论基本知识
• 1.2 图的因子问题中的一些基本知识
• 1.3 图因子分解的发展概述
• 第二章 完全图的分支因子分解
• 2.1 引言
• 2.2 完全图新的分支因子分解
• 2.3 小结
• 第三章 图中具有推广的正交（ g, f ）因子分解的子图
• 3.1 引言
• 3.2 图中具有推广的正交（g, f ）因子分解的子图
• 3.3 算法
• 3.4 小结
• 第四章 有向图的因子
• 4.1 基本概念和记号
• 4.2 重要引理
• 4.3 有向图中的最小出入度条件与某些特殊的因子的存在性
• 4.4 网络流与有向图的因子及其算法
• 4.5 小结
• 第五章 图的定向
• 5.1 基本概念和记号
• -, f^-; g⁺, f⁺）定向的充要条件'>5.2 图具有（g^-, f^-; g⁺, f⁺）定向的充要条件
• 5.3 小结
• 结论
• 致谢
• 参考文献
• 附录：硕士期间的主要工作