论文部分内容阅读
图的控制理论是图论研究的一个重要方向,在超图理论,编码理论,计算机科学,通信网络和监视系统等相关学科方向有着重要的理论意义和广泛的应用价值.它起源于De Jaenisch的皇后问题:在一个国际象棋棋盘上,最少放置几个皇后就可控制所有的方格?经过最近四十年来的发展,关于图的控制参数已经有许多的变形,现在的研究主要集中在确定各个参数界的确定以及彼此的相互关系和算法复杂性上.本文的研究对象是:符号边全控制和上负全控制.本文所做的工作主要包括以下四部分:
第一,我们分别给出了一般图和超立方体的符号边全控制数的下界和紧上界;
第二,我们给出了三正则图的符号边全控制数的紧下界,确定了n阶三正则图的最小符号边全控制数的精确值;
第三,我们确定了完全二部图符号边全控制数的精确值;
第四,我们研究了上负全控制函数:确定了偶正则图的上负全控制数的上界,并对达到其上界的极值图进行了刻画;因此,解决了由单而芳等提出的公开问题.