混合图上的投递员问题的近似算法

1.引言投递员问题是一类很广泛的应用问题,实际生活中的收购废品、清扫马路等都可以化成求解混合图上的投递员问题。考虑一个混合图G=(V,E,A),其中边集E和弧集A分别代表双向和单行马路或街道,顶点集V代表这些马路的交点。中国投递员问题是要求一条从某点出发经过各条马路至少一次(如果是单向马路,应按指定方向走),并且费用最少的路线。最初的投递员问题是考虑无向图上的情况,即是所要经过的街道都是双向的。无向图上的投递员问题是多项式     

On Alternating Sequences Relative to a c-Matching of a Hypergraph

In[1], C.Berge has modified Theorem 1 of [2]to a theorem which is a charac-terization of maximum c-Matchings in a hypergraph (see[1], P.416, Theorem 2),and at the same time can be considered as a generalization of Berge's theorem on     

乡村投递员问题的多面体

设 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,     

图的邻域复形的同调群的不变性

本文研究了图的邻域复形同调群的不变性质。设G是一个简单连通图,x是G的一个顶点,以G/x表示G中剔去点v及其关联边而得到的图,给出了G和G/x的邻域复形的同阶同调群同构的充要条件。