Table of Contents
Introduction ix
I Preliminaries 1
1 Short preview of the book 3
1.1 Outline of Part I. Preliminaries 4
1.2 Outline of Part II. Main notions and examples 4
1.3 Outline of Part III. Outs, hyperimetries and their generalizations 6
1.4 Outline of Part IV. Cones and polytopes of generalized finite metrics 6
1.5 Outline of Part V. Important cases of polyhedra of generalised finite semi-metrics 7
2 Main definitions 9
2.1 Graphs 9
2.2 Vector spaces 16
2.3 Matrices 19
2.4 Cones and polytopes 20
II Main notions and examples 29
3 Non-oriented case: metrics 31
3.1 Preliminaries 31
3.2 Definitions 32
3.3 Examples 33
4 Oriented case: quasi-metrics 51
4.1 Preliminaries 51
4.2 Definitions 51
4.3 Examples 53
5 Multidimensional case: m-metrics 61
5.1 Preliminaries 61
5.2 Definitions 61
5.3 Examples 65
6 Important special case: partial metrics and weight able quasi-metrics 83
6.1 Preliminaries 83
6.2 Definitions 83
6.3 Examples 87
III Cuts, hyper metrics and their generalizations 93
7 Cuts and their generalizations 95
7.1 Preliminaries 95
7.2 Classical non-oriented ease 95
7.3 Oriented case 99
7.4 Multidimensional case 102
7.5 Important special cases of cut-related constructions 104
8 Hypermetrics and their generalizations 107
8.1 Preliminaries 107
8.2 Hypermetric and negative type inequalities 107
8.3 Hypermetrics and distances of negative type 110
8.4 Some generalizations of hypermetrics 112
IV Cones and polytopes of generalized finite semimetrics 117
9 Non-oriented case: semimetrics and cuts 119
9.1 Preliminaries 119
9.2 Cones and polytopes of semimetrics and cuts 120
9.3 Small cones and polytopes of semimetrics and cuts 124
9.4 Theorems and conjectures for general case 127
10 Oriented case: quasi-semimetrics and oriented cuts 129
10.1 Preliminaries 129
10.2 Cones and polytopes of quasi-semimetrics and oriented multicuts 130
10.3 Small cones and polytopes of quasi-semimetrics and oriented multicuts 135
10.4 Theorems and conjectures for general case 149
10.5 Other constructions of quasi-semimetric polyhedra 156
11 Multidimensional case: m-hemimetrics 157
11.1 Preliminaries 157
11.2 Cones and polytopes of m-hemiriietrics and (m. s)-supermetrics 158
11.3 Small cones of m-hemimetrics and (m, s)-supermetrics 162
11.4 Some special cases of parameters 178
11.5 Theorems and conjectures for general case 182
V Important cases of polyhedra of generalized finite semimetrics 187
12 Cones of partial semimetrics and weightable quasi-semimetrics 189
12.1 Preliminaries 189
12.2 Polyhedra of partial semimetrics and weightable quasi-semimetrics 191
12.3 Maps P, Q and connections between considered polyhedra 195
12.4 Small polyhedra of partial semimetrics and weightable quasi-semimetrics 198
12.5 Theorems and conjectures for general case 205
13 Cones of hypermetrics 219
13.1 Preliminaries 219
13.2 Non-oriented case 221
13.3 Partial and weighted hypermetric cones 234
13.4 Quasi-hypermetric cones 237
14 Cuts over general graphs 243
14.1 Preliminaries 243
14.2 Metric and cut polyhedra over graphs 244
14.3 Cut polytopes over some graphs 249
14.4 Some general results about metric and cut polyhedra over graphs 255
15 Connections between generalized metrics polyhedra 261
15.1 Preliminaries 261
15.2 Decomposition of real vector spaces 262
15.3 Construction of projections of cones on n + 1 points 269
15.4 Projections of METn+1 and CUTn+1 277
15.5 Cases 3 < n 6 284
Appendixes 287
Bibliography 295
