Задачи аппроксимации графов и наследственных систем

• Автор: Навроцкая, Анна Александровна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Омск
• Количество страниц: 90 с. : ил.

Оглавление
Введение

1 Задачи аппроксимации графов

1.1 Постановки задач

1.2 Алгоритм локального улучшения для задачи аппроксимации неплотных графов

1.3 Алгоритм с константной оценкой точности для задачи аппроксимации двухкомпонентными графами

2 Задачи аппроксимации наследственных систем

2.1 Наследственные системы, матроиды и коматроиды

2.2 Задача аппроксимации линейной наследственной системы

2.3 Задачи аппроксимации наследственных систем матроида-

ми и коматроидами

3 Задача аппроксимации графами с компонентами связности ограниченного размера
3.1 Полиномиально разрешимые случаи
3.2 АР-трудные задачи
3.3 Приближенный алгоритм для задачи аппроксимации графами с компонентами мощности, не превышающей трех

Заключение
Список литературы
Публикации автора по теме диссертации

Введение
В диссертационной работе исследуются различные варианты задач аппроксимации графов и их обобщения — задачи аппроксимации наследственных систем.
Задачи аппроксимации графов наряду с задачами о минимальных разрезах в графах являются наиболее адекватными математическими моделями задач кластеризации и классификации взаимосвязанных объектов. Однако, в отличие от задачи о минимальном разрезе в задаче аппроксимации графа минимизируется не только число «лишних» связей между классами, но и число «недостающих» связей внутри классов.
Актуальность темы диссертации обусловлена тем, что задачи на наследственных системах являются математическими моделями множества сложных в вычислительном плане практически важных задач. Одна из таких задач — задача аппроксимации наследственных систем матрои-дами, являющаяся обобщением задачи аппроксимации графа. Эта задача относится к классу Л’Р-трудных, поэтому отыскание точного решения представляется весьма сложной проблемой. В то же время возрастает актуальность построения эффективных приближенных алгоритмов и получения гарантированых оценок точности таких алгоритмов.
Целью настоящей диссертации является исследование задач аппроксимации графов и задач аппроксимации наследственных систем, а также разработка и анализ приближенных алгоритмов решения этих задач.

Действительно, достаточно положить
(4 ап13 + п)(к — 1)
” п2 — 2 капР
Построение полиномиальной приближенной схемы для задачи Ак на неплотных графах можно разбить на два этапа. На первом этапе по заданному є из формулы є = (Аап+п) (к — 1 )/(и2 — 2капР — кп) определяем п = п£. На втором в зависимости от размерности конкретной задачи формулируем алгоритм Ає решения задачи Аи- Обозначим размерность данной задачи п.
Если п пе, то решаем задачу алгоритмом Ь и по теореме 1.2 получаем оценку
/(р) < і1 + >г) < +
При п < пе находим точное решение с помощью метода ветвей и границ или полного перебора, что гарантирует требуемую оценку. Для полного перебора в худшем случае потребуется порядка кп~1п2 операций. Но для любого фиксированного п£ существует число у такое, что п1 кп~1п2 при п < пЕ. Т. е. для заданного наперед £ существует полиномиальный алгоритм А£, находящий решение задачи Ак, значение целевой функции на котором отличается от оптимального значения целевой функции не более чем в 1 + є раз. Таким образом, полиномиальная приближенная схема построена.
Лемма 1.5. Оптимальные решения задач А и Аг на неплотных графах совпадают.
Доказательство. Рассмотрим неплотный граф Є = (V. Е). Пусть У = п. Такой граф содержит вершину и, степень которой меньше