重载费用欧拉回路问题研究

发布时间：2021-05-20 03:34

　　本论文主要研究2-边染色与2-弧染色重载费用欧拉回路问题。对2-边染色重载费用欧拉回路问题,具体描述如下:给定一个2-边染色欧拉图G=（V,E）,染色函数c:E→{1,2},重载费用函数r:{1,2} × {1,2}→R+0,其中r11 = r22 = 0,要寻找图G的一条欧拉回路PP,目标是使得欧拉回路P的重载费用r（P）达到最小,这里对欧拉回路P=（v0,e1,v1,...,em,V0）,欧拉回路P的重载费用规定为r（P）= rc（em）c（e1）+∑i=1m-1rc（ei）c（ei+1）°对2-弧染色重载费用欧拉回路问题,具体描述如下:给定一个2-弧染色欧拉图D =（V,A）,染色函数c:A →{1,2},重载费用函数r:{1,2} × {1,2}→R+0,其中r11 =0,要寻找图D的一条有向欧拉回路P,目标是使得有向欧拉回路P的重载费用r（P）达到最小,这里对有向欧拉回路P＝（v0,a1,v1,...,am,v0）,有向欧拉回路P的重载费用规定为r（P）＝rc（am）c（a1）+ ∑i=1m-1rc（ai）c（ai+1）°本论文主要得到两个结果:（1）当重载费用满足对称性时,... 

【文章来源】：云南大学云南省 211工程院校

【文章页数】：54 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 引言
    1.1 理论背景
    1.2 问题来源
    1.3 主要结果
    1.4 论文结构
第二章 预备知识
    2.1 图论基础知识
    2.2 基本问题及算法
第三章 重载费用欧拉回路问题及算法设计
    3.1 2E-RCETP问题及算法设计
    3.2 2A-RCETP问题及算法设计
    3.3 算例
结论
附录
参考文献
致谢



本文编号：3197005