乡村投递员问题的多面体

THE POLYHEDRON OF THE RURAL POSTMAN PROBLEM

设 G=(V,E)是以 V 为顶点集,E 为边集合的连通无向图.对任意的 E′(?)E,以G[E′]记 G 的由 E′中的边所组成的子图,称之为边集 E′导出的子图.称边序列 w=〈(i_0,i_1,),(i_1,i_2),…,(i_(k-1),i_k)〉为连接 i_0和 i_k 的路,其中 i_j∈V,(i_j,i_(j+1)∈E,0≤j≤k-1.如果 i_0=i_k,则称 w 为一个闭路.如果 w 中 i_s(?)i_t,对任意0≤s,t≤k,

The general routing problem proposed by C.S.Orloff in 1974 is,given a graphG=(V,E) with V_0(?)V,E_0(?)E and edge cost c∶E→R_+,to find a clised walk ofminimum cost which contains every vertex of V_0 and every edge of E_0.When V_0=φ,the problem is the Rural Postman Problem(RPP).When E_0=E,the RPP isthe familiar Chinese Postman Problem(CPP).It is proved that the CPP can be so^(?)lved in polynomial time while the RPP is NP-complete.The combinatorial polyhedral methods are successfully used in NP-complete pro-blems in recent years.In this paper,the polyhedron relative to RPP is discussed andseveral kinds of facets of this polyhedron are described.