论文部分内容阅读
生活中许多实际问题都可以转化为图的相关问题.近年来,图论已经广泛应用于运筹学,网络理论,信息论,控制论,博弈论以及计算机科学等领域.图的控制理论是图论研究的一个重要课题.它在通信网络,编码理论,监视系统等方面都有广泛的应用.本文主要研究图的非对称距离κ的博弈控制数的界.点集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)-κ-博弈控制数的可行值都可以实现.第四章对本文得出的主要结论进行了总结.