Исследование задачи о ширине графа и ее обобщений

• Автор: Иванова, Светлана Диадоровна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Омск
• Количество страниц: 115 с. : ил.

1. Задача о ширине графа и ее обобщения

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

1.2. Приложения задач

1.3. Обзор результатов

1.4. Анализ Ь-структуры задачи о ширине графа

2. Полиномиально разрешимые случаи задачи о ширине графа

2.1. Вспомогательные утверждения

2.2. Прямоугольные решетки с угловыми выемками

2.3. Решетки с диагональными ребрами

3. Задача проектирования изделий сложной структуры

3.1. Математические модели

3.2. Генетический алгоритм для задачи проектирования изделий сложной структуры
3.3. Программное обеспечение
3.4. Результаты расчетов
Заключение

Диссертация посвящена исследованию известной задачи комбинаторной оптимизации - задачи о ширине графа и некоторых вариантов более общей задали проектирования изделий сложной структуры
Графы традиционно и успешно применяются для моделирования и анализа различных систем, имеющих сложную сетевую структуру, например, транспортных, информационно-вычислительных сетей, систем взаимоотношений в коллективе и т.д. [6,27].
Широко распространенной моделью реальных систем является структурная схема системы [26]. Она содержит информацию об элементах системы, о связях между элементами, а также о связях системы с окружающей средой. Абстрагируясь от содержательной стороны структурной схемы и выявляя ее математическую сущность, мы получаем схему, в которой содержится только информация о наличии элементов и связей между ними. Эта схема может быть представлена графом, вершины которого соответствуют элементам системы, а ребра - наличию связей между элементами. Таким образом, графы являются адекватными и наглядными математическими моделями многих реальных систем.
В задаче о ширине графа требуется пронумеровать вершины графа последовательными натуральными числами так, чтобы минимизировать максимальное значение модуля разности номеров смежных вершин. Она интересна как с теоретической, так и с практической точки зрения, поскольку имеет ряд важных приложений в различных областях, таких как решение систем линейных уравнений, проектирование интегральных схем и других объектов. Задача о ширине графа относится к задачам оптимальной нумерации. Общим для всех задач данного класса является вид допустимого решения - нумерация вершин, а отличаются они друг от друга лишь оптимизируемой функцией. Этот класс включает, в частности, задачу оптимального линейного упорядочения, которой посвящено значительное число работ [28,66,68,77], а также ряд других задач [3,30,60,78]. Обзор результатов по задачам нумерации можно най-

ти в [39,63].
Задачи оптимальной нумерации, в свою очередь, можно отнести к более широкому классу задач размещения графа па линии. Они изучаются в работах [9,10,19,79].
Приведем содержательную постановку задачи проектирования изделий сложной структуры. Предположим, что проектируемое изделие состоит из конечного числа образующих элементов. Структура изделия задается графом, вершины которого соответствуют возможным местам размещения элементов, а ребро между парой вершин указывает на взаимосвязь данных позиций. Элементы изделия характеризуются фиксированным числом параметров, которые могут быть выражены в числовых величинах. Если пара элементов оказывается размещенной во взаимосвязанных позициях, то могут накладываться ограничения на разность значений их параметров. Требуется расположить в вершинах графа элементы изделия (по одному в каждой вершине) таким образом, чтобы полученное размещение являлось оптимальным в смысле одного или нескольких критериев. Как правило, для каждого параметра известен ’’вес”, поэтому в качестве целевой функции может быть выбрана, например, линейная свертка критериев - взвешенная сумма максимальных разностей значений параметров взаимосвязанных элементов.
Эта задача имеет важное прикладное значение. Она возникает, в частности, при проектировании изделий из натурального меха или кожи. Заметим, что если число элементов равно числу вершин, и каждый элемент имеет единственный параметр, значение которого совпадает с номером элемента, мы получаем задачу о ширине графа.
Задача о ширине графа, а следовательно, и более общая задача проектирования, являются /УР-трудными [71], поэтому особый интерес представляет выделение полиномиально разрешимых частных случаев и разработка алгоритмов приближенного решения этих задач. Исследованиям в области алгоритмов для задачи о ширине графа посвящены работы [30,34,36,40,44,45,51-53,67,72,73,76]. В работах [29,32,33,41,54,56, 62,70,74,75] описываются некоторые классы графов, для которых задача о ширине может быть решена за полиномиальное время. Заметим, что задача о ширине остается ТУР-трудной даже для графов достаточно простой структуры - деревьев с максимальной степенью вершины 3 [45], а также для решеточных графов [38]. Граф называется решеточным, если множество его вершин - это подмножество множества £2, и две вершины смежны тогда и только тогда, когда евклидово расстояние между ними

