四色定理的三代证明 被引量：7

1

作者 王献芬 胡作玄 《自然辩证法通讯》 CSSCI 北大核心 2010年第4期42-48,共7页

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

关键词 四色定理 计算机辅助证明 形式证明 数学证明 图着色理论

原文传递

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

2

作者 周光辉 敬帅 梁伟 《系统工程理论与实践》 EI CSSCI CSCD 北大核心 2021年第9期2338-2354,共17页

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

关键词 调度 对地观测 飞艇 图着色理论(graph coloring theory GCT) 文化基因算法(memetic algorithm MA)

原文传递

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

3

作者 段瑞杰 姚富强 +2 位作者 李永贵 牛英滔 齐扬阳 《计算机工程》 CAS CSCD 北大核心 2016年第4期94-100,共7页

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

关键词 短波无线接入网 智能跳频 定频通信 频谱分配模型 图着色理论

下载PDF 职称材料

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

4

作者 吴润泽 秦宇浩 樊冰 《光通信技术》 2021年第7期41-47,共7页

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

关键词 弹性光网络 图着色理论 混合整数线性规划 带宽阻塞率

下载PDF 职称材料

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

5

作者 段瑞杰 姚富强 +1 位作者 李永贵 郭鹏程 《计算机应用》 CSCD 北大核心 2016年第8期2163-2169,共7页

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

关键词 短波无线接入网 智能跳频 非对称频谱配置 固定式频谱分配方法 图着色理论 动态频谱分配

下载PDF 职称材料

基于用户需求的改进型CSGC频谱分配算法 被引量：2

6

作者 胡虹梅 覃玉荣 《无线电通信技术》 2011年第4期18-20,52,共4页

针对基于图论着色模型的频谱分配算法目前未能很好解决用户自身需求这一重要问题,研究了基于用户需求的改进型颜色敏感的图论着色(Color Sensitive Graph Coloring,CSGC)频谱分配算法。该算法通过降低已满足需求用户的分配优先级,使系... 针对基于图论着色模型的频谱分配算法目前未能很好解决用户自身需求这一重要问题,研究了基于用户需求的改进型颜色敏感的图论着色(Color Sensitive Graph Coloring,CSGC)频谱分配算法。该算法通过降低已满足需求用户的分配优先级,使系统未满足的带宽需求总量达到最小化,在保证原CSGC算法性能的同时,较好地实现了频谱分配与自身需求相匹配。仿真结果表明该算法是有效的。 展开更多

关键词 图论着色模型 频谱分配 CSGC 用户需求

下载PDF 职称材料

基于时间Petri网的并行测试任务过程建模及验证技术研究 被引量：2

7

作者 吕晓明 黄考利 连光耀 《计算机测量与控制》 CSCD 北大核心 2012年第5期1310-1314,共5页

为满足复杂装备中某些关键系统的实时测试与诊断需求,在测试性设计过程中开展并行测试调度优化研究;针对测试任务之间关联关系复杂的实际情况,通过建立基于图染色理论的测试任务关系模型,实现了对系统资源冲突、死锁等问题的形式化描述... 为满足复杂装备中某些关键系统的实时测试与诊断需求,在测试性设计过程中开展并行测试调度优化研究;针对测试任务之间关联关系复杂的实际情况,通过建立基于图染色理论的测试任务关系模型,实现了对系统资源冲突、死锁等问题的形式化描述,将并行测试调度优化转化为求解图的色数问题;并在求解图的色数问题过程中,利用改进的遗传算法逐步求解图的最大独立集,即可并行测试的测试任务子集,从而获得并行测试调度方案;最后,利用某实例对文章提出的并行测试任务调度建模及优化方法进行了验证,优化效果明显,证实了该方法对解决并行测试调度优化问题的有效性。 展开更多

关键词 并行测试调度 图染色理论 最大独立集 改进遗传算法

下载PDF 职称材料

基于认知无线电网络中用户需求频谱分配算法 被引量：2

8

