【摘 要】
:
图的支配集及其扩展是图论中的经典组合优化问题,在优化理论、城市交通路线规划、通信等领域中有广泛应用。然而,最小支配集及其扩展问题已被证明为NP难问题,已有近似求解算法的复杂度和精度有待进一步改进。本文结合粗糙集理论研究了无向图的最小支配集求解方法,主要工作及创新点包括以下几个方面:1.基于粗糙集理论中的属性序思想,提出了顶点序下无向图极小支配集求解算法。首先,在给定无向图顶点集上定义一个全序关系(
论文部分内容阅读
图的支配集及其扩展是图论中的经典组合优化问题,在优化理论、城市交通路线规划、通信等领域中有广泛应用。然而,最小支配集及其扩展问题已被证明为NP难问题,已有近似求解算法的复杂度和精度有待进一步改进。本文结合粗糙集理论研究了无向图的最小支配集求解方法,主要工作及创新点包括以下几个方面:1.基于粗糙集理论中的属性序思想,提出了顶点序下无向图极小支配集求解算法。首先,在给定无向图顶点集上定义一个全序关系(即,顶点序),进而在顶点闭邻接集集合上定义一个二元等价关系;然后,基于该二元等价关系提出了一种顶点序下的极小支配集算法;最后,证明了该算法在给定顶点序下求解相应极小支配集的完备性与唯一性,通过实例验证了算法的正确性和有效性。2.基于粗糙集理论中决策表属性约简原理,提出了无向图的一种启发式最小支配集近似算法。首先,利用图的邻接矩阵构造一个诱导决策表,证明了图的最小支配集与其诱导决策表的最小属性约简等价;其次,基于诱导决策表的特征,采用前后向搜索机制和诱导决策表正域的累积计算策略,提出了一种复杂度较低的启发式最小支配集近似算法;最后,在公用数据集上与典型算法进行了实验对比,结果表明该算法在运行时间方面具有明显优势,且能得到更高精度的近似最小支配集。3.针对动态图提出了一种增量式支配集更新算法。首先,分析了支配集在无向图四种基本动态变化(插入顶点、删除顶点、插入边、删除边)下的特点,由此给出了相应的支配集更新策略;然后,提出了动态图的一种极小支配集增量式更新算法;最后,通过在公开的数据集上与非增量式算法进行了实验对比,验证了增量式更新算法的正确性和有效性。综上所述,本文在无向图的最小支配集近似求解算法方面取得了一些进展,有助于进一步研究最小支配集及其扩展问题,有望促进粗糙集理论与图论研究的新思路。
其他文献
滚动轴承作为机械设备的关键部件之一,其工作状态和性能直接影响着机械设备的正常工作和安全运行。如果不能及时预测滚动轴承的健康状况或损坏情况,不仅会影响机械设备维修和更换计划的制定,还容易造成严重的经济损失,甚至发生安全事故。因此,对滚动轴承性能退化趋势进行准确地预测有助于工程人员合理制定轴承的维护策略和更换计划,以保障机械设备的安全服役,提高经济效益。本文的研究方法属于数据驱动方法,研究内容主要为:
随着我国经济的发展、生活水平的不断提高,人们对道路交通的要求也越来越高。在满足传统道路安全性、舒适性的同时,人们对改善交通环境的需求也越来越大。彩色沥青(别名彩色胶结料)作为一种新型的路面建筑材料,能有效美化道路,还能与周围的环境形成一道亮丽的风景线。以乳化沥青为基础的微表处技术是一种工作性能与经济效益良好的预防性养护方法,它能有效且快速的对路面病害进行修复。我国现目前大部分完工使用的道路进入到了
滑坡和泥石流等地质灾害给社会经济发展、群众生命和财产安全带来了巨大的影响。重庆市云阳县位于我国西南、重庆东北部,地势处于第一阶梯,山多坡陡是云阳县地形的特点,夏天受强降雨和三峡库区水位影响,区域内地质灾害频发。本文选择重庆市云阳县薛家沟周围地区作为研究区,利用极限平衡法模型对边坡稳定性进行研究。本文以分布式水文模型作为下垫面土层含水量计算模型;采用深度神经网络(DNN)来学习土壤含水量、地形坡度、
航空发动机、风电系统和武器装备等机械设备具有结构复杂、功能集成、寿命长和不易维修等特点,开展此类设备的系统可靠性评估和剩余寿命预测工作能及时找出系统工作能力的薄弱环节和制定科学合理的维修策略。机械系统在运行时会发生性能退化,零部件的失效状态不再是单一的正常-故障二态性,特别是在复杂工况下更是呈现出多种复杂特性,如:多状态性、动态性和不确定性等,同时,系统还会受到外界运行环境带来的冲击失效,且和系统
SBS分子结构形态、S/B嵌段比、掺量对SBS改性沥青性能有显著影响,本文以不同嵌段比(S/B值)和结构的SBS改性剂为基础,使用不同掺量,研制SBS高粘改性沥青,探讨不同S/B值、结构和掺量对SBS高粘改性沥青制备工艺、技术性能的影响,最后利用分子动力学模拟技术对不同嵌段比的改性沥青粘度进行模拟。首先,查阅资料,初步确定工艺参数,使用不同嵌段比、结构和掺量的SBS改性剂制备SBS改性沥青,并针对
电子商务的发展形成了线上线下双渠道的销售环境,也使消费者购买行为呈现出新的特点,消费者在线下进行体验然后在线上进行购买的搭便车行为已经成为了常态。消费者搭便车行为往往造成线上线下销售渠道的冲突,如何在不同权力结构的供应链环境中探讨消费者搭便车行为下的合理定价以及实施有效的销售策略已经成为重要课题。借鉴国内外相关研究成果,本文从制造商和零售商的博弈关系着手,基于消费者的搭便车行为对竞争双渠道以及制造
因为光催化反应具有节能、低污染和降解能力彻底等优点,所以利用光催化技术处理环境污染和水体污染已成为一项具有前景的研究。在众多的光催化材料中,TiO2由于高活性、高稳定性、无毒、无污染以及合适的能带位置等优点,被认为是最具应用前景的光催化材料之一。但是它仍然存在着一些缺陷,光利用率低和量子效率低这两大问题,一定程度上制约了它在工业上的应用。为了提高光催化技术的应用范围,研究出新型高活性TiO2催化剂
自我国加入世界贸易组织以来,国内企业积极拥抱全球化,开始在全球市场寻求供应商。然而,伴随着全球采购带来的低价优势,国内企业也面临着更加不确定的采购环境,这对供应链的质量和效率也提出了更高的要求。特别是近年来,一方面,国际上“黑天鹅”事件频繁发生,采购环境的不确定性呈现不断增加的趋势;另一方面,国内企业系统集成能力逐渐提升,纷纷对采购、库存和配送进行协同优化。这使得如何在不确定的环境中,协同优化多品
近年来,重庆市航运业迅猛发展,港口吞吐量及港口集疏运货物量处于我国内河港口的前列,由于港口高耗能和高排放特性,相应的温室气体排放量也随之不断上升,带来的港口生态环境问题日益加剧,低碳可持续绿色发展模式成为港口发展的必然趋势。为了推动重庆港低碳绿色发展,研究港口机械设备碳排放规律,构建污染气体排放清单和科学制定减排策略对重庆港的长远发展具有十分重要的意义。通过分析国内外研究现状,对近年来研究所取得的
新一代信息技术在制造业的应用,使得制造企业在实现规模效益的同时,能够满足消费者的个性化定制需求。数字经济下,依托于电商平台采用定制工具箱等方式实现大规模定制已是多数定制企业的选择。这种大规模定制对于消费者个性化属性相对较少的定制品类比较容易实现,但对于不止依赖虚拟空间分析,还需考虑定制产品物理空间约束的产品具有一定局限性。不同于一般定制产品,该种场景依赖型定制产品既要深度考虑消费者的个性化需求,又