In this paper the problems of construction and description of cones
and polyhedra of finite quasi-metrics are considered. These objects
are asymmetrical analogs of classical finite metrics.
The introduction presents the historical background and examples of
applications of metrics and quasi-metrics. In particular, the
questions connected with maximum cut problem are represented.
In the first section definitions of finite metrics and semi-metrics are
given, and also their major special cases are considered: cuts,
muluticuts and hypersemimetrics. Cones and polyhedrons of the
specified objects are constructed; their properties are
investigated. Connections of the cut cone with metric $l_1$-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 defining the corresponding polyhedron.
In the second section finite quasi-metrics and quasi-semimetrics are
considered. They are asymmetrical analogs of the usual finite
metrics and semimetrics. Definition 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
$l_1$-space are considered. The special attention is paid to
symmetries 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 defining the corresponding polyhedron. Different
approaches to creation of a cone and a polyhedron of asymmetrical
hypersemimetrics 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,
weighed quasimetrics and partial metrics for $3, 4, 5$ and $ 6$
points are considered. In fact, the dimension of an object, the
number of its extreme rays (vertices) and their orbits, the number
of its facets and their orbits, the diameters of the skeleton and
the the ridge graph of the constructed cones and polyhedrons are
specified.
Bibliography: 15 titles.
