学位论文 > 优秀研究生学位论文题录展示

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

作　者: 廖原原
导　师: 谢政
学　校: 国防科学技术大学
专　业: 应用数学
关键词: 图有向图因子因子分解流多项式算法
分类号: O157.5
类　型: 硕士论文
年　份: 2005年
下　载: 38次
引　用: 0次
阅　读: 论文下载

内容摘要

图的因子理论是图论的重要分支之一,是图论研究中的最活跃的课题之一.特别是图的因子分解研究是一个引人注目的课题,它在网络设计和计算机科学中有着广泛的应用.目前,关于图的因子分解已有很多结论.本文主要基于图的因子分解的如下几个问题作了一些工作.　1.完全图的因子分解问题.本文研究了完全图的分支因子分解,分别给出了完全图K₂n的{K2, Sn-1}因子分解、2ùS n-1因子分解和当n=r′m为合数时的{K2r, Kr, （m-1）r}或{K2m, Km, （r-1）m}因子分解、A2r n或A2m n因子分解,以及完全图K_2n+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⁺）定向.

全文目录

摘要  6-7
Abstract  7-8
第一章绪论  8-16
  1.1 图论基本知识  8-12
  1.2 图的因子问题中的一些基本知识  12-14
  1.3 图因子分解的发展概述  14-16
第二章完全图的分支因子分解  16-24
  2.1 引言  16
  2.2 完全图新的分支因子分解  16-23
  2.3 小结  23-24
第三章图中具有推广的正交( g, f )因子分解的子图  24-30
  3.1 引言  24-25
  3.2 图中具有推广的正交(g, f )因子分解的子图  25-27
  3.3 算法  27-29
  3.4 小结  29-30
第四章有向图的因子  30-48
  4.1 基本概念和记号  30-31
  4.2 重要引理  31-33
  4.3 有向图中的最小出入度条件与某些特殊的因子的存在性  33-39
  4.4 网络流与有向图的因子及其算法  39-47
  4.5 小结  47-48
第五章图的定向  48-55
  5.1 基本概念和记号  48-49
  5.2 图具有(g~-, f~-; g~+, f~+)定向的充要条件  49-54
  5.3 小结  54-55
结论  55-56
致谢  56-57
参考文献  57-59
附录：硕士期间的主要工作  59

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

内容摘要

全文目录

相似论文