作者 林冉晴 陈跃斌 +1 位作者 谭元 王小芳 《太赫兹科学与电子信息学报》 2013年第3期402-405,共4页

在认知无线电网络中,对图着色频谱分配算法进行了分析,发现只有少数已有算法考虑到用户的需求是否得到满足,导致需求低的用户分配到过多资源。为解决这个问题,根据基于用户需求的图着色论频谱分配算法,对用户的满意度设置优频谱分配优... 在认知无线电网络中,对图着色频谱分配算法进行了分析,发现只有少数已有算法考虑到用户的需求是否得到满足,导致需求低的用户分配到过多资源。为解决这个问题,根据基于用户需求的图着色论频谱分配算法,对用户的满意度设置优频谱分配优先级函数,满意度差的用户进行优先选择分配,得到一种改进算法。仿真结果表明,基于用户需求的频谱分配算法的改进算法,能够增加系统的信道效益,提高用户的需求满意程度。 展开更多

关键词 认知无线电 图着色 用户需求 频谱分配

下载PDF 职称材料

基于图着色理论的异构车联网时隙分配方案 被引量：1

9

作者 张鹏涛 周一青 +2 位作者 刘航 田霖 石晶林 《高技术通讯》 CAS CSCD 北大核心 2016年第6期550-557,共8页

针对异构车联网系统车辆较多导致时隙分配困难的问题,提出了一种基于图着色理论的时隙分配方案。该方案以考虑两跳内节点的图为模型,通过图着色的方法分配时隙,有效降低了隐藏终端带来的丢包;另外给出了一种高效实用的时隙重用分配算法... 针对异构车联网系统车辆较多导致时隙分配困难的问题,提出了一种基于图着色理论的时隙分配方案。该方案以考虑两跳内节点的图为模型,通过图着色的方法分配时隙,有效降低了隐藏终端带来的丢包;另外给出了一种高效实用的时隙重用分配算法。该算法根据度定义权值以确定车辆分配时隙数目,保证了公平性,提高了时隙重用,进而提高了消息发送的可靠性,同时也适用于网络拓扑多变的车联网场景。仿真结果表明,在车辆数为200、时隙数为100时,与传统时隙分配方法相比,该方案的车辆平均收包率获得大幅提升。此外,随着时隙重用的增加,车辆间干扰增强,从而导致平均收包率降低。研究还发现,增加车辆发射功率时,由于接收端信干噪比先增加后趋于不变,所以平均收包率也先增加后趋于不变。 展开更多

关键词 异构车联网 图着色 时隙重用 发射功率 收包率

下载PDF 职称材料

基于图着色理论的阵列天线校正方法 被引量：1

10

作者 高卫斌 党锐锐 杨李杰 《遥测遥控》 2019年第3期1-10,共10页

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

关键词 图着色理论 阵列校正 平面相控阵 幅度相位误差

下载PDF 职称材料

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

11

作者 李胜男 李永贵 +1 位作者 牛英滔 闫岩 《通信技术》 2017年第2期255-261,共7页

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

关键词 抗干扰 动态频谱分配 图着色理论 动态业务需求

下载PDF 职称材料

基于图染色理论和遗传蜂群算法的并行测试任务调度 被引量：1

12

作者 吴勇 王雪 赵焕义 《计算机应用》 CSCD 北大核心 2015年第5期1280-1283,1289,共5页

针对并行测试中任务优化调度这一关键性问题,提出了一种图染色理论和遗传蜂群算法相结合的任务调度优化算法。首先,建立了基于图染色理论的并行测试任务关系模型,用图来描述测试任务占用仪器资源的情况;然后,在测试任务关系模型的基础上... 针对并行测试中任务优化调度这一关键性问题,提出了一种图染色理论和遗传蜂群算法相结合的任务调度优化算法。首先,建立了基于图染色理论的并行测试任务关系模型,用图来描述测试任务占用仪器资源的情况;然后,在测试任务关系模型的基础上,将遗传算法特有的交叉、变异操作与人工蜂群(ABC)算法相结合搜索最优解,能够有效避免算法早熟并且加速算法收敛;最终得到并行度最大的任务分组方案。经仿真验证,所提方法能有效地实现并行测试,提高自动测试系统的测试效率。 展开更多

