论文部分内容阅读
图的符号控制是图论的一个重要的研究方向，不仅仅在实际生活中有着非常广泛的应用，例如，发射基站的选址、计算机通讯网络和群决策等，而且人们也可以在计算的复杂性和算法设计、优化理论、通讯网络设计与分析等方面应用图的控制理论。我们研究图的符号控制尤其是一些特殊图的符号控制问题可以为解决一般的NP-困难问题提供重要的借鉴，具有较为重要的意义，图的控制数的研究也因此一直受到广大学者的关注。 本文主要研究路径图Pm与圈图Cn的交图的全符号控制数。本文考虑的图G均为有限简单连通图，根据Pm□Cn的点和边邻域的特点（在全符号控制研究中，顶点的邻域中包含边，边的邻域中也包含顶点），给出图Pm□Cn的全符号控制数较好的上下界。 首先，根据前人的重要结论，对于任意图G，如果图G顶点的最小度为δ(G)，最大度为△(G)，顶点数为|V(G)|，边数为|E(G)|，那么G的全符号控制数为:γ*s(G)≥([)δ(G)-△(G)+1/δ(G)+△(G)+1(|E(G)|+|V(G)|)(])ρ(|E(G)|+|V(G)|), 并且这个下界是可达的，其中ρ(s)表示s的奇偶性，即如果s是奇数时，则ρ(s)=奇数，如果s是偶数时，则ρ(s)=偶数。 对于Pm□Cn，根据上式可以得到γ*s（Pm□Cn）≥0，由于Pm□Cn的点和边邻域的特性，我们可知其全符号控制数γ*s（Pm□Cm）的下界可以比零更大一些。利用解析法证明Pm□Cn的全符号控制数γ*s（Pm□Cn）的下界，该下界比一般图G的全符号控制数γ*s(G)的下界大。 然后，利用计算机构造证明给出图Pm□Cn的全符号控制数较好的上界。基于Pm□Cn点和边邻域的特点，设计有效的分支限界条件，研制计算机算法，构造全符号控制函数，计算γ*s（Pm□Cn）的上界。 最终，我们给出图Pm□Cn的全符号控制数。