POLYHEDRALSTRUCTURESASSOCIATED WITHQUASI-METRICS
In this paper the problems of construction and description of cones and polyhedraof ?nitequasi-metrics areconsidered.Theseobjectsareasymmetrical analogs of classical ?nite metrics. Theintroductionpresents thehistoricalbackgroundand examples of applications of metrics and quasi-metrics. In particular, the questions connected with maximum cut problem are represented. In the ?rst section de?nitions of ?nite metrics and semi-metrics are given, and also their major special cases are considered: cuts, muluticuts and hypersemimetrics. Cones and polyhedrons of the speci?ed objects are constructed; their properties are investigated. Connections of the cut cone with metric l1-spaces are indicated. The special attention is paid to symmetries of the constructed cones which consist of permutations and so-called switchings; transformation of a switching serves the basis for a choice of the inequalities de?ning the corresponding polyhedron. In the second section ?nite quasi-metrics and quasi-semimetrics are considered. They are asymmetrical analogs of the usual ?nite metrics and semimetrics. De?nition of the oriented cuts and oriented multicuts are given: they are the most important special cases of the quasi-semimetrics. Concept of weightable quasi-metrics and related to them partial metrics is introduced. Cones and polyhedrons of these objects are constructed; their properties are investigated. Connections of the oriented cut cone with quasi-metric l1-space are considered.The special attentionispaid tosymmetries of the constructed cones, which consist of permutations and oriented switchings; as well as in symmetric case, transformation of the oriented switching serves the basis for a choice of the inequalities de?ning the corresponding polyhedron. Di?erent approaches to creation of a cone and apolyhedron of asymmetricalhypersemimetrics are considered. In the last section results of the calculations devoted to cones and to polyhedrons of quasi-semimetrics, the oriented cuts, the oriented multicuts, weighedquasimetrics andpartial metricsfor 3, 4, 5 and 6points are considered. Infact,thedimension of an object,the number ofits extreme rays(vertices) and theirorbits,thenumber ofitsfacetsand theirorbits,thediameters of the skeletonand thetheridgegraph of theconstructed conesandpolyhedrons are speci?ed.