关键词 并行测试 遗传蜂群算法 图染色理论 自动测试系统 任务调度

下载PDF 职称材料

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

13

作者 殷君茹 唐小明 +1 位作者 李惺颖 卜祥亮 《吉林大学学报（理学版）》 CAS CSCD 北大核心 2015年第3期525-530,共6页

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

关键词 空间数据部署 数据粒度 并行环境 图着色理论 负载均衡

下载PDF 职称材料

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

14

作者 李晟彬 唐小明 +2 位作者 李志清 殷君茹 李惺颖 《吉林大学学报（理学版）》 CAS CSCD 北大核心 2016年第3期524-528,共5页

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

关键词 并行计算系统 空间数据布局 图着色理论 多副本

下载PDF 职称材料

基于图着色模型飞机智能化排班算法的研究 被引量：1

15

作者 廖峰 刘红 文军 《中国民航飞行学院学报》 2012年第3期20-23,共4页

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

关键词 图着色理论 飞机智能化排班 顶点序列图着色算法

下载PDF 职称材料

分枝定界在多级动态频谱分配中的应用 被引量：1

16

作者 刘俊彤 王可人 冯辉 《信号处理》 CSCD 北大核心 2014年第3期321-327,共7页

针对认知无线电动态频谱分配中认知用户较多,传统优化算法收敛时间较长的问题,本文结合分枝定界原理提出一种多级动态频谱分配算法。首先建立基于用户需求的多级动态频谱分配模型,然后借助图着色理论,将问题转化为函数优化问题,最后借... 针对认知无线电动态频谱分配中认知用户较多,传统优化算法收敛时间较长的问题,本文结合分枝定界原理提出一种多级动态频谱分配算法。首先建立基于用户需求的多级动态频谱分配模型,然后借助图着色理论,将问题转化为函数优化问题,最后借助分枝定界算法,通过把全部可行的解空间不断分割为越来越小的子集,从而实现了对该多级模型的频谱分配。仿真实验采用与遗传算法比较,通过对二者认知用户接入量和系统网络效益的分析比较,表明该算法对处理多级DSA分配问题的优越性,且所提算法具有较小的计算复杂度,具有较高的应用价值。 展开更多

关键词 认知无线电 动态频谱分配 图论 分枝定界

下载PDF 职称材料

全双工下基于最优匹配的D2D用户簇资源分配 被引量：1

17

作者 李校林 朱彬欣 《计算机工程与设计》 北大核心 2019年第4期959-963,共5页

全双工模式下,D2D链路的吞吐量约为半双工D2D链路的2倍,但全双工通信在带来吞吐量增加的同时也造成了严重复杂的干扰。由于频谱资源的匮乏,考虑多个D2D用户复用一个蜂窝用户的场景,此时共享同一蜂窝资源的D2D用户对之间还将产生同频干... 全双工模式下,D2D链路的吞吐量约为半双工D2D链路的2倍,但全双工通信在带来吞吐量增加的同时也造成了严重复杂的干扰。由于频谱资源的匮乏,考虑多个D2D用户复用一个蜂窝用户的场景,此时共享同一蜂窝资源的D2D用户对之间还将产生同频干扰。该方案通过图着色对D2D对进行分簇,使蜂窝用户在保证通信质量的条件下能复用足够多的D2D用户对;使用最优匹配算法为每个D2D簇分配最优蜂窝信道资源,达到减少链路间干扰的同时增大系统吞吐量的效果。仿真结果表明,该方案能有效提高频谱资源的利用率,增加系统容量。 展开更多

关键词 全双工 分簇 图着色 最优匹配算法 资源分配

下载PDF 职称材料

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

18

作者 张文俊 朱诗兵 +1 位作者 李长青 王雪 《科学技术与工程》 北大核心 2013年第27期8166-8172,共7页

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

关键词 信道分配 信道冲突模型 图N重着色理论

下载PDF 职称材料