弹性光网络中基于图着色理论的资源分配算法

传统的波分复用网络采用固定栅格,已无法满足网络需求。提出一种改进的基于图着色理论的路由选择频谱分配(GT-RSA)算法。首先,使用前k条最短路径算法确定备选路由集合,根据各备选路由集合建立备选路由关系图;然后,使用图着色理论的混合整数线性规划模型进行选路,根据分支定界的饱和度最大优先算法得到优解,同时完成频谱的路由着色分区分配;最后,采用分区前后适配(PAR-FLF)算法对业务完成频谱资源的分配。仿真结果表明:GT-RSA算法具有更低的频谱资源消耗、阻塞率以及更高的平均链路连续率。

基于图着色理论的阵列天线校正方法

由于受环境变化影响,大规模平面相控阵天线收发通道的幅相一致性会发生偏移,常常需要标校才能保证其正常工作,但目前阵列天线收发通道数量较多,校正过程复杂,而且费时费力。基于图着色理论提出一种阵列天线快速校正方法,将校正时隙分配转化为图论中的着色问题,通过最小化时隙着色提高每个校正时隙的复用率,以降低阵列通道校准次数,达到缩短全阵列校正时间目的。仿真表明,对正六边形、正方形和正三角形平面阵列,分别最多仅需要8个、9个和16个时隙就可完成全阵列校正。

干扰环境下基于图着色理论的动态频谱分配算法

针对目前无线通信系统抗干扰能力不强、资源利用率较低等问题,首先根据不同的业务优先级,建立了一种具有分层架构的动态频谱分配模型。然后,基于图着色理论,提出了一种动态业务需求条件下的频谱分配算法。该算法既能保证优先级高的通信链路优先分配信道,也能保证系统具有一定的均衡性。仿真结果表明,与固定频谱分配算法和传统动态频谱分配算法相比,该算法能够有效提升系统的抗干扰能力、均衡性和满意度,并可获得更高的吞吐量。

并行环境下基于图着色理论的空间数据部署

在面向计算部署到数据节点端执行的分布式并行环境下,提出一种基于图着色理论的适用于矢量空间数据的部署方法,将空间数据粒度的部署问题转化为图顶点着色的过程,提高了任意空间区域的信息查询效率.给出基于图着色理论的数据部署方法,并通过节点的任务量进一步改进算法,使得该算法可实现海量空间数据粒度的离散化部署,提高了空间数据检索和查询的并行化程度,充分利用了并行计算资源.

图的着色理论在自动导引小车调度规划系统中的应用

针对目前AGVS(自动导引小车系统)的调度问题的研究现状,为解决AGVS在FMS(柔性制造系统)中的调度次数最优化的问题,文章提出通过图的着色理论来研究满足一定约束的AGVS中调度问题,为满足此类约束条件的AGVS,给出一种行之有效的方法。理论分析结果表明,该方法能够在完成调度任务的同时,能够使AGVS的调度次数最优。图的着色理论对于此类问题的研究,较传统的方法,运算简单,求解直观。与此同时,该方法还可以确定此类问题背景下的系统所需小车的最小值。

斯泰勒三元系(STS)的着色理论

主要讨论斯泰勒三元系(Steiner Tripk Systems,以下简称STS)的着色理论.文献[1]中给出了顶点数为n的STS(n)的上色数的一个上界为[1og2(n+1)],并证明了当n=2k-1时该上界是可以达到的.该文作者在文章的最后提出的问题之一是当n≠2k-1时该上界是否也可以达到.本文改进了其上界为[1og2(n+1)],给出了一种由STS(n)构造了STS(3n)的方法,并证明了当n=3(2k-1)时,该上界也是可以达到的.

基于图着色理论的短波无线接入网动态频谱分配方法

