Графы многогранников и сводимость задач комбинаторной оптимизации

Оглавление
Введение
1. Сложность в комбинаторной оптимизации
1.1. Некоторые сведения из теории сводимости задач.
1.2. Многогранники задач.
2. Конусное разбиение и аффинная сводимость
2.1. Конусное разбиение
2.2. Аффинная сводимость
3. Труднорешаемые задачи
3.1. Задача КЛИКА .
3.2. Задача 2ВЫПОЛНИМОСТЬ.
3.3. Задача РАЗРЕЗ.
3.4. Задача ТРЕХМЕРНОЕ СОЧЕТАНИЕ.
3.5. Задачи РЮКЗАК и РАЗБИЕНИЕ
3.6. Задача КОММИВОЯЖЕР
3.6.1. Задача гамильтонов контур.
3.6.2. Задача гамильтонов цикл.
3.6.3. Задача коммивояжера
с условием неравенство треугольника.
3.7. Задача ДЛИННЕЙШИЙ ПУТЬ
4. Полиномиально разрешимые задачи
4.1. Задача о кратчайшем пути .
4.2. Задачи о паросочетаниях.
Заключение
Список литературы