engleski

Generalized cut and metric polytopes of graphs and simplicial complexes

The metric polytope METP(Kn) of the complete graph on n nodes is defined by the triangle inequalities x(i, j)≤x(i, k)+x(k, j) and x(i, j)+x(j, k)+x(k, i)≤2 for all triples i, j, k of {; ; ; 1, …, n}; ; ; . The cut polytope CUTP(Kn) is the convex hull of the {; ; ; 0, 1}; ; ; vectors of METP(Kn). For a graph G on n vertices the metric polytope METP(G) and cut polytope CUTP(G) are the projections of METP(Kn) and CUTP(Kn) on the edge set of G. The facets of the cut polytopes are of special importance in optimization and are studied here in some detail for many simple graphs. Then we define variants QMETP(G) for quasi-metrics, i.e. not necessarily symmetric distances and we give an explicit description by inequalities. Finally we generalize distances to m-dimensional area between m+1 points and this defines an hemimetric. In that setting the generalization of the notion of graph is the notion of m-dimensional simplicial complex K for which we define a cone of hemimetric HMET(K).

Metric polytope ; hemimetrics ; oriented metrics

nije evidentirano