Исследование и разработка алгоритмов решения некоторых комбинаторных задач типа разрезания графа

• Автор: Гильбурд, Михаил Марксович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1985
• Место защиты: Киев
• Количество страниц: 117 c. : ил

ГЛАВА I. ЗАДАЧА РАЗРЕЗАНИЯ ГРАФА БЕЗ ОГРАНИЧЕНИЙ

§ І.І. Постановка задачи. Основные сведения

§ 1.2. Вычислительная сложность задачи

§ 1.3. Исследование многогранника

§ 1.4. Точный алгоритм решения задачи

ГЛАВА 2. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ РАЗРЕЗАНИЯ ГРАФА С

ОГРАНИЧЕНИЯМИ

§ 2.1. Общие сведения

§ 2.2. Исследование эвристических алгоритмов

§ 2.3. Точные методы- решения задач разрезания графа с

ограничениями

ГЛАВА 3. КОНСТАНТНОСТЬ И СМЕЖНЫЕ ВОПРОСЫ ТЕОРИЙ ЗАДАЧ
ВЫБОРА ОПТИМАЛЬНОГО ПОДГРАФА
§ 3.1. Форцулировка проблемы
§ 3.2. Результаты для направленных графов
§ 3.3. Результаты для симметричной задачи выбора оптимального подграфа
ЗАКЛШЕНИЕ
ЛИТЕРАТУРА

При решении многих прикладных проблем, связанных с техническим проектированием, обработкой и классификацией данных, возникают задачи следующего вида: задано некоторое множество взаимосвязанных объектов, известны показатели их попарной взаимосвязи /сходства, близости/; требуется разбить все множество объектов на несколько непересекающихся подмножеств так, чтобы минимизировать общую величину связей между различными подмножествами либо максимизировать суммарную связь объектов внутри подмножеств. Приведем примеры подобных задач:
I/ Задача сегментации программы /27, 38, 717*. задано множество программных единиц /модулей, секций, блоков/, составляющих некую программу, известны частоты совместного или последовательного выполнения каждой пары программных единиц. Требуется найти разбиение программы на сегменты /наборы программных единиц/ обеспечивающее минимальную суммарную частоту межсегментных обращений; при этом каждый из сформированных сегментов должен вмещаться в оперативную память ЭВМ.
но множество функциональных элементов, составляющих радиоэлектронную схему, для каждой пары элементов известно количество схемных соединений между ними. Требуется разбить данную схему на ограниченное число плат, так, чтобы общее число соединений между различными платами было минимальным; при этом необходимо учитывать ограничения по размерам плат.
3/ Задачи классификации и кластерного анализа /з, 19, 207, ЗтУ : задано множество классифицируемых объектов /наблюдений, признаков, элементов организационных, природных или технических систем/, известны показатели попарных связей между объектами
2/ Задача компоновки радиоэлектронных схем

/например, коэффициенты корреляции/. Требуется найти разбиение заданного множества на "обозримое" число классов, максимизирующее суммарную величину связей внутри классов. В том случае, когда классифицируемым объектам соответствуют точки в некотором признаковом пространстве, классификация может основываться на значениях попарных расстояний между точками; при этом минимизируется сумма внутриклассовых расстояний. /В связи с тем, что требования к искомой классификации могут существенно изменяться в зависимости от специфики классифицируемых объектов, при формулировке задач кластерного анализа в литературе /з, 20 , 54] используются, наряду с упомянутыми и другие критерии, не характерные для традиционных постановок задач типа разрезания графа и поэтому не рассматриваемые в данной работе/.
Задачи, аналогичные перечисленным, возникают также при проектировании организационных структур /4, 4в] и сети ВЦ коллективного пользования Ы , при обработке экспертных данных [4о] и т.п. В математической постановке все эти задачи формулируются как частные случаи следующей общей задачи:
ЗАДАЧА РАЗРЕЗАНИЯ ГРАФА /ЗРГ/Ч Дан взвешенный граф О с множеством вершин и матрицей весов ребер
Iл/= (иф . Веса ребер могут быть положительными, отрицательными, равными - 00 ; при отсутствии ребра (в графе полагаем Ыу. Каждое разбиение р множества А/ на ] пересекающиеся подмножества М, Мя , М-(р) характеризуется
связей:
пн, у.рнгх
отражающим степень автономности подмножеств в разбиении.
функционалом суммы внутренних связей:
I) В иностранной литературе употребляется термин "задача разбиения графа "(Graph partit со/71ло pro Stem).

отделимости в среднем.
Следующее утверждение показывает, что свойство отделимости в среднем эквивалентно некоторой нижней оценке для суммы внутренних связей. /Здесь и далее предполагается, что в VJ нет элементов, равных - со /.
Утверждение 2.1. Разбиение р отделимо в среднем тогда и только тогда, когда
If/t,W,p) > S(W) /2.6
Доказательство. Запишем неравенство /2.5/ в виде
К/V, МгШгШМРШ,,,
Подставив сюда /Г//1/ IV,pi OIWJ 1 (/V,W,p)и учитывая,
что ju(p)+ ^(р)-/?!/?-/)/Р, получим:
jПА/, V/>S(V/)'ju!p)
что эквивалентно /2.6/. Все применяемые преобразования - тождественные, поэтому» в свою очередь, из /2.6/ вытекает /2.5/. Утверждение доказано.
Замечание. Вычитая /2.6/ из тождества 3(W)~ 3(V/) , получим следующее эквивалентное неравенство:
Em/2.v
которое также используется в дальнейшем.
Заметим, что оценка /2.6/ достижима как в классе отделишх в среднем разбиений, так и в более узком подклассе отделимых разбиений. В самом деле, любое разбиение р> полного графа Кп с единичными весами ребер отделимо с порогом oi=i ♦ при этом:
КМ V/, р) "p/p) ~ju(p)' swH
Таким образом, для подкласса отделимых разбиений оценку /2.6/ нельзя улучшить.