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

图的控制参数和一类极值问题

作　者: 焦艳
导　师: 于洪全
学　校: 大连理工大学
专　业: 计算数学
关键词: k-控制连通k-控制 2-控制数连通2-控制数单圈图 minimizer graph
分类号: O157.5
类　型: 硕士论文
年　份: 2004年
下　载: 87次
引　用: 3次
阅　读: 论文下载

内容摘要

图的某些参数，如图的控制参数，因为其在图论的研究以及现实世界的各种应用中固有的重要性，而得到广泛的研究和发展。图的控制集定义为图中的一个点的集合，使得图中其它任何一个点都与该点集中的某个点邻接。确定图的控制集问题在网络的目标、安全装置和便利设施等的定位的方面有很大用处。在过去的30多年里，对图的各种控制参数的研究已经成为图论研究的一个重要领域，迄今为止关于图的控制参数问题的研究已有上千篇文章，现在已有近百种类型的控制形式得到研究。本文主要工作包括以下几个方面： (1)简单介绍了几种常见的控制参数的概念和应用，以及它们的上下界和相互关系； (2)讨论了连通图G的连通k-控制数γ_k~c(G)的上下界，并证明了不等式 (3)给出在树和单圈图中，2-控制数和连通2-控制数相等的充分必要条件，并加以证明； (4)讨论了给定边数和顶点数的图的一类极值问题。对于所有给定边数和顶点数的图，我们将刻画出其所有顶点度数的α(0＜α＜1)次方的和为最小的一个图，这个图是由一个最大的完全子图和一个非孤立点，以及其它一些孤立点组成，并证明这个图是唯一满足条件的图。

全文目录

第一章绪论  6-11
  1.1 背景介绍  6-7
  1.2 图论的基本概念和术语  7-11
第二章图的控制参数和k-控制参数  11-26
  2.1 几种常见的控制参数  11-13
  2.2 四类k-控制形式  13-21
    2.2.1 k-控制  14-16
    2.2.2 k-独立控制  16-18
    2.2.3 k-无赘  18-20
    2.2.4 total k-控制  20-21
  2.3 四类k-控制参数的关系  21-23
  2.4 一些控制参数的Nordhaus-Gaddum类型的结果  23-26
第三章连通k-控制  26-32
  3.1 问题介绍  26-27
  3.2 图的连通k-控制集的上下界  27-32
第四章一类图的刻画问题  32-43
  4.1 问题介绍  32-33
  4.2 2-控制数等于连通2-控制数的树  33-34
  4.3 2-控制数等于连通2-控制数的单圈图  34-43
第五章关于图的一类极值问题  43-53
  5.1 问题介绍  43-44
  5.2 图的一类极值  44-53
参考文献  53-57
附录  57-58
致谢  58-60

图的控制参数和一类极值问题

内容摘要

全文目录

相似论文