点可迁图的全约束数和有效全控制

摘要

本篇论文，主要考虑的是非空简单图.通常所说的图即包含有向图也包含无向图，在图论中没有明确的规定图的符号.一般地，用G=(V,E)来表示图，其中V=V(G)表示图G的顶点集以及E=E(G)表示图G的边集.顶点对（u，v）表示的是从顶点u指向顶点v的一条有向边，注意当(u，v)，（v，u）∈E时，则可把这两条有向边当成一条无向边，用uv表示.设图G是有向图，如果G的每条边（u，v）都有(v，u)∈E则图G就称为无向图.
　　设D为图G的顶点子集，如果对于任意一个不在D当中的顶点v都有u∈D使得(u，v)∈E，则称D为图G的控制集.图G的控制数是指最小控制集所含顶点的个数，通常用γ(G)来表示.设S为每个顶点入度大于零的图G的顶点子集，如果对于每一个顶点v∈V(G)都有u∈D使得(u，v)∈E，则称S为图G的全控制集.图G的全控制数是指在最小全控制集所含有顶点数，通常用γt(G)来表示.图G的约束数是指删除G中最少边集的数目使得图G的控制数增加，用b(G)表示.图G的全约束数是指删除G中最少边集的数目使得图G的全控制数增加，用bt(G)表示.
　　在这篇论文中，建立了点可迁图的全约束数的一个紧的下界（通常下界比上界难很多），通过研究全约束数和有效全控制数之间的关系，也得到了正则图全约束数的一个上界.如果图有有效全控制集，在无向图情形下给出了紧的上下界，在有向图情况下，完全确定了全约束数的精确值.作为应用推广，也研究了一些循环图、哈拉里图、网格网络的运算，通过它们有效控制集存在的特征，研究得到它们的全约束数.另外对于一些特殊的图，例如超级立方体也得到了它的全约束数的上下界.实际应用中的图模型大都是点可迁图，论文取得的成果，加深了点可迁图在控制理论上的认识，在实际网络中的结果为人们在现实中应用这些网络提供了全控制容错性的参考.

目录

声明

摘要

第一章 绪论

§1．1 图论的由来和发展过程

§1．2 关于图论的基本概念

§1．3 控制数和约束数的概念

第二章 全约束数和有效全控制

§2．1 引言

§2．2 初步的结果

§2．3 主要的结果

第三章 循环图的全约束数和有效全控制集

§3．1 双环网络图的有效全控制集和全约束数的上下界

§3．2 Harary图的全约束数和有效全控制集

§3．3 其它的应用

第四章 总结与展望

§4．1 总结

§4．2 展望

参考文献

攻读硕士学位期间科研情况及学术活动

致谢