针对现有短波无线接入网频谱分配采用固定式分配方法,难以满足使用智能跳频技术新要求的问题,分析智能跳频短波无线接入网的频谱需求,将短波无线接入网用户频谱分配问题转化为基于图着色理论的短波无线接入网动态频谱分配模型,并提出可用于智能跳频短波无线接入网的动态频谱分配算法。将使用此算法的智能跳频与使用固定式频谱分配方法的定频通信相比,仿真结果表明,该算法明显提高了短波无线接入网的子网可通性及网络吞吐量,并能降低互扰率,有效支撑智能跳频技术在短波无线接入网中的应用,同时快速、高效、准确地完成对可用频谱的分配。

着色理论在教学管理中的一个应用

建立了期末补考安排的图论模型 ,并利用着色理论进行优化 。

一种基于图N重着色理论的信道冲突模型

无线网络的信道分配问题是网络规划的重点,而信道冲突模型是信道分配的基础。通过对信道冲突模型的分析,可以估计该网络信道分配问题的规模,并得出理想条件下信道分配的结果。针对当前的信道冲突模型无法完整描述多射频多信道网络信道冲突情况的问题,提出图N重着色理论,以及基于图N重着色理论的信道冲突模型,并在图论运算基础上给出了模型建立和求解的方法。理论分析与仿真结果表明,该模型可完整描述多射频网络的信道冲突情况,突出了多个射频接口间的信道冲突问题,并将信道分配问题抽象为图N重着色问题,进而转化为一般的图着色问题,以便于信道分配问题的分析和求解。

基于图着色理论的多飞艇多载荷协同对地观测和数据传输调度模型与算法

临近空间平台是一类新兴的空间平台,可用于局部区域的对地观测.本文针对飞艇的特性和用户需求的复杂性,设计了多飞艇多载荷协同对地观测和数据传输体系,考虑常规观测任务的调度,以及应急观测任务的重调度.基于图着色理论(graph coloring theory,GCT),构建多飞艇多载荷协同对地观测和数据传输调度模型.将多飞艇协同对地观测与数据传输任务、任务间的冲突、以及飞艇和地面站分别映射为无向图中的点、边和颜色,从而将问题构建为图着色问题(graph coloring problem,GCP),最大化完成任务总收益的优化目标转换为GCP中最大化着色点收益.提出一种文化基因算法(memetic algorithm,MA),设计基于收益改进的禁忌搜索(Tabu search,TS)算子更新染色体,和对父代染色体中最大收益的连续基因进行遗传的交叉策略.数值实验结果表明,针对不同规模的算例,相较于TS和ILOG CPLEX,MA能够在合理时间内获得更满意的解.

基于图着色模型飞机智能化排班算法的研究

飞机排班问题关系到航空公司的系统运作,作用十分重要。通过对飞机排班问题的分析,把飞机分配问题转化为图着色,应用图着色理论,建立了飞机分配问题的图着色模型,引入时间片算法确定了航班使用飞机的时间冲突集合,根据"先到先服务"的原则给出了飞机分配的顶点序列着色算法。用一个具体的算例,验证了飞机智能化排班比现有航空公司调度员人工排班更先进、更实用、更加节省资源,使资源配置更加合理。

高校自动排考系统设计与实现

针对目前高校考务管理的现状,分析了自动排考系统所面临的必要和优化问题.以图论为理论依据,设计了一种能够高效解决这些问题的自动排考算法,并将该算法实现,得到了较好的效果.

反超图的最小边数问题

主要讨论了 3一致反超图的最小边数问题 ,给出了上色数为 2的 3一致反超图的最小边数的一个上界 .

基于认知无线电的自适应小波调制

为了解决小波调制频带利用率不高的缺点,提出了一种基于认知无线电的自适应小波调制方案。通过实时感知信道频谱占用情况,运用基于着色理论的贪婪算法,并以均方误差达到最小值为准则,调整权值,控制信源中各种不同的噪声敏感度信号的功率,实行动态频谱分配。在高斯白噪声信道中对其进行了仿真,仿真结果表明,在传递不同的噪声敏感度信号时,自适应小波调制方案的性能优于传统平均功率分配的小波调制。

