Research On The Problem Of Eulerian Tour With Reload Costs

In this thesis,we considered Eulerian tour problem with reload costs in 2-edge coloring graphs and 2-arc coloring digraphs.The Eulerian tour problem with reload costs in 2-edge coloring graphs is described as follows:Given a 2-edge coloring Eulerian graph G =(V,E),a color function e:E?{1,2},reload cost function r:{1,2} x {1,2} ?B-0,r11 = r22 = 0,we are asked to find an Eulerian tour P in graphG.such that the objective is to minimize the reload cost r(P)of this Eulerian tour P,where the reload cost of P =(e1,e2,...,em,e1)is defined as r(P)= rc(em)c(e1)|?i=1 m-1rc(ei)c(ei+1)The Eulerian tour problem with reload costs in 2-arc coloring digraphs is described as follows:Given a 2-arc coloring Eulerian digraph D =(V,A),a color function c:A ? {1,2},reload cost function r:{1,2} x{1,2} ?R0,r11=r22=0,we are asked to find an Eulerian tour P in digraph D,such that the objective is to minimize the reload cost r(P)of the Eulerian tour P,where the reload cost of P=(a1,a2,...,am,a1)is defined as(P)?rc(am)c(a1)+?i=1 m-1rc(ai)c(ai|1)We obtain two results as follows:(1)For the Eulerian tour problem with symmetric reload costs in 2-edge coloring graphs,we design a polynomial-time algorithm to solve it,the complexity in our algorithm is O(n3),where n is the order of graph G.(2)For the Eulerian tour problem with symmetric reload costs in 2-arc coloring digraphs,we design a polynomial-time algorithm to solve it,the complexity in our algorithm is O(n3),where n is the order of digraph D.