Введение
1 Корневой полуметрический многогранник 16
1.1 Разрезной многогранник 16
1.2 Определение корневого полуметрического многогранника 19
1.3 Некоторые основные свойства корневого полуметрического многогранника 20
1.4 Корневой полуметрический многогранник
как релаксация разрезного многогранника 23
1.5 Минорные характеристики матрицы корневого полуметрического многогранника 26
2 Релаксационный многогранник задачи 3-SAT 31
2.1 Задача 3-ВЫПОЛНИМОСТЬ и ее релаксационный многогранник 31
2.2 Фасеты и целочисленные вершины 38
2.3 Нецелочисленные вершины 40
2.4 Задача целочисленного программирования на Pm,n 52
2.5 Задача распознавания целочисленности 61
3 Последовательности релаксационных многогранников задач о разрезе и 3-SAT 70
3.1 Релаксации многогранника задачи 3-SAT 70
3.2 Релаксации разрезного многогранника 76
4 Гиперграфы специального вида и свойства вершин релаксаций разрезного многогранника 88
4.1 3-однородные смешанные гиперграфы 89
4.2 Гиперграфы точек многогранника Мп,з 93
4.3 Свойства точек релаксаций Мп^ и Мп$ 97
4.4 О классе неинвертируемых гиперграфов 113
Приложение 1 129
