图的控制博弈

发布时间：2020-05-20 06:40

【摘要】：本文所涉及的图都是简单的无向连通图.对任意的点v∈V(G),G|v表示图G的一个部分控制图,即G中顶点v已经被控制.设图G的控制数与博弈控制数分别是γ(G)与γ_g(G).若图G满足公式 γ_g(G)= 2γ(G)-1,则这类图是γ_g-极大图.若对任意的点v∈ V(G)有γ_g(G)=γ(G|v),则图G是控制博弈稳定的(简称γ_g-稳定的);若对任意的边e∈E(G)有γ_g(G-eγ_g(G),则图G是控制博弈边-临界的(简称γ_g-边-临界的).若G是博弈控制数为k的γ_g-稳定图(或γ_g-边-临界图),则G是k-γ_g-稳定图(或k-γ_g-边-临界图).本文的第一章简单介绍了文章所涉及的图的一些基本概念、符号、相关研究背景以及所需要的相关定义.第二章首先在具有支撑控制集的图中,给出一大类γ_g极大图.然后在似星树,即有且只有一个点的度数大于等于3的树中,刻画了所有γ_g-极大图.第三章首先刻画了当k∈｛1,2｝时的k-γ_g-稳定图,3-γ_g-稳定树,并证明Kneser图K(n,2)是k-γ_g-稳定的,其中n = 5时k= 5;n≥6时k = 3,并确定了所有γ_g-稳定的路与圈.其次证明了对任意的正整数k,存在一个k γ_g-稳定图.文章最后描述k∈{1,2 时的所有k-γ_g-边-临界图以及一个3-γ_g-边-临界图的例子,并给出两个判断非-γ_g-边-临界图的充分条件.第四章对本论文进行了系统性的总结,并列举了一些论文中未能解决的问题.
【图文】：

地图,尼斯

线段来表示这些事物之间所具有的特定关系.众所周知，图论起源于非常经典的柯尼斯堡七桥问题：在柯尼斯堡的普莱格尔河上有七座桥将河中的岛与河连接起来，问能否从四块陆地中的任何一块开始，通过每一座桥正好一次，最后回到起点？1736 年瑞士数学家欧拉最先用图论的思想解决了这个问题，由此图论便与几何拓扑学一起诞生了，而欧拉也因此被称为是图论的创始人.到目前为止，，图论已经给世人呈现出大量有趣的问题，其中的一个焦点性问题就是图的染色问题.它起源于著名的“四色猜想”，即用四种颜色就可以对任意一张地图进行染色.1879 年 Kempe 第一个给出这个猜想的证明，但是后来被证实他的证明方法有误，直到 1976 年美国数学家 Appel与 Haken 在计算机的帮助下证明了四色猜想是正确的，后来这个猜想被改成了著名的“四色定理”.此外天文学家哈密顿提出了一个非常有趣的问题——哈密顿回路问题，即在一个有多个城市的地图网络中，寻找一条从给定起点到给定终点且沿途恰好经过所有其它城市各一次的路.这个问题便形成了大家现在熟知的哈密顿圈 1 .1936年匈牙利的数学家哥尼格发表了《有限图与无限图的理论》，这是第一本关于图论的著作，也是图论成为一门独立学科的标志.图 1.1 为柯尼斯堡七桥问题的简化图及其在图论中反映的图形.

图的控制博弈

g-临界树
【学位授予单位】：南京航空航天大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5;O225

【相似文献】