论文部分内容阅读
自欧拉发表第一篇图论论文以来,图的理论逐渐建立并完善和丰富起来.其中,图的控制理论在图论中占据着举足轻重的地位.许多实际问题可以用图进行建模,将其转化为计算图的控制数问题来解决.除此之外,图的控制理论对运筹学、网络理论、社会科学等学科的发展有着深远的影响.因此,近年来,关于图的控制数理论的研究成果层出不穷.由于确定任意图的控制数问题是一个NP-完全问题,于是,确定控制数的尽可能好的上界和下界就具有非常重要的意义,进而可以继续研究达到上下界时极值图的结构问题. 本文主要讨论了给定控制数的连通二部图极图的结构,以及倍图的全符号点控制数达到上界时图的结构问题. 第一章介绍了图论这门分支的历史背景和图的控制数的发展进程;第二章介绍了图的基本概念和符号表示,为后两章做准备工作;第三章研究了给定控制数的连通二部图极图的结构问题,刻画了当控制数大于等于3时边数达到极值时的连通二部图所满足的特性;第四章研究了倍图的全符号点控制问题,利用图的全符号点控制数的性质,刻画了倍图的全符号点控制数达到上界时的极图,并且确定了圈和路的倍图的全符号点控制数.