Введение
ГЛАВА I. Задача разрезания графа без ограничений 20
1.1. Постановка задачи. Основные сведения 20
1.2. Вычислительная сложность задачи 23
1.3. Исследование многогранника 26
1.4. Точный алгоритм решения задачи 32
ГЛАВА 2. Алгоритмы решения задач разрезания графа с ограничениями 44
2.1. Общие сведения. 44
2.2. Исследование эвристических алгоритмов 46
2.3. Точные методы решения задач разрезания графа с ограничениями 71
ГЛАВА 3. Константность и смежные вопросы теории задач выбора оптимального подграфа 88
3.1. Формулировка проблемы 88
3.2. Результаты для направленных графов 93
3.3. Результаты для симметричной задачи выбора опти мального подграфа 102
Литература 108
