本论文主要研究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)当重载费用满足对称性时,对2-边染色重载费用欧拉回路问题,设计出一个多项式时间最优算法求解,算法复杂性为O(nn3),其中n为无向图中顶点数目。(2)当重载费用满足对称性时,对2-弧染色重载费用欧拉回路问题,设计出一个多项式时间最优算法求解,算法复杂性为O(n3),其中n为有向图中顶点数目。