约束性遗传算法的OFDMA毫微微蜂窝动态频谱分配

随着用户对于无线数据流量的需求日益剧增,频谱资源稀缺,经调查发现,仍旧有大量频段未被充分利用,造成了频谱资源的极大浪费,为了解决这一问题,频谱动态分配成为研究热点。本文在动态频谱分配的深入分析与研究的基础上,建立宏蜂窝和毫微微蜂窝双层网络模型,对毫微微基站进行着色分簇,用来减轻同层干扰,并根据簇中用户数的差异性,提出在毫微微蜂窝中基于约束性遗传算法的自适应频谱资源分配方案。最后仿真结果表明,该算法可以有效提高频谱利用率并使公平性得到改善。

基于图论的认知无线网络频谱动态分配

在认知无线电网络中,图论与量子遗传算法相结合的频谱分配策略能够提高频谱利用率,但存在早熟和收敛精度不够等缺点。为了解决该问题而实现算法的优化,对图着色理论的频谱分配模型进行数学建模,并针对该模型提出了改进的量子遗传算法。首先,通过使用小生境技术初始化种群,使种群分布更加广泛、算法的收敛度更高;其次,根据进化代数对量子旋转角进行实时动态调整,对染色体进行阈值变异,防止个体陷入早熟,跳出局部解;然后,对干扰约束条件进行重新设计,有效地避免盲目性,提高了网络的公平性和网络效益。仿真结果表明,所提算法有效地提高了频谱利用率,极大地增强了网络系统的性能。

基于并行计算的多副本空间数据离散布局策略

根据空间数据的特点及其关系,提出一个负载均衡的空间矢量数据布局目标,并结合特定环境,采用基于图着色理论的空间数据布局算法及多副本的数据安全机制,提高了空间数据部署在并行环境下,数据节点上任务的执行效率和数据安全性.实验结果表明,该布局方法能实现数据的均衡布局,兼顾了并行计算的效率和安全性,适应并行计算下更多的查询应用.

基于智能跳频的短波无线接入网动态频谱分配算法

针对现有短波无线接入网的固定式频谱分配方法难以满足使用智能跳频技术新要求的问题,分析智能跳频短波无线接入网的通信需求,提出智能跳频短波无线接入网的动态频谱分配策略及算法。首先将各机动用户和接入基站看作一子网;然后将对各子网的频谱分配建模为基于图着色理论的智能跳频短波无线接入网频谱分配模型;最后结合通信需求提出分配策略和算法,完成频谱分配并进行了仿真分析。结果表明,这些频谱分配策略及算法以不同的目标进行频谱分配,能够有效支撑智能跳频技术在短波无线接入网中的应用,与固定式频谱分配方法的定频通信相比,在网络效益、子网满意度、网络公平性、网络支持用户数和频谱利用率等方面均有明显提升,同时能有效降低互扰率。

怎样进行图论中最小最大定理的教学

在极值图论当中,写成最小最大定理形式的基础理论非常之多,按传统的教学安排和大多数图论专著的写法,它们分散于连通性、匹配理论、网络图论、独立与覆盖、着色理论等各章之中,独立地进行论述。事实上,它们之间存在着本质的联系,我们在科大数学系离散数学专门化教学中,按内在的逻辑关系,以最大流最小截定理为发祥点。

四色定理的三代证明

四色猜想是图论中的一个重要问题。它从猜想到定理历经三代证明:1976年阿佩尔和哈肯的计算机辅助证明、1994年西缪尔等人的修正、2005年贡蒂埃的形式证明。每一代证明都有其特点和不足。本文对这三代证明进行了简单的评述,说明由一个经验来源的问题如何逐步得到解决并在发展过程中形成诸多新的数学分支。它的重要性不在于结果本身而是从它的证明中可学到的潜在道理。本文提出数学证明的一个方面,即用有限驾驭无穷,同时在四色定理的证明史中表明简化永远是数学方法的灵魂。