德杰尼斯五后问题泛化研究

在德杰尼斯五后问题求解方法基础上,给出了2p×2p棋盘坐标表示,定义了方环和马步格,并利用皇后控制数或剩余控制数、皇后最佳(极佳)位置或剩余最佳(极佳)位置,以及棋盘对称性,得到了德杰尼斯五后问题泛化求解定理和便于求解的简化定理.     

奇数网格(或棋盘)德杰尼斯问题解法

在德杰尼斯五后问题泛化研究基础上,给出了(2p+1)×(2p+1)奇数网格坐标表示,定义了解首格集,利用皇后控制或剩余控制数、马步格、解首格集,以及图形对称性,得到了奇数网格(或棋盘)德杰尼斯问题求解定理和求解方法,并给出了3×3网格、5×5网格和7×7网格德杰尼斯问题的1个、3个和24个基础解及其图示.结果表明奇数网格(或棋盘)德杰尼斯问题是网格优化管控问题之一,具有一定的理论价值和应用价值.     

图的逆罗马控制数

介绍了图的逆罗马控制数的概念,证明了特殊图(路,圈,完全图等)的罗马控制数和逆罗马控制数;给出了任意n(n≥3)阶图G的逆罗马控制数的上下界,其界值为2≤γ1R(G)≤n-1.     

广义彼得森图意大利控制数

图的罗马控制来源于古罗马帝国的军事防御问题.图的意大利控制是一种泛化的罗马控制.确定图的意大利控制数是NP困难的.一般情况下,很难确定某一类图意大利控制数的精确值,只能给出其上界或下界.通过构造可递推的意大利控制函数,得到了广义彼得森图P(n,k)(k≥4)的意大利控制数紧的上界.结合前人给出的意大利控制数的下界,确定了当k≡2,3(mod 5)且n≡0(mod 5)时,P(n,k)(k≥4)意大利控制数的精确值.     

关于图的符号圈(点)控制

引入了图的符号圈(点)控制概念,给出了所有n阶极大平面图G(n≥3)的符号圈(点)控制数γsc(G)的一个下界,即γsc(G)≥(8n - 16 - n△)/△,并且此下界是最好可能的,获得了满足γsc(G)=∣V( G)∣ -2的所有连通图的一个特点.此外,还确定了几类特珠图的符号圈(点)控制数.     

图中控制数的有关结论

令G=(V,E)是一个图,点集S V,如果满足N[S]=V(G)(或N(S)=y(G)),则称点集S是一个控制集(或伞控制集).一个连通图G如果满足:对任何不相邻于一次点的v点,G-v的全控制数小于G的全控制数,则称图G是一个γt-临界图.给出连了通无爪3-正则图G的控制数满足γ(G)≤3-n.同时找到一个直径是2的4-γt-临界图.     

关于图的强符号控制数的下界

图G的强符号控制数γss(G)有着许多重要的应用背景,因此确定其下界有重要意义.本文在图的符号控制数基础上对图的强符号控制数进行了研究,指出了文献[3]定理5的小错误,改进了文献[4]定理4的下界,给出了图的强符号控制数的3个独立的下界,并给出了达到这3个下界的图.     

关于史坦因豪斯棋盘问题的一个证明

推广并证明了由著名波兰数学家史坦因豪斯提出的棋盘问题 :在国际象棋棋盘 (8× 8)的某些格子里埋着地雷 ,使得开始时 ,不管把皇后放在哪个格子里 ,皇后总不能从棋盘的左边走到棋盘的右边 ,在这种条件下 ,车 (castle)能沿着一些埋有地雷的方格从棋盘的上边走到棋盘的下边     

关于图的减边控制

引入了图的减边控制的概念,给出了一个图G的减边控制数γ′m(G)的两个下界,确定了完全图、圈和轮图的减边控制数,并提出了若干未解决的问题和猜想.     

基于对控制数与双控制数强相等的图

给出基于对控制数与双控制数强相等的图的一个性质,并依据该性质,刻画了基于对控制数与双控制数强相等的树及单圈图.     

关于蝶形网的(d,m)控制数研究

研究了蝶形网的(d,m)控制数问题.对于n维蝶形网B(n),证明了当d≥2n 2时,(d,2)控制数等于1;当2n-1≤d≤2n 1时,(d,2)控制数等于2.     

关于一类图的符号边控制数

设G为给定的图,且δ(G)≥1,用G ′表示图G的每个顶点v上增加d(v)-1个悬挂边所得到的图。徐保根给出了图G ′的符号边控制数。本文对上述结果做了详细证明,并给出四个例子。     

一类排列实现与皇后控制问题求解

在回溯实现从n个不同元素取m个与另n-m个相同元素的排列基础上,求解m个皇后控制n×n棋盘问题,推广了著名的高斯八皇后问题.     

八皇后问题所有解的模拟DNA算法

建立了求解八皇后问题所有解的数学模型.根据八皇后问题解的性质提出了7个相关的算子:主转置算子、行翻转算子、列翻转算子、倒置算子、顺旋算子、逆旋算子和倒转算子.给出了等价可行解的概念,并以这7个相关算子为工具研究了等价可行解的性质和八皇后问题解空间的性质.由此给出了求解八皇后问题所有解的模拟DNA算法,并用Mathematica软件进行了实现,并得到了所有的可行解,进而验证了算法的正确性和可行性.     

图的弱罗马控制

图的弱罗马控制数是图的弱罗马控制函数的最小权,记为γr(G).用逻辑推理和逐步分析法,刻画了弱罗马控制数等于最小控制数加1的图(即γr(G)=γ(G)+1)的特征.     

关于图的距离控制数的上界

对于任意的正整数l,连通图G的顶点子集D被称为距离l 控制集 ,是指对于任意顶点v D ,D中至少含有一个顶点u ,使得距离dG(u ,v) ≤l.图G距离l 控制数γl(G)是指G中所有距离l 控制集的基数的最小者 .确定图G的距离l 控制数γl(G)是NP 问题 .给出了当G是阶数为p (p ≥l 1 )的连通图时 ,对于任意的正整数l,都有最优上界γl(G)≤ p-Δ l - 1 l .而且针对某些Δ和l,是对Meir和Moon的结果的一种改进     

关于图的Fractional控制数

研究了图的 Fractional 控制问题,主要给出了关于联图的 Fractional 控制数的1个上界,由此确定了几类特殊联图的 Fractional 控制数,并推广了部分已知的结果。     

图的符号边全控制数

用γ′_st(G)表示图G的符号边全控制数,给出了一般图的符号边全控制数的下界 ,最后确定完全图的符号边全控制数.     

路与圈的笛卡尔乘积的全控制数

令图G是无孤立点的无向图.V(G)是图G的顶点集,D是V(G)的真子集.如果图G的每一个顶点至少与集合D中一点相邻,则集合D是图G的全控制集.G中最小全控制集的顶点数称为G的全控制数,记为γt(G).参考已有全控制数的知识及笛卡尔乘积Cm□Cn、Pm□Pn的全控制数的相关结论,利用γt(Cm□Cn)≤γt(Pm□Cn)≤γt(Pm□Pn)这一不等式给出了Cm□Pn(m=3,4)、Pm□Cn(n=2,4)的全控制数.     

Wenger图的控制数

Wenger图H_m(q)是定义在有限域F_q上的q-正则二部图.根据二部图G=(X∪Y,E)的控制数为Y在X中的控制数与X在Y中的控制数之和,采用矩阵运算的方法在H_m(q)中通过构造含点数最少的控制集,说明了这两个控制数应该相等,从而确定了Wenger图的控制数.