【摘 要】
：
图的着色问题是图论中研究最广泛的问题之一,也是一个重要和基本的问题。实际生活中的很多问题都可以看作是图着色问题。边着色图是指对一个图上的每一条边赋予一个颜色,图的适当边着色是指给图上每一个边着上颜色后,使得相邻的边着不同的颜色。本文研究边着色图上最大弱适当树问题:给定一个顶点r,寻找以r为根节点的顶点个数最多的弱适当树T,即从根r到树T的任意叶子节点的路径都是适当着色的,但树顶点的邻边可以着相同颜
论文部分内容阅读
图的着色问题是图论中研究最广泛的问题之一,也是一个重要和基本的问题。实际生活中的很多问题都可以看作是图着色问题。边着色图是指对一个图上的每一条边赋予一个颜色,图的适当边着色是指给图上每一个边着上颜色后,使得相邻的边着不同的颜色。本文研究边着色图上最大弱适当树问题:给定一个顶点r,寻找以r为根节点的顶点个数最多的弱适当树T,即从根r到树T的任意叶子节点的路径都是适当着色的,但树顶点的邻边可以着相同颜色,这一问题已被证明是NP-hard的。本文考虑设计求解此问题的多项式时间近似算法并通过计算机编程实现该算法。第一章,首先介绍了边着色问题和组合优化问题的基本概念,给出近似算法和算法的计算复杂性的相关定义,并对国内外边着色图上最大适当树问题和最大弱适当树问题进行综述,最后对整篇论文的结构进行了简单描述。第二章,重点考虑了当颜色数等于2时的最大弱适当树问题,基于贪婪思想设计了一个近似算法,并对近似算法的最坏情况界进行理论分析,得到该算法的最坏情况界为2,并提供了紧例。.第三章,我们使用Python语言编程实现该算法,随机生成s=10,n=200;s=20,n=400;s=20,n=600的算例.每对s,n随机生成10个算例,并对10个算例进行比较,实现了边着色图上最大弱适当树的贪婪算法GA的数值实验。第四章,简单总结本文所研究的内容。
其他文献
作为一种频繁发生的自然现象,海洋内波对海上军事活动和海洋工程建设有着严重的破坏性影响。随着海洋工程和海洋经济的快速发展,海洋内波监测和预报技术已经成为国内外研究热点。传统的内波监测方法主要是锚系阵列监测以及卫星遥感观测。锚系阵列监测方法是基于温盐深链和ADCP等传感器,通过对海洋水体物理变化监测来实现海洋内波监测。卫星遥感观测方法是基于卫星图像分析,通过对内波引起的海面波纹成像特征提取和观测来实现
城市的绿化水平近年来不断提高,而绿化草坪的维护需要耗费大量人力资源,故以智能割草机代替人工维护的方式越来越受到市场的欢迎。但是在目前市场上大多数具备定位功能的智能割草机中存在如下缺点:智能割草机的室外定位精度不高,易受到多径效应和NLOS的影响导致定位稳定性较差;且通常采用单一的随机路径规划进行割草作业,其割草作业耗时较长且容易存在部分区域漏割的问题。本文设计了一种基于超带宽定位的智能割草机系统,
针对现有指针式仪表读数识别算法存在鲁棒性和通用性差的问题,本文对算法中的关键步骤展开了研究,并提出了一套基于深度学习的指针式仪表读数识别新算法,主要步骤包括图像校正、图像极坐标变换以及仪表示数计算。本文的主要研究内容包括:（1）基于刻度值文本的图像校正方法。针对传统图像校正方法存在仅适应某一特定仪表和鲁棒性较差等问题,且考虑到刻度值文本是仪表的通用特征,本文提出了一种基于刻度值文本特征匹配的仪表图
陆基导航系统在无线通讯、导航定位、气象预测等领域有着广泛的应用,相比于星基导航系统具有信号传播稳定、不易受干扰等优点,可作为星基导航系统的重要备份。但是由于地波信号传播路径复杂、以及受气候、季节等难以预测的因素影响,导致传播时延计算精度较低。其中附加二次相位因子（ASF）是影响精度的关键因素,本文深入分析了影响ASF时延的因素和修正方法,具体工作内容如下:1、阐述了低频地波传播时延的三个组成部分。
近些年,人们对高速率通信有了越来越大的需求,毫米波频段因其具有频段资源丰富、传输速率高等优点逐渐成为无线通信系统的发展方向。Ka波段作为毫米波频段的一部分,受到了广泛研究。而CMOS工艺在成本和集成度方面的表现要优于化合物工艺。并且低噪声放大器是无线通信系统的重要组成部分。因此研究如何基于CMOS工艺设计出工作在Ka波段的低噪声放大器对现代通信系统的发展有重要意义。首先,文章阐述了国内外毫米波频段
无线传感器网络（Wireless Sensor Network,WSN）是一种具有连通性的网络系统,该系统将数量不定的传感器以非结构化但逻辑有序的方式部署在监测区域内,传感器之间通过无线信道传输的控制消息来获取相关信息,因此具有感应环境、收集处理数据以及交互信息的能力。随着无线传感器网络的深入应用,不同领域的专家学者们也相继开展研究。在5G时代下,人们对网络的覆盖率要求更高,在地理环境复杂,地势偏
近年来,随着我国集成电路芯片领域高速发展,片上系统（System on Chip,SoC）设计趋向模块化,其复杂度和工艺要求也日益提高,这对集成电路的验证提出巨大挑战。通用验证方法学（Universal Verification Methodology,UVM）的诞生和发展极大提高了集成电路验证的工作效率,其通过对自身技术更迭来不断适应当前大规模芯片验证。同时,由于CPU技术的不断更新迭代,其运算
如今,通信为人们带来了便利,通信中信息传输的容量和速率更是万物互联基础。与传统的电子通信系统相比较,全光通信网络信号处理速度快、信息交换及时不再受“电子瓶颈”的影响。作为全光通信网络的关键器件,全光逻辑门已广泛引起国内外学者的关注。本文利用半导体光放大器（Semiconductor Optical Amplifier,SOA）、Sagnac干涉仪（Sagnac Interferometer,SI）
无线电能传输技术作为一种新的供电方式逐渐成为研究热点。其中,磁耦合谐振式无线电能传输技术（Magnetic Coupled Resonant Wireless Power Transfer,MCR-WPT）具有高效率、中等传输距离、对传输介质依赖小等优点,成为主要研究方向。目前,MCR-WPT技术主要研究集中于“一对一”线圈传输模式,但存在为满足时效性需求的情况下,需要多个接收负载端的应用场景。本
近年来,随着鳌虾养殖规模快速增长,其人工繁殖相关的智能化技术需求也在不断增长。其中,对孵化场中虾卵的准确计数是鳌虾人工孵化过程中的基本要求。准确的数量信息能够给养殖场管理者提供丰富的信息反馈,如母虾抱卵数、孵化率、存活率等,能够帮助管理者实现更加精细和有效的放养管理。然而,目前在孵化场中的虾卵计数主要由相关人员进行人工打样和人工清点。人工方式必然费时费力,容易出错,而且在操作方面的一致性和连续性较