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. Cuts, hypermetrics 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
generalized finite semimetrics .......................... 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 weightable
quasi-metrics ............................................... 83
6.1 Preliminaries .......................................... 83
6.2 Definitions ............................................ 83
6.3 Examples ............................................... 87
III Cuts, hypermetrics and their generalizations .............. 93
7 Cuts and their generalizations .............................. 95
7.1 Preliminaries .......................................... 95
7.2 Classical non-oriented case ............................ 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: ш-hemimetrics ....................... 157
11.1 Preliminaries ......................................... 157
11.2 Cones and polytopes of m-hemimetrics 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
|
