关于图的非对称距离k的博弈控制数界的研究

来源 :福州大学 | 被引量 : 0次 | 上传用户:zhouqin1983
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
生活中许多实际问题都可以转化为图的相关问题.近年来,图论已经广泛应用于运筹学,网络理论,信息论,控制论,博弈论以及计算机科学等领域.图的控制理论是图论研究的一个重要课题.它在通信网络,编码理论,监视系统等方面都有广泛的应用.本文主要研究图的非对称距离κ的博弈控制数的界.点集D称为图的κ-控制集如果图中每一个点与D的距离至多是κ.点集A称为图的出独立集如果A中任意两个点的距离大于d.假设两个博弈选手Dominator和Staller在一个图上进行非对称距离κ的控制游戏,即(a,6)-κ-控制游戏.在游戏开始时图中的点都没有被控制Dominator先选a个点,然后Staller选择b个点,依次循环.每一个被选择的点和与它距离至多是κ的点都会被控制.不管谁从图中选点必须保证至少有一个未被控制的点被控制.当由二者选择的点构成图的一个κ-控制集时,游戏结束Dominator的目标是最小化最终得到的κ-控制集的基数,而Staller的目标是最大化最终得到的κ-控制集的基数.当两个游戏者都达到最优时,得到的κ-控制集的基数就是非对称的距离κ的博弈控制数.本文主要就(α,1)-κ-博弈控制数的界展开研究.第一章介绍了图论中一些基本概念和定义,图的博弈控制论,弱博弈染色理论的相关背景和目前已有的成果.第二章结合(α,1)-κ-控制游戏和(a,1)-κ-弱染色游戏对确定(a,1)-κ-博弈控制数的上界展开研究.在子图上进行(a,1)-κ-弱染色游戏中的两个选手称为Alice和Bob.在选点的过程中保证两个游戏都满足各自的游戏规则.对于(a,1)-κ-控制游戏而口,Dominator复制Alice在(a,1)-κ-弱染色游戏中选择的点作为自己的移动点,接下来Staller进行选点.对于(a,1)-κ-弱染色游戏而言,Alice按照自己的策略选点,Bob复制Staller在(a,1)-κ-控制游戏中选择的点作为自己的移动点.当(a,1)-κ-弱染色游戏结束后,Dominator和Staller轮流在图上进行的(a,1)-κ-控制游戏中选点.两个游戏都结束时,由Dominator和Staller选择的点即构成κ-控制集,并选择满足一定条件的点构成m-独立集(1≤m≤2κ+1).最终利用m-独立集的基数与(a,1)-κ-弱博弈染色数确定(a,1)-κ-博弈控制数的上界.此外,本章还研究了当Alice在(a,1)-κ-弱染色游戏运用激活策略和协调策略时所对应的(a,1)-κ-弱博弈染色数,由此可以得到(a,1)-κ-博弈控制数的更好的上界.同时,对平面图,弦图,克-树等一些特殊图类也做了类似的研究.第三章建立了图的最小κ-控制集的基数与(a,1)-κ-博弈控制数之间的联系.利用κ-控制集的基数确定了(a,1)-κ-博弈控制数的上下界,并且通过构造图形证明了(a,1)-κ-博弈控制数的可行值都可以实现.第四章对本文得出的主要结论进行了总结.
其他文献
本文考虑到概周期环境和时滞作用对种群动力学系统的影响,分别建立了具有反馈控制的差分时滞概周期竞争系统和具有脉冲作用的微分时滞概周期竞争系统,运用有关预备引理、定理
量子信息学是目前科学研究领域的一门前沿性新兴学科,它将量子力学和信息科学相结合,无论在理论上还是在实验上都有了很大的突破。作为一种重要的资源,研究如何制备纠缠态,对
非局部扩散竞争模型在生物学或生态学上有着广泛的应用.人们通常对两个竞争种群的共存或灭绝现象很感兴趣.数学上而言,我们通过分析竞争模型静态解的全局渐近稳定性来解决这
本文利用微分分次范畴的技术来构造奇点范畴的粘合.首先,我们回顾微分分次范畴的基本概念,并且给出一些基本性质.其次.我们简单介绍三角范畴粘合的概念,将它们与t-结构以及TT
分数阶Laplacian能通过延拓法得到Luis Caffarelli-Luis Silvestre利用平面上的调和延拓,将分数阶Laplacian刻化为带有Dirichlet边界条件映射到带有Neumann条件的算子.通过这
山岭隧道是隧道工程中的常见隧道形式,由于地质构造较复杂,存在危岩落石、断层破碎带等不良地质地质构造的影响,在修建过程中遇到了一系列的问题。本文以修筑在山体中的双线铁路隧道为例,该隧道设计全长3596m,通过地层岩性主要为石英砂岩、局部夹粉砂岩和变质砂岩夹粉砂岩,围岩破碎,隧道施工难度大,施工风险高。隧道选址区发育一条平移断层,一条褶皱带,断层带岩体破碎,洞顶易坍塌;隧道洞身侧壁DK99+590~D
在统计学的研究过程中,损失函数作为一种度量,在统计学和经济学等多个领域都有广泛的应用.统计学家们比较熟知且应用最多的是平方损失函数,而近些年来提出的平衡损失函数为判
本文对大兴安岭东南部吉林洮南万宝盆地下侏罗统红旗组非含煤地层中发现的苏铁类植物假篦羽叶进行形态学和分类学研究。确认所采集的假篦羽叶与模式种伊什假篦羽叶最接近,但
设G=(V,E)是一个至少有三个点的无向简单连通图,称作非平凡图.其中V和E分别表示图的点集和边集.映射f:E→{1,2,...,k},令c(u)=Πv∈N(u)f(uv),u∈V若对任意uv∈E,都有c(u)≠c(
本论文涉及两类Sierpinski地毯的Hausdorff测度的计算问题。我们以单位正方Q=[0,1]2作为种子集,分别用两族迭代函数系统生成两类自相似集合并试图确定它们的Hausdorff测度。