В силу (2.14) для каждого £ < й справедливо следующее неравенство: (Р*(Уа2,з) < <Р*(Уаа{)- При £ = 1 С учетом (2.19) получаем 'ш(а2 + 1,1) < 002+1 = 4>*{у02,в) + щ < (р*{уаъ 1) + П = ц(а2 + 1,1) + П, а значит, ги(а,2 + 1,1) £ II(а,2 +1,1). Если же £ £ [2,5 — 1], то ю(а2 + 1,£) < 0а2-ы = ¥>*0ч,в)+П1 < тт(П2+1^) = ги(а,2 + 1,£) для любого £ £ [1,5 — 1]. Нетрудно доказать, что ги(а2 + 1,£) = 0а2+1 — I + 1, £ £ [1,5 - 1]. Таким образом, 1р*(Уа2+и) = 002+1 - £ + 1 для всех £ £ [1, 5 - 1].
12) Теперь покажем, что для любого £ £ [з,с£(а2 +1)] справедливо равенство (д(на2+1../;) = ги(а2 + 1,£) = /Д2+1 — £ + 1 (индукция по £). При £ - 5 утверждение верно. В самом деле, в силу доказанного в п. Н имеем
Ца2 + 1, з) - Д^+1 - з + 1 = (д(щ2„,) + щ -5 +
< <Р(Уа2,&) + п — Д(а 2 + !,«)+ Щ.
(последнее равенство вытекает из (2.19) с учетом того, что 5 < г](а2) = (1(а2 + 1) — 1). Следовательно, 10(0,2 + 1,5) £ Н(а2 + 1,5) и <д(цЦ2+11А.) = ги(а2 +1, 5) — 0а.2+1 — 5+1.
Предположим теперь, что утверждение п. 12) верно для некоторого £ £ [я, с1(а2 + 1) — 1] и покажем, что оно справедливо для £ + 1.
Рассмотрим сначала случай £ < с?(о2 + 1) — 1. По предположению индукции, (р(уа2+и) = ш(а2 + 1,£) = /Д,+1 “ £ + 1, и из (2-14) и (2.19) получаем
и)(а2 + 1, £ + 1) = Д,,,2+1 — £ = 1Р(^а2,в) + 'Лт ~ £ = ^(+++1) ~ 5 + 1 + '/'+
< <р{'иа2,ш) + П1 — +(а2 + 1; £ + 1)-
Значит, го(а2 + 1,£ + 1) £ С/(а2 +1, £ +1) и ^(г^+и+х) = го(а2 + !,£+!)
Д,2+1 - £.
При £ = с1(а2 +1) -1 имеем го(а2 +1, с/(а2 +1)) = /Зй.2+1 - с/(а2 +1) +1 = а%+1 £ и (о,2 + 1, (1{а2 + 1)), поэтому (д(щ2+м(а2+1)) = Я<2+1 - с1(а2 +1) +1.
Таким образом, ц>(уа2+и) = 0а2+1 - £ + 1 Для всех £ £ [5, <1(а2 +1)], т.е.
в случае 2 утверждение 2 справедливо.
Итак, при к — а2 + 1 утверждение 2 леммы 2.8 верно.
Предположение индукции. Пусть утверждение 2 леммы 2.8 справедливо для некоторого к £ [а2 + 1, /г — 2].
Шаг индукции. Докажем, что утверждение верно для к + 1.
По предположению индукции либо (р*(уц) = 0к — £ + 1 ДЛЯ всех £ £ [1Д(/с)], либо для к выполнено (2.15) (для любого £ £ [1, с£(&)]).