《树图的成对控制数研究》由会员分享，可在线阅读，更多相关《树图的成对控制数研究（32页珍藏版）》请在金锄头文库上搜索。
1、中国科学技术大学硕士学位论文树图的成对控制数研究姓名：莫琼祁申请学位级别：硕士专业：应用数学指导教师：侯新民20080401摘要本文一共四章。第一章介绍一些图论的基本概念和控制参数的预备知识。然后，我们在第二章给出了关于树图的成对控制数的研究，在第三章中对给出了成对控制边临界图的一些研究工作。最后，我们总结本文的主要结果，并提出几个有待继续研究的问题。如果s是一个控制集且它的导出子图(s)包含至少一个完全匹配，则s是成对控制集。成对控制集的最小势就是成对控制数。记协(G)为图G的成对控制数。在第二章，我们证明了，对于树图丁的成对控制数有一个紧的上界1碲口)2s+f(礼一sz一1)21，并且给出
2、了达到这个上界的一类树族。不含孤立点的图G，如果它的任意两个不相邻顶点u，u，有协(G+uu)，6(G)=mindG(z)Izy(G)无向图G称为七正则的(七regular)，如果对每个zy(G)均有dG(z)=七。设图D是有向图，!，y(D)的顶点出度(verteX-ou扛degree)定义为D中以掣为起点的有向边的数目，记为d去(可)；3y(JD)的顶点入度(vertex-indegree)定义为D中以可为终点的有向边的数目，记为呖(y)。图D(或G)中连接顶点z和y且长度(1ength)为七的链(chain或硼此)，记为z可链，是指顶点毛和边q交错出现的序列=zto(=z)口nznnt2
3、口“z“(=y)，其中与边。略都相邻的两顶点z幻一。和正好是D巧的两个端点(可能有一，=z白)。z和!，称为的端点(endvertices)，其余顶点称为内部点(internalvertices)。中边的数目七称为w的长度。边互不相同的链称为迹(trail)。内部点互不相同的迹称为路(path)。两端点相同的链(迹、路)称为闭(closed)链(迹、路)。闭(有向)路又称为(有向)圈(cyck)。设G=(G)，E(G)，妒G)和日=(y(日)，E)，妒日)是两个图，若y旧)y(G)，E(日)E(G)，并且妒H是妒G在E(日)上的限制，即妒H=妒GlF()，则称日为G的14图的控制参数介绍5任何
4、两顶点之间无边相连并且y中任何两顶点之间也无边相连，则称该图为2部分图(bipartitegraph)，(x，y)称为2部划分(bipartition)。简单2部分无向图uE)称为完全2部分图(completebipartitegr印h)，如果x中的每个顶点与y中的每个顶点均有边相连。14图的控制参数介绍定义141设图G=E)，s是y的子集，如果G陋】=y，则s是图G的控制集(dominatingset)。如果s是图G的顶点数最少的控制集，则称吲为图G的控制数，记为，y(G)。也称s为图G的最小控制集。图12：简单二叉树的控制集在树中，一度点被称作是叶点，而它的邻点称作是支撑点。如果某个支撑点
5、与两个或两个以上的叶点相邻，则被称作是强支撑点。考虑图12中的简单二叉。我们把图B中的2个黑色顶点组成的集合记为s，注意日中剩下的顶点都和s中的某个顶点相连。因此，7(B)2。又因为每个叶点和它的支撑点至少有一个属于S，因而有7(B)2。所以，我们得到7)=2。考虑图13。集合s=e，6构成图c的控制集，又因为不存在一个与其他顶点都相连的顶点，所以，y(c)=2。再看图14中的树T。因为5个黑色顶点控制树r，并且树z的控制数必定大于等于它的支撑点的个数，所以有1口)=5。对于控制集s，yS中的每个顶点都与S中的某个顶点相连。进一步，我们要求y中的每个顶点都与s中的某个顶点相连，于是得到了全控制
6、的概念。下面14图的控制参数介绍7图15：简单二叉树的全控制集H：d图1，6图C的全控铋集6C互不相连，使得s不是c的全控制集。c的全控制集s7=p，c)如图16所示。注意，c的控制数等于全控制数。最后考虑图14中的树T，T中所有支撑点构成一个控制集。但是，由于这些支撑点互不相连，所以它并不是T的全控制集。T的全控制集如图17所示，由8个黑色顶点构成，且讥)=8。对于全控制集s，我们可进一步要求s中的顶点两两成对，由此得到成对控制集。下面给出成对控制集和成对控制数的定义。定义143设图G=(KE)不含孤立点，s是y的子集，如果G)=y，且G旧至少包含一个完备匹配，则s是图G的成对控制集(paj
7、reddominatingset)。如果s是图G的顶点数最少的成对控制集，则称吲为图G的成对控制数，记为协(G)。每个成对控制集同时也是全控制集，所以对不含孤立点的图G，有饥(G)协(G)。我们再看图15中的简单二叉树。黑色顶点构成B的全控制集s7，但是这3个顶点不能构成一个完全匹配。由此得到B的成对控制集s玎如图18所示。s由14图的控制参数介绍9图1，9：树T的成对控制集立点的图G=(VE)对应一个互连网络。为这个网络安装警卫系统，子集scy中的每个顶点t，对应一个警卫的位置，它的作用是保护GM中的每个顶点。那么控制集s(domillating驼t)，是要求ys中每个顶点都得到保护，即G(
8、s)2矿s。全控制集s(totaldo衄natingSet)，进一步要求每个警卫也能得到相邻警卫的保护，即G(S)=y。成对控制集S(paLireddominatingset)，是在全控制的基础上，要求所有警卫每两个相邻的一组，互相提供保护。满足如上要求的子集s分别被称为控制集、全控制集和成对控制集。我们希望投入警卫的数量最少，于是就有了控制数、全控制数和成对控制数的概念。14中国科学技术大学硕士学位论文(mod4)。所以d(tk，tk，)三o(mod4)，因此d(u，u。)=d(u，t，叫)一d(u。，u埘)三o(mod4)。由此可得d，2)=d，u。)+d(”。，z)三2(mod4)，由此
9、tlD(T7)c(T7)=C(T)。如果树T是由树T7通过运算仇得到的，那么c口)=c(T7)u也)。由引理223，得d(札，2)兰2(mod4)对任何树T的叶节点f成立。根据对树丁的归纳，知D(T7)c(T7)。设zD(T)以及2是树T的叶节点使得如(u，2)三2(mod4)。如果z=乙，u或屯，因为d(u，z)三2(mod4)我们可以导出矛盾。因此假设uy(丁，)。如果fL(T，)，那么，由归纳假设，口D(T7)c(T7)cc(T)。如果f=L，那么如(u，匕)=d(，乙)一4三2(mod4)。因为kL(T)，由归纳假设知，口D(T7)c(丁7)c(T)。引理225设T丁是一棵阶为仃有s个
10、支撑节点和2个叶节点的树，那么协(丁)=2s+(ns一21)2。证明我们仍就使用构造树T=死中的术语，并且设图日1的节点为叫和乩，以及图带有节点钍，t，且叶节点标为!缸，k。为了证明这个引理，我们对构造树r的运算个数七进行归纳。结果对乃=P5成立。现在假设结果对树族丁中所有通过毙一lo次运算得到的树成立。设T=死丁其中七22是通过运算倪，i=1，2，3由r=死一l丁得到的。设n7表示树T7的阶数，并设s7=Is(r，)I还有f7=lL(T，)l。设D是一个协口)一集，它包含TT中尽可能少的顶点，再设D7是一个协()一集。如果树T是由树T7通过运算Dl得到的，那么协口)=协(T，)，n=n7+1
11、，s=s7还有f=f7+1。根据对树丁7的归纳，协(T7)=2s7+(仃7一s一271)2。那么饰，(T)=协(r)=257+f(n7一s7一z71)21=2s+f(nsz1)21。如果树T是由树r通过运算D2得到的，那么我们有n=n7+2，s=s7+1和2=17+1。这里因为s=D7um，f。)是树丁的一个PDs，有协(T)俐=协(r)+2。根据性质221，有硼口。设cc(砷表示与顶点伽相邻的顶点。由我们对D的选择，我们有伽，k，c)D或加，c)D。如果_【叫，k，c)D，那么D一叫，f。)是树T7的一个PDs，因此协(T7)协汀)2。由此可知研(T)=22主要结果15协(7)+2。根据对树
12、7的归纳，去验证，研口)=2s+f一sc1)21将是一个很常规的事情。如果伽，c)D，设存在一个顶点y(c)伽)满足!，4(T7)。根据性质221，yD。根据性质22，2，顶点可的邻点除了c都是树T的叶节点。因为顶点可必须在集合D中成对，所以一定存在一个叶节点幻D。那么D一舰，叫，是树T7的一个PDS，因此协(7)S协(x)22主要结果17的阶数为n并且直径至少为4还有s个支撑节点和f个叶节点。在接下来，我们设s7和z，分别表示树T，的支撑节点数目和叶节点数目。如果任意一个树T的支撑节点，称为z，它与两个或两个以上的叶节点相连，那么设树T7是从树T通过移去与节点z相连的叶节点得到的。那么协(r
13、)=协(T)，n7=nl，s7=s还有z7=z一1。注意到dinm(T7)=出nm(T)4。对树T7应用归纳假设，我们可得到希望得到的不等式。更进一步，如果协(T)=2s+(nsf一1)2，那么协(T7)=2s+f(nsz1)21=2s7+(n一5一f一1)2，还有T，丁。因此，我们有T丁且知它是通过树T，经过运算01得到的。自此以后，我们假设树T的每一个支撑节点都只和一个叶节点相连。我们现在对树T进行根化处理，根节点为r并有最大的离心率，使得出口m(T)4。设u是一个距离顶点r距离最远的一个支撑节点，设也是节点t，的在根化树里的父节点，再设叫是节点u的在根化树里的父节点。注意到d(r，t，)
14、=di口m(T)一1和de岔T)2。用足表示从顶点z导出的子树和它的在根化树T里的子孙节点。我们区别以下的两种情形。情形1de9T(让)3那么或者节点让有一个孩子节点6t，那是一个支撑节点或者顶点u的每个孩子节点除了u都是叶节点。首先假设顶点札有一个孩子节点6且这是一个支撑节点。设r=T一正。那么有n，_n一2，s，=s一1和z7=z一1。一个协(T，)集通过添加顶点u和与它相连的叶节点能够扩展成为树T的一个PDs。所以我们有协口)协(T7)+22s+f(n7一s一z7一1)21+2=2(s1)+(n一2一s+1一f+l一1)21+2=2s+(凡一s一2一1)21。更进一步，如果协p)=2s+
15、ms一21)2，那么我们可以通过这个不等式链来得到一个等式。特别的，协(T7)=2s7+f(n7一s7一z，-1)2和ss一1，z7=cl。根据对树，的归纳假设，有T，丁，那么树T是通过树z通过运算仍得到的，因此有r丁。现在假设节点u除了节点t，之外全都是叶节点。根据假设树T的每一个支撑节点都只和一个叶节点相连，我们可以得到de卵(u)=3。如果de卵(叫)3，第三章成对控制边临界图的一些研究研究图论参数的临界性是图论中一个基本问题。临界性是指任意添加(或删去)图上的一个顶点(或者一条边)均导致某个图论参数(例如连通性，色数)增加(或者减少)。本章，我们研究图的成对控制边临界性，即任意添加图的一条边，均导致该图的成对控制数减少。31成对控制边临界定义311设图G=(UE)不含孤立点，如果对任意不相邻的两个顶点t，u，都有协(G+u钞)2。证明假设图G是4一协临界图，有，枷(G)=4。因此对任意的边eE(D)，可以得到协(G+e)=2。如果d钯m(0一e)=2，那么根据引理315可以知道协(再)=协(G+e)4，矛盾。所以diom(0一e)2或者dfom(0一e)=1。如果出口m(Ge)=22中国科学技术大学硕士学位论文1，那么图Ge就是一个完全图，这是不可能的。所以有dtom(召一e)2。又因为协(G)=4，根据引理315可以知
