【摘 要】
:
图的控制理论起源于运筹与优化中的实际问题,是图论的一个重要研究方向。随着网络和大数据技术的发展,人们面临的图都是规模较大、结构超级复杂的图。笛卡尔乘积图(交图)是一种很重要的图类,其规模大、结构也复杂。研究交图的控制数具有理论意义和应用价值。罗马{2}-控制(也叫意大利控制或弱2控制)是一种新型的控制。罗马{2}-控制可以描述成这样的一个防御问题:在古罗马帝国(图G),每个城市(顶点)最多能安置两
论文部分内容阅读
图的控制理论起源于运筹与优化中的实际问题,是图论的一个重要研究方向。随着网络和大数据技术的发展,人们面临的图都是规模较大、结构超级复杂的图。笛卡尔乘积图(交图)是一种很重要的图类,其规模大、结构也复杂。研究交图的控制数具有理论意义和应用价值。罗马{2}-控制(也叫意大利控制或弱2控制)是一种新型的控制。罗马{2}-控制可以描述成这样的一个防御问题:在古罗马帝国(图G),每个城市(顶点)最多能安置两支部队防守,有部队防守的城市是安全的。如果没有部队防守的城市都至少与两个有一支部队的城市相邻或至少与一个有两支部队的城市相邻,那么这个城市也是安全的。如果罗马帝国的所有城市都是安全的,那么这种安置部队的方式就是罗马{2}-控制函数。在保证所有城市都是安全的情况下,所需的最少部队数量就是图G的罗马{2}-控制数。本文研究的是路径与路径笛卡尔乘积图(路径交图)Pn□Pm的罗马{2}-控制数。确定图的罗马{2}-控制数是NP困难的。本文根据Pn□Pm的特点,研制了有效的分支限界条件,根据这些条件,设计计算机算法,构造了可递推的罗马{2}-控制函数。利用这些函数可以计算出Pn□Pm的罗马{2}-控制数的上界。然后利用数学推理证明了Pn□P2,Pn□P3罗马{2}-控制数的下界与其上界相等,从而确定了Pn□P2,Pn□P3罗马{2}-控制数的精确值。对于其它的路径交图Pn□Pm(n,m≥4),本文给出了较好的上下界。
其他文献
随着技术的高速发展与成本的不断降低,无人机已走入我们的生活并被广泛应用于多种领域,如遥感测绘、农业监控、安保巡逻、军事侦察等。相比较传统的人力巡逻或摄像头监控等安
本文考虑一类具有图约束的平行机调度问题,具体研究具有树状结构或路约束的同型平行机调度问题及具有图覆盖约束的不同类平行机调度问题。第一个问题描述为:给定无向图G(或有向图D)以及工件集,这里要求工件集与无向图G(或有向图D)中的边集(或弧集)建立一一对应关系,需要选取工件集的一个子集,使其满足无向图G(或有向图D)中树或路的属性,然后将其放置在同型平行机上处理,目标是使得机器的最大负载达到最小。第二
认缴制给予股东在出资方面相当程度“认”的自由,然而股东出资“认”而难“缴”已经成为一大问题。法律放松了公司资本管制,股东通过约定漫长的出资期限规避出资义务的履行,
随着移动通信设备的不断增加,移动数据流量不断增长,这对移动通信系统提出了更高的要求,第五代移动通信系统(5G,the 5th Generation of Mobile Communication Systems)应运而
由于决策环境的复杂多样性以及决策者自身理论知识和实践经验的局限性,使得决策信息不确定性趋向繁冗交互化。为了表达更高层次的不确定性偏好信息以及处理决策信息融合、排序问题,本文分别以犹豫二元语义模糊集、犹豫Fermatean二元语义模糊集为决策背景对聚合算子进行探索与研究,其主要内容如下:(1)针对犹豫二元语义模糊信息环境下不同的决策需要,建立相应的聚合算子及决策方法。对于属性权重部分未知的决策信息融
预约合同是社会实践的结果。市场活动中很多交易机会稍纵即逝,而交易事实或行为还未完善,为了提前固定磋商结果、增大交易的可能性,很多当事人选择先签订预约合同。由于我国
破产重整程序中的债转股已经成为重整计划的常见债权调整方案。债转股作为债权调整手段能够将债权人所持有的债务人债权转为股权,从而使困境企业减轻财务负担,帮助企业重获经
微生物膜燃料电池(microbial fuel cell,简称MFC)是一种产生电能的新方法-利用细菌通过生物质产生生物电能。微生物膜燃料电池不仅能产电,因其阳极反应物为有机物,所以还可以进行污水处理。微生物膜燃料电池中微生物膜是其关键组件,微生物膜的性能直接决定着微生物燃料电池的性能,而微生物膜的微观结构直接影响着微生物膜燃料电池的性能。用实验方法研究生物膜内的物质传递不仅成本高、周期长,还很难