【摘 要】
:
设G=(V,E)为简单连通图,节点集S(?)V称为G的电力控制集,若V中的所有节点都被S中的节点“控制”.这里节点控制它自己和它所有的邻居,并且若一个被控制的节点除了一个以外的所有邻居都被控制,则这个剩下的邻居也变为被控制的.电力控制集的最小基数称为电力控制数,记为γp(G).基数为γp(G)的电力控制集s称为G的最小电力控制集,记为γp(G)-集.电力控制集问题就是确定给定图的电力控制数,最初由
论文部分内容阅读
设G=(V,E)为简单连通图,节点集S(?)V称为G的电力控制集,若V中的所有节点都被S中的节点“控制”.这里节点控制它自己和它所有的邻居,并且若一个被控制的节点除了一个以外的所有邻居都被控制,则这个剩下的邻居也变为被控制的.电力控制集的最小基数称为电力控制数,记为γp(G).基数为γp(G)的电力控制集s称为G的最小电力控制集,记为γp(G)-集.电力控制集问题就是确定给定图的电力控制数,最初由T.W. Haynes提出,并证明了这个问题对于一般图而言是NP-完全的.本文在总结了前人的理论成果的基础之上,系统地论述了图的电力控制集问题.众所周知,完美图是图论研究中的一个重要图类.本文第二章研究完美图上的电力控制集问题.对于树的电力控制集问题和k-电力控制集问题,给出了在线性时间内计算控制集的标号算法,改良了已有的算法.对于节点带权值的树,也给出了在线性时间内计算电力控制数的动态规划算法.对于块图上的电力控制集问题,给出了在线性时间内计算电力控制集的标号算法,该算法直接在块图上操作,减少了中间的转化步骤,并且在对节点排序时,也可任意选取根节点,改良了已有的算法;并首次给出了块图上k-电力控制集问题的线性时间算法.对于区间图上的电力控制集问题,利用标号加上集合的方式,给出了在线性时间内计算电力控制集的算法,该算法直接从区间图的节点序出发,且仅依赖于一个节点序,改良了已有的算法.本文第三章对电力控制集问题作难度分析,按照将一般的图上的控制集问题可归约为电力控制集问题的方式,得出电力控制集问题的NP-完全性.本文第四章介绍其他一些特殊图类上电力控制集问题的研究情况,主要是路和圈的笛卡儿乘积图,以及一般的Petersen图,描述了网格图上电力控制集问题的解决算法.
其他文献
基于非线性光学和频产生以及脉冲激光泵浦探测原理,频率上转换荧光光谱技术具有超快的时间分辨,尤其是近年来飞秒激光技术的不断发展和普及,频率上转换的时间分辨已经达到了飞秒量级,为研究生物大分子的精细结构、功能以及超快动力学提供了重要的技术手段和方法。结合相关的光学设计和程序设计技术和方法,我们自行设计和组建了一套专门用于研究生物大分子动力学的非线性频率上转换荧光光谱测量系统。目前,我们利用这套频率上转
细菌视紫红质(Bacteriorhodopsin, bR)是嗜盐杆菌细胞膜上主要的蛋白质,它由248个氨基酸组成并形成一个具有七个跨膜α螺旋的结构。bR的配体视黄醛分子作为发色团与蛋白第七个跨膜螺旋上的Lys216以共价键结合形成质子化的希夫碱,对光波具有选择性的吸收。作为一种光驱动质子泵,在光的驱动下,引发视黄醛的构象异构转变,并能够逆着电化学梯度,将H+从膜内泵到膜外。越来越多的研究表明,芳香
本文主要研究了线性、对称陀螺、近非对称陀螺这三种类型冷分子在静电场中的摆动光谱,及它们在电场中的一些现象,如能级变化、取向、系综取向、电场的绝热和非绝热引入等。除此之外,我们还提出了一种采用线性冷分子的摆动光谱来测量静电场矢量的新方案。文中通过大维基矢下的强电场与冷分子的相互作用矩阵来研究问题,而不是采用微扰理论。编写的计算程序基于非零矩阵元来减少程序运算时间,对近非对称陀螺分子在强场中的振转光谱
逆转录病毒是一类感染宿主细胞,并整合到宿主基因组中的正链RNA病毒,其中已发现的数量最多的一类是gamma逆转录病毒。gamma逆转录病毒可以感染一大类脊椎动物,特别是哺乳动物,目前为止,已发现被感染的哺乳动物包括猫、猪、小鼠、考拉、灵长类动物等。它们还会引发包括白血病、免疫系统疾病以及神经性疾病等多种疾病,因此,是一类广受关注的病毒。然而,虽然gamma逆转录病毒数量众多,但作为哺乳动物中第二大
藏狐(Vulpes ferrilata)在2009年被中国物种红色名录收录为濒危物种,是引发包虫病(Echinococcosis)的棘球绦虫(Echinococcus)终末宿主,了解藏狐的种群数量和动态是制定保护管理对策、有效监控流行病的基础。然而藏狐相对较低的种群密度和机警的习性,给绝对种群数量的准确估计带来了挑战,已有的藏狐种群数量调查很少,调查方法都为样线直接计数法,这种方法受调查时间、强度
50Hz工频磁场作为环境中最为常见的极低频磁场之一,它对生物可能造成的影响是很多研究者关注的重点之一。我们已取得的前期的研究结果表明:0.4mT50Hz工频磁场的辐照细胞仅30min就能使细胞表面的表皮生长因子受体(epidermal growth factor receptor, EGFR)发生聚集;同时引起人羊膜成纤维细胞(FL细胞)和中国仓鼠肺成纤维细胞(CHL细胞)的细胞骨架发生重组;且P
图谱理论是图论研究的一个非常活跃而又重要的研究领域,它在量子化学,统计力学,计算机科学,通信网络以及信息科学中均有着广泛的应用.在图谱理论中,为了研究图的性质,人们引入了各种各样的矩阵、诸如图的邻接矩阵、无符号拉普拉斯矩阵(即拟拉普拉斯矩阵)、关联矩阵、距离矩阵等等,这些矩阵与图的结构都有着密切的联系.图谱理论的一个主要问题就是研究图的性质能否以及如何由这些矩阵的代数性质反映出来.这里所指的矩阵的
盘基网柄菌是以二分裂方式进行繁殖的阿米巴类的原生动物,在生存环境不良条件下(如饥饿),单个分散的盘基网柄菌细胞在cAMP的趋化作用下相互聚集开始多细胞发育。该发育时期要经过细胞聚集、细胞丘、蛞蝓体和子实体四个阶段。在细胞丘阶段,细胞依赖黏附分子(如gp150, gp80, DdCAD-1)的相互作用向中心聚集,形成多细胞组成的丘状结构。其中,gp150异嗜性细胞表面粘附分子对细胞的发育和分化有重要
众所周知细胞是构成有机体以及生命活动的基本单位,对细胞进行研究是认识生命科学之前提。细胞的新陈代谢、光合作用、信息传递和物质的跨膜运输等都与细胞荷电粒子或者电活性粒子的传递息息相关。众多的生理活动都伴随着定向的电荷传递、传导或转移,所以电化学反应为细胞基本的生命活动基础,电化学是研究细胞最为有效的研究生命活动的方法之一。由于生物组织中各种化学成分的分布具有很大程度上的不均一性,细胞与细胞间也存在着
蛋白酶体激活因子REGγ在近年的研究中被证明除了能降解短的多肽之外,还能通过降解哺乳动物细胞中完整的蛋白质发挥多种重要的生物学功能。本研究利用REGγ基因敲除小鼠建立了血管内皮细胞生长因子(VEGF)诱导的角膜血管新生和氧诱导视网膜血管新生模型,首次发现了REGγ可以促进小鼠血管新生。VEGF诱导的REGγ基因敲除小鼠动脉环血管新生也同样受到抑制。在体外试验中,人脐静脉内皮细胞(HUVEC)中高表