Содержание к диссертации
Введение
Глава 1. Применение графов в математическом моде лировании систем управления 27
1.1. Основные понятия и определения 28
1.2. Маршруты в графах 33
1.3. Разложения графов на цепи 38
1.4. Алгоритмы построения эйлеровых циклов без огра
ничений на порядок обхода ребер 43
Глава 2. Маршруты с локальными ограничениями 53
2.1. Алгоритм построения допустимой цепи 54
2.2. Алгоритм построения допустимой эйлеровой цепи 64
2.3. Покрытие графа допустимыми цепями 76
Глава 3. Маршруты с упорядоченным охватыванием 81
3.1. Представление плоского графа 84
3.2. Существование эйлеровых ОЕ-циклов 86
3.3. Рекурсивный алгоритм построения эйлеровых ОЕ циклов 89
3.4. Результативность рекурсивного алгоритма 93
3.5. Нерекурсивный алгоритм построения эйлерова
ОЕ -цикла 96
3.6. Эффективный алгоритм построения ОЕ -маршрута в произвольном связном плоском графе 111
3.6.1. ОЕ -маршрут китайского почтальона 111
3.6.2. Задача построения покрытия
с упорядоченным охватыванием 120
3.7. Оптимальное покрытие плоского графа последовательностью ОЕ -цепей 130
3.8. Построение Oi -покрытия
для многосвязного графа 136
Глава 4. AOi -маршруты 144
4.1. О существовании системы переходов, допускающей АОЕ-цеиь 147
4.2. АОЕ-цеїт для 4-регулярных графов 148
4.2.1. Пример 152
4.3. О числе эйлеровых ОЕ -цепей для заданной систе мы переходов 154
4.3.1. Число ОЕ -цепей для системы переходов, соответствующей А-цепи 157
4.3.2. Число ОЕ -цепей для непересекающейся системы переходов 160
4.3.3. Необходимое условие существования ОЕ -цепи для фиксированной системы переходов 162
4.3.4. Некоторые замечания и критерии 169
Глава 5. Программное обеспечение для построения ОЕ-цепей и Oi -покрытий 172
5.1. Программное обеспечение задачи построения эйлерова ОЕ -цикла 173
5.1.1. Рекурсивный алгоритм построения эйлерова ОЕ -цикла 173
5.1.2. ОЕ -маршрут китайского почтальона 178
5.1.3. Эффективный алгоритм построения покрытия 181
5.2. Программное обеспечение для построения ОЕ -покрытия несвязного графа 183
5.3. Алгоритм тестирования. Критерий соответствия цепи условию упорядоченного охватывания 186
5.4. Программа для построения АОЕ-цеїт 189
Глава 6. О возможных практических приложениях решаемой задачи 192
6.1. Задача прямоугольного раскроя и ОЕ -покрытия 198
6.1.1. Алгоритмы для кодирования раскройного плана 200
6.1.2. Выбор оптимальной укладки деталей 206
Выводы и основные результаты 210
Литература
- Разложения графов на цепи
- Покрытие графа допустимыми цепями
- Оптимальное покрытие плоского графа последовательностью ОЕ -цепей
- Число ОЕ -цепей для непересекающейся системы переходов
Разложения графов на цепи
В дальнейшем будем использовать терминологию, введенную в монографиях [48], [115] и [4]. Для цельности изложения приведем понятия, используемые в данной диссертационной работе.
Обыкновенным графом G = (V, Е) будем называть упорядоченную пару множеств: конечное непустое V, элементы которого называются вершинами графа G1 и подмножество Е1 элементы ко торого называются ребрами графа. Ребро, соединяющее вершины х и у (или, что то же самое, у и х), будем обозначать ху. Также говорят, что ребро ху инцидентно каждой из этих вершин (и наоборот, они обе инцидентны данному ребру). Если не требуется напоминать, какие именно вершины соединяет ребро, то его можно обозначать и одной буквой (е, и и др.). Вершины ж, у Є V смежны, если ребро ху Є Е, и несмежны, если ху ф Е.
Часть G = (Vі, Е ) называется подграфом графа G, если Е = {ху Є Е \х,у Є V }] иными словами, при образовании подграфа G из графа G удаляются все вершины множества V \ V и только те ребра, которые инцидентны хотя бы одной удаляемой вершине. Таким образом, подграф данного графа G однозначно определяется заданием непустого подмножества вершин V или, что равносильно, заданием строгого подмножества W = V\V С V тех вершин, которые надо удалить; в последнем случае будем кратко писать G = G\ W, а если V = {у} (одновершинное множество), то даже G = G \ {у}. В частности, при Vі = V имеем G = 3\0 = G.
Граф называется связным, если множество его вершин невозможно так разбить на попарно непересекающиеся непустые подмножества, чтобы никакие две вершины из разных подмножеств не были бы смежны. Несвязный же граф однозначно разбивается указанным способом на связные подграфы, называемые компонентами связности. В дальнейшем, если не оговорено противное, будем рассматривать только связные графы. Обобщением понятия обыкновенного графа является понятие мультиграфа. Под мультиграфом будем понимать упорядоченную тройку G = (V,E,ip), где V ф 0 множество вершин, Е - множество ребер, оба конечные, а (р : Е — V2 - отображение, относящее каждому ребру є Є Е неупорядоченную пару ср(е) = ху вершин ж, у Є V, называемых концами этого ребра.
Возможной формой представления графов является матрица инцидентности «вершины/ребра». Строкам данной матрицы соответствуют вершины графа О, а столбцам - ребра. Если ребро е = { 1 2}, то на пересечении столбца е и строк v\ и v i будут стоять единицы. Остальные элементы столбца е - нулевые. Пространственная сложность такого представления равнаО(У \Е\).
Очевидно, что для представления графа можно организовать список ребер, с указанием для каждого ребра пары инцидентных вершин. Пространственная сложность такого представления будет 0(.Е log21 V I). Логарифм в данном выражении появляется в связи с необходимостью нумерации вершин.
Для обозначения мультиграфа G(V, Е, ср) будем использовать обозначение G = (V, Е)1 если это не приводит к двусмысленности.
Топологическим графом называют такой граф G = (У,.Е, ), вершинами которого служат некоторые выделенные точки трехмерного евклидова пространства, а ребрами - жордановы дуги, соединяющие эти точки; у звена обе инцидентные вершины (концевые точки) различны, у петли совпадают. Требуется еще, чтобы никакая внутренняя (неконцевая) точка ребра не совпадала ни с одной вершиной графа и ни с одной точкой другого ребра; всякое нарушение этого требования будем кратко называть пересечением,. Таким образом, изображение абстрактного графа на рисунке само является топологическим графом, изоморфным исходному лишь при условии, что рисунок не содержит пересечений.
Всякий абстрактный граф допускает топологическое представление, т. е. в пространстве R существует изоморфный ему топологический граф.
Как в теории, так и в приложениях особо важную роль играют те топологические свойства графа, которые связаны с возможностью или невозможностью поместить его в плоскость. Известно, что евклидова плоскость гомеоморфна сфере, из которой удалена одна точка; соответствующее отображение можно осуществить, например, с помощью стереографического проектирования. Этим же отображением топологический граф на сфере переводится в изоморфный топологический граф на плоскости и наоборот. Граф, допускающий такие топологические представления, называется пла-нарным, а его конкретное представление в плоскости - плоским графом.
Покрытие графа допустимыми цепями
Первоначальное паросочетание M(Gf) выделено на рисунке жирными линиями. Для данного паросочетания чередующейся увеличивающей последовательностью ребер является { ід 5,2І, { 5,2 2} И,2 5,2}, {W5,2W5,1 , {5,1 і}, K,1 5,l}, W }, { 6,2 6,2}3 { 6,2 6,2}, { 6,2 6,l}, { 6,1 д}, { бД бд}, { 6,1 7,2 . Ребра этой последовательности, не вошедшие в первоначальное паросочетание, изображены пунктирной линией. Эти ребра образуют множество {{ 1,1 5,2} , K,2W5,2} , { 5,l l} , { 5,1 6,2} , { 6,1 6д} , { 6,1 7,2 } Все ребра данного множества, принадлежащие графу С, т.е. {ui }, {V VQ}} {VQVT} образуют Х -совместимый путь из вершины V\ в вершину Vj. С помощью алгоритма Тс-СОВМЕСТИМЫЙ ПУТЬ возможно построение только простой цепи между двумя различными вершинами (т.е. цепи, в которых любая вершина встречается ровно один раз).
Однако в общем случае непосредственное применение данного алгоритма не позволяет решить задачу нахождения Х -совместимого маршрута, содержащего максимальное число ребер. Действительно, паросочетание максимальной мощности в графе G не может содержать пары ребер, образующих запрещенный переход, т.к. они инцидентны одной общей вершине графа G . В то же время, в общем случае может существовать Х -совместимый маршрут, содержащий такую пару ребер. При разработке алгоритма построения допустимой цепи возник вопрос, можно ли заменить графы переходов некоторой ориентацией исходного графа. В качестве примера рассмотрим граф, представленный на рис. 2.4(a). Пусть для этого графа заданы следующие допустимые переходы {{ 2, v\}, { 1, 3}}? {{ з, vi}, {vuV4}}, №1, М { 4, v2}}, {{vh г;4}, {vh v3}}, {{ 4, з}? { з? і}}3 {{ з? }? { 2? і}}- Попытаемся представить их в виде дуг орграфа, как показано на рис. 2.4(6).
Заметим, что в построенном орграфе присутствуют и переходы, которые не были заданы системой допустимых переходов (например, {{ 2? і}? { і, 4І})- Для иллюстрации работы предложенного алгоритма построим вспомогательный граф в соответствии с шагом 3 (рис. 2.5(a)) [23,84,96].
В частности, вершину v\ нам потребовалось расщепить на две, чтобы показать возможные переходы в ней, как показано на рис. 2.5(6). Таким образом, представление в виде орграфа не гарантирует существования возможного перехода.
Этот пример показывает, что для нахождения алгоритма построения допустимой цепи невозможно представить систему переходов в виде дуг орграфа, т.е. для каждой вершины необходимо строить соответствующий граф переходов [96].
На рис.2.6 показаны элементы экранного интерфейса программной реализации [28, 76] данного алгоритма. Жирной линией отмечена найденная цепь между вершинами 1 и 4, удовлетворяющая системе разрешенных переходов, задаваемой в отдельном окне FORM_TRANSP [95]. Входные данные программы представлены в виде списка смежности vector list pair string, int Graph;
Данные заданы в виде вектора вершин, каждый элемент вектора это список пар. Первая пара в каждом списке является описанием данного списка смежности: первый элемент пары - номер вершины, второй элемент - ее степень. Остальные пары представляют собой номера смежных вершин и номер соответствующей компоненты разбиения ребра [37].
Заметим, что в работе [35] открытым остался вопрос распознавания многодольности графов TG(V), а также проблема построения допустимого маршрута или множества маршрутов, покрывающих Г ЯЯ№ Вершина все ребра исходного графа. В общем случае непосредственное применение данного алгоритма не позволяет решить задачу нахождения Х -совместимого маршрута, содержащего максимальное число ребер. Действительно, паросочетание максимальной мощности в графе G не может содержать пары ребер, образующих запрещенный переход, т.к. они инцидентны одной общей вершине графа G . В то же время, в общем случае может существовать TQ-совместимый маршрут, содержащий такую пару ребер.
Оптимальное покрытие плоского графа последовательностью ОЕ -цепей
В предыдущем разделе был рассмотрен рекурсивный алгоритм построения ОЕ -цикла в плоском эйлеровом графе. В работе [13] предложен еще один эффективный алгоритм построения ОЕ -циклов в плоских эйлеровых графах OECover (алг. 5), имеющий вычислительную сложность О (\Е\ log2 V).
В теле алгоритма кроме указанных выше функций Vk(), (), /fc(), к = 1, 2 формируются дополнительные функции: 1. Stack : У — i?: Stack(v) - указатель на очередь г;-списка М2-помеченных ребер; 2. markfcQ : E — E и prevfc() : E —t E, k = 1,2 для организации двусвязных списков с целью обеспечения операций вставки/удаления за время 0(1).
Кроме того, функция markiQ используется для представления результата выполнения алгоритма.
Алгоритм OECycle (алг. 5) состоит из последовательного выполнения процедур Initiate, Order, и FormChainO, соответствующих трем этапам: «Инициализация», «Упорядочение» и «Форм-рование». В алгоритме также используется описанная ранее процедура REPLACE() (см. раздел 3.3, алг.2).
Как уже отмечалось ранее, данная прцедура переопределяет введенные функции Vk(e), /&(е), Л(е), к = 1,2 таким образом, чтобы движение по ребру є Є Е в построенном алгоритмом цикле происходило бы от вершины (е) к вершине V\(e).
Этап «Инициализация». В теле процедуры Initiate (алг. 6) присваиваются начальные значения а также определяется ребро ео Є Е, принадлежащее границе внешней грани /Q. Функции на ребре ео переопределяются таким образом, чтобы /і(ео) = /о, т.е. чтобы ребро Zi(eo) принадлежало грани Algorithm 6 Процедура Initiate це внешней грани. Также в теле данной функции инициализируется очередь М1-помеченных ребер (рис.3.4), как состоящая из единственного ребра ео, переменные first и last используются для указания соответственно первого и последнего элементов очереди. ппагМе,) mark,[е. ) markjej
Организация очереди М1-помеченных ребер Переменная пе используется для определения следующего кандидата для включения в список М1-помеченных ребер. Переменная VQ используется для запоминания вершины, принадлежащей границе внешней грани, а переменная v - как текущая вершина для задания ориентации ребра, определяемого пе.
Этап «Упорядочение». Процедура Order (Упорядочение) представлена в алг.7. Функциональное назначение процедуры
Процедура Order использует переменную к как счетчик стадий и функцию rank() : Е — N, указывающую номер стадии, на которой ребро ставится в очередь М1-помеченных ребер. Содержа-ельный смысл функции rank заключается в том, что она определяет ранг ребра е (определение ранга ребра приведено в разделе 3.3). Заметим, что ранг любого ребра плоского графа может быть определен за время 0(.Е) с помощью процедуры Order.
Данная процедура выполняется следующим образом. На первой стадии в очередь М1-помеченных ребер вводятся все ребра є Є Е) ограничивающие внешнюю грань /о, а их ориентация задается так, чтобы /і(е) = /о. На стадии к + 1 каждое ребро е G Е, попавшее в очередь М1-помеченных на стадии /с, переводится в состояние М2-помеченного и помещается в списки вершин vj(e)J I = 1,2 (см. рис. 3.5), а в очередь М1-помеченных включаются все непомеченные ребра, ограничивающие грань, общую с ребром е.
Число ОЕ -цепей для непересекающейся системы переходов
Алгоритм OECover определяет дополнительные ребра, соединяющие конец текущей и начало последующей цепей. Эти ребра образуют множество М, существование которого утверждается в теореме 11. Они представляют собой некоторое паросочетание на множестве Vodd- Приведем доказательство более сильного результата, анонсированного в [68]: построение последовательностей цепей с упорядоченным охватыванием с любым множеством М, образующим паросочетание на множестве V0dd [18,77,79].
Оптимальное покрытие плоского графа последовательностью ОЕ-цеией Теорема существования минимального по мощности эйлерова покрытия плоского графа G и алгоритм его построения приведены в [?, 12,19].
Рассмотрим алгоритм построения оптимального по длине дополнительных построений покрытия произвольного плоского связного графа без висячих вершин последовательностью цепей с упорядоченным охватыванием, а также доказательство его результативности [79,89].
Теорема 12. Пусть G = (V,E) - плоский связный граф на S, не имеющий висячих вершин. Для любого множества М, являющегося паросочетанием на множестве V0dd графа G, и такого, что М : (М П S)\V = 0, сугцествует эйлеров цикл С = v\e\v Le L...env\, п = \Е\ + \М\, для любой начальной части которого Сі = v\e\V2e2---Vi, I \Е\ + \М\, выполнено условие Ы(Сг) Г\ Е = $ .
Доказательство этой теоремы также конструктивно и состоит в доказательстве результативности следующего алгоритма. Алгоритм M-Cover Входные данные: плоский граф G1 представленный списком ребер с заданными на них функциями г (е), (е), /fc(e), к = 1,2; паросочетание М на множестве вершин нечетной степени V0 id Выходные данные: Cj, j = 1,..., У0 /2, - покрытие графа G ОЕ -цепями. Шаг 1. Выполнить процедуры «Инициализация» и «Упорядочение» как в алгоритме, приведенном в [98]. В результате для \/v Є V будет определено значение rank(i ), численно равное ее уровню вложенности. Положить j = 1. Объявить вершину VQ Є /О Текущей, ПОЛОЖИТЬ VQ = VQ. 131 Шаг 2. Выполнять построение цепи Cj с помощью процедуры «Формирование» алгоритма [98] до тех пор, пока вершина v2 Є V0dd не станет текущей. Если вершина v2 является тупиковой, то 3( 2, 3) і перейти на шаг 4. Если v2 является транзитной -перейти на шаг 3. Шаг 3. Если гапк(г;з) гапк ), то перейти на шаг 2 (продолжить построение цепи Cj из текущей вершины). Шаг 4. Закончить построение текущей цепи: v\ = v2l j = j +l, Vodd = Vodd\{v2, v3}, M = M\{{v2l v3)} принять vJ0 = v3 за текущую вершину следующей цепи и перейти на шаг 2 (начать построение новой цепи Cj из вершины VQ). Шаг 5. Останов. Для анализа результативности алгоритма положим Ек = {є Є Е : rank(e) = к} , Е% = {є Є Е : rank(e) к} , Ек = Е\Е к, через G(E ) будем обозначать плоский граф, порожденный множеством ребер Е С Е. В [98] доказаны следующие леммы, которые показывают результативность выолнения процедуры «Упорядочение». 132 Лемма 5. Для любого к = 1,2,3, ...,М; где М = maxrank(e); ееЕ имеет место следующее утверждение: M(G(Ek)) Э G(M); S\M(G(Ek)) э G(E{). Лемма 6. Если М = maxrank(e); т,о Ем = 0. ееЕ Таким образом, этих лемм непосредственно следует результативность шага 1 алгоритма M-Cover. В теле алгоритма M-Cover организована такая последовательность применения процедуры «Формирование», при которой концом цепи будет либо тупиковая вершина, либо транзитная вершина, у которой напарник имеет более высокую спепень вложенности. Для этой последовательности оказывается справедлива лемма, аналогичная приведенной в [98].
Похожие диссертации на Построение маршрутов с локальными ограничениями на порядок обхода ребер в плоских графах: алгоритмы и программное обеспечение
