论文部分内容阅读
对于图G=(V,E),子集S包含于V,称点集S为图G的控制集,若对于任意的y∈V-S,都存在x∈S,使xy∈E(G)。 由于控制理论的研究越来越引起人们的重视,人们对控制数有了更深的了解,提出了不同的控制数。例如:符号控制数,符号边控制数,符号全控制数等。这些控制数在图的结构中起了重要的作用。 本论文主要讨论了图的几类控制数的下界。在[3]中,鲁进步,刘林中给出了全符号控制函数的定义,并给出了一些特殊图的全符号控制数的上界。本文继续研究图的全符号控制数,并且得到一些特殊图的全符号控制数的下界,接着又给出了一般图的全符号控制数的下界。 本文还给出了图的负边控制的定义:设为一个图,一个函数f:E→{-1, 0,1}被称为图G的一个负边控制函数,如果G f[e]=f(N[e])=∑x∈N[e]f(x)≥1对所有的边e∈E成立。图的负边控制数定义为:γ-e(G)=min{f(E)|f为图G的负边控制函数}。并讨论了图的负边控制数的下界,还刻画了γ-e(G)=|E(G)|的图。 最后本文研究了路的符号边控制数的界,即给出了m+4/3≤γse(Pn)≤m+8/3。