论文题目: 关于图的因子与分数因子的若干结果
论文类型: 博士论文
论文专业: 运筹学与控制论
作者: 卞秋菊
导师: 刘桂真
关键词: 二分图,自由图,分数亏格对集,分数对集可扩,因子临界,韧度,孤立韧度
文献来源: 山东大学
发表年度: 2005
论文摘要: 二十世纪六十年代以来,图论已经成为发展最快的数学分支之一.应用图论来解决运筹学、化学、生物学、网络理论、信息论、控制论、博弈论和计算机科学等学科问题已显示出极大的优越性.图论在各个学科分支、工程技术领域及社会科学有着广泛的应用,它作为组合数学中的一个分支,受到了各方面的普遍重视. 因子理论是图论的一个重要分支,在图论研究中得到了极大关注.在日常生活中,许多诸如编码设计、积木设计,计算机网络的文件传输、进度表等关于运筹和网络设计问题都涉及到图的因子,因子分解和正交因子[2].其中,文件传输问题可以模拟为因子和(O,f)-因子分解(或f-染色),拉丁方块和空间方块的设计则涉及到图的因子和正交因子问题. 本文所考虑的图都是有限简单图.设G是一个图,V(G)是顶点集,E(G)是边集.对V(G)的子集S,G-S表示由V(G)S导出的子图,G[S]表示由S导出的子图.图G的点割是V(G)的子集S,使得G-S是不连通的.K-点割是有K个元素的点割.G的连通度k(G)是使得G有k-点割的最小的k.图G称为是k-连通的若k(G)≥k.图G的边割是E(G)的子集[S,V(G)S],其中S是V(G)的非空子集. k-边割是有k个元素的边割.G的边连通度λ(G)是使得G有k-边割的最小的k.G称为k-边连通的若λ(G)≥k. 令g和f是两个整值函数且对所有x∈V(G),0≤g(x)≤f(x).图G的(g,f)-因子F是G的支撑子图且对所有x∈V(G),满足g(x)≤d_F(x)≤f(x).若对任意x∈V(G),g(x)=f(x),则(g,f)-因子称为f-因子.对非负整数k和所有x∈V(G),若f(x)=k,则f-因子称为k-因子.特别的,若对任意x∈V(G),g(x)=f(x)=1,(g,f)-因子称为1-因子,即完美对集.图G的完美对集可参见[22].
论文目录:
Chinese Abstract
English Abstract
Symbols
Chapter 1 Introduction
1.1 Basic Definitions and Notations
1.2 Introduction on Factors of Graphs
1.3 Introduction on Fractional Factors of Graphs
Chapter 2 (g, f)-Factors in Bipartite Graphs
2.1 (g, f)-Factors in Bipartite (mg, mf)-Graphs
2.1.1 Preliminary and Results
2.1.2 Proof of Main Theorems
2.2 On Toughness and (g, f)-Factors in Bipartite Graphs
2.2.1 Preliminary and Results
2.2.2 Proof of Main Theorems
Chapter 3 Factors in K_(1,n)-Free Graphs
3.1 (g, f)-Factors in K_(1,n)-Free Graphs
3.2 On (f; m)-Uniform Graphs
3.2.1 Preliminary and Results
3.2.2 The Lemmas
3.2.3 Proof of Main Theorems
Chapter 4 On (g, f)-Factors and Fractional (g, f)-Factors
4.1 Neighborhood Conditions and (g, f)-Factors
4.2 On Binding number for Graphs to have (g, f)-Factors
4.3 Fractional Factors and Connected Induced Subgraphs
Chapter 5 On Fractional Matching Extension
5.1 Fractional Defect-d Matching
5.2 Fractional (n, k, d)-Graphs
5.3 Fractional Matching Extension in K_(1,n)-Free Graphs
Chapter 6 On n- Factor-Critical Graphs
6.1 On Fractional n-Factor-Critical Graphs
6.2 Fractional n-Factor-Criticality and Complete Closure
6.3 On Toughness and (a, b; n)-Critical Graphs
6.4 Fractional (a, b; n)-Critical Graphs and Isolated Toughness
References
Acknowledgement
Curriculum Vitae
学位论文评阅及答辩情况表
发布时间: 2005-10-17
参考文献
- [1].关于Hamilton-Waterloo问题的研究[D]. 雷洪川.上海交通大学2011
相关论文
- [1].图参数与图的因子[D]. 刘红霞.山东大学2010
- [2].图的因子和分数因子[D]. 常仁英.山东大学2010
- [3].图的控制数及其相关参数[D]. 单而芳.上海大学2005
- [4].图的点荫度和点线性荫度[D]. 左连翠.山东大学2005
- [5].不确定优化问题的若干模型与算法研究[D]. 戎晓霞.山东大学2005
- [6].拟阵与图[D]. 李乐学.山东大学2005
- [7].图的边覆盖染色及分数边染色[D]. 王纪辉.山东大学2006
- [8].图的因子和分数因子[D]. 蔡建生.山东大学2007
- [9].边染色图中的匹配、圈及图的圆染色[D]. 王光辉.山东大学2007
- [10].图的f-染色和均匀边染色[D]. 张霞.山东大学2007