Содержание к диссертации
Введение
Глава 1. Применение графов в математическом моделировании систем управления 21
1.1. Основные понятия и определения 22
1.1.1. Обыкновенные графы 22
1.1.2. Мультиграфы 23
1.1.3. Топологические графы 24
1.2. Маршруты в графах 25
1.2.1. Эйлеровы циклы. Задача о Кенигсбергских мостах 26
1.2.2. Гамильтоновы циклы. Задача коммивояжера 28
1.3. Разложения графов на цепи 30
1.4. Алгоритмы построения эйлеровых циклов без ограничений на
порядок обхода ребер 33
Глава 2. Маршруты с локальными ограничениями 40
2.1. Алгоритм построения допустимой цепи 41
2.2. Алгоритм построения допустимой эйлеровой цепи 49
2.3. Покрытие графа допустимыми цепями 58
Глава 3. Маршруты с упорядоченным охватыванием 62
3.1. Представление плоского графа 64
3.2. Существование эйлеровых Оі?-циклов 65
3.3. Рекурсивный алгоритм построения эйлеровых Оі?-циклов 68
3.4. Результативность рекурсивного алгоритма 69
3.5. Нерекурсивный алгоритм построения эйлерова Оі?-цикла 73
3.6. Эффективный алгоритм построения Оі?-маршрута в произ вольном связном плоском графе 85
3.6.1. Оі?-маршрут китайского почтальона 86
3.6.2. Задача построения покрытия с упорядоченным охваты-ванием 93
3.7. Оптимальное покрытие плоского графа последовательностью О -цепей 101
3.8. Построение оптимального Оі?-покрьітия для многосвязногографа 105
Глава 4. Дополнительные ограничения на обходы с упорядоченным охватыванием 111
4.1. О существовании системы переходов, допускающей АОЕ-цепь 113
4.2. АОЕ-цеии для 4-регулярных графов 114
4.2.1. Пример 116
4.3. О числе эйлеровых ОЕ-цепей для заданной системы переходов 118
4.3.1. Число ОЕ-цепей для системы переходов, соответствующей Л-цепи 120
4.3.2. Число ОЕ-цепей для непересекающейся системы переходов 122
4.3.3. Необходимое условие существования ОЕ-цепи для фиксированной системы переходов 124
4.3.4. Некоторые замечания и критерии 129
Глава 5. Программное обеспечение для построения ОЕ-цепей и ОЕ-покрытий 132
5.1. Программное обеспечение задачи построения эйлерова Оі?-цикла132
5.1.1. Рекурсивный алгоритм построения эйлерова ОЕ-цикла, 132
5.1.2. Оі?-маршрут китайского почтальона 136
5.1.3. Эффективный алгоритм построения покрытия 139
5.2. Программное обеспечение для построения Оі?-покрьітия несвязного графа 142
5.3. Алгоритм тестирования. Критерий соответствия цепи условию упорядоченного охватывания 143
5.4. Программа для построения АОЕ-цеии 145
Глава 6. О возможных практических приложениях решаемой задачи 148
6.1. Задача прямоугольного раскроя и Оі?-покрьітия 152
6.1.1. Алгоритмы для кодирования раскройного плана 153
6.1.2. Выбор оптимальной укладки деталей 158
Выводы и основные результаты 161
Литература 164
- Эйлеровы циклы. Задача о Кенигсбергских мостах
- Нерекурсивный алгоритм построения эйлерова Оі?-цикла
- О числе эйлеровых ОЕ-цепей для заданной системы переходов
- Эффективный алгоритм построения покрытия
Эйлеровы циклы. Задача о Кенигсбергских мостах
Обыкновенным графом G = (V, Е) называется упорядоченная пара множеств: конечного непустого V, элементы которого называются вершинами графа (7, и подмножества Е, элементы которого называются ребрами этого графа. Ребро ху соединяет вершины х и у (или, что то же самое, у и ж), а также инцидентно каждой из них (и наоборот, они обе инцидентны этому ребру); ребро можно обозначать и одной буквой (е, и и др.), если не требуется напоминать, какие именно вершины оно соединяет. Вершины ж, у Є V смежны, если ребро ху Є Е, и несмежны, если ху ф Е.
Часть G = (V , Е ) называется подграфом графа G, если Е = {ху Є Е \х,у Є V }; иными словами, при образовании подграфа G из графа G удаляются все вершины множества V \ V и только те ребра, которые инцидентны хотя бы одной удаляемой вершине. Таким образом, подграф данного графа G однозначно определяется заданием непустого подмножества вершин V или, что равносильно, заданием строгого подмножества W = V\V С V тех вершин, которые надо удалить; в последнем случае будем кратко писать G = G \ W, а если V = {у} (одновершинное множество), то даже G = G\ {у}. В частности, при V = V имеем G = G\0 = G. Граф называется связным, если множество его вершин невозможно так разбить на попарно непересекающиеся непустые подмножества, чтобы никакие две вершины из разных подмножеств не были бы смежны. Несвязный же граф однозначно разбивается указанным способом на связные подграфы, называемые компонентами связности.
Под мультиграфом будем понимать упорядоченную тройку G = (V, Е, (/?), где V т 0 - множество вершин, Е - множество ребер, оба конечные, а ср : Е — V - отображение, относящее каждому ребру є Є Е неупорядоченную пару (р(е) = ху вершин х, у Є V, называемых концами этого ребра.
Возможной формой представления графов является матрица инцидентности «вершины/ребра». Строкам данной матрицы соответствуют вершины графа G, а столбцам - ребра. Если ребро е = {V1V2}, то на пересечении столбца е и строк V\ и V2 будут стоять единицы. Остальные элементы столбца е -нулевые. Пространственная сложность такого представления равнаО(У \Е\).
Очевидно, что для представления графа можно организовать список ребер, с указанием для каждого ребра пары инцидентных вершин. Пространственная сложность такого представления будет 0(i? log2 ). Логарифм в данном выражении появляется в связи с необходимостью нумерации вершин.
Для обозначения мультиграфа G(V, Е, ср) будем использовать обозначение G = {V, Е), если это не приводит к двусмысленности. 1.1.3. Топологические графы
Топологическим графом называют такой граф G = (V, Е,(р), вершинами которого служат некоторые выделенные точки трехмерного евклидова пространства, а ребрами - жордановы дуги, соединяющие эти точки; у звена обе инцидентные вершины (концевые точки) различны, у петли совпадают. Требуется еще, чтобы никакая внутренняя (неконцевая) точка ребра не совпадала ни с одной вершиной графа и ни с одной точкой другого ребра; всякое нарушение этого требования будем кратко называть пересечением,. Таким образом, изображение абстрактного графа на рисунке само является топологическим графом, изоморфным исходному лишь при условии, что рисунок не содержит пересечений.
Всякий абстрактный граф допускает топологическое представление, т. е. в пространстве существует изоморфный ему топологический граф.
Как в теории, так и в приложениях особо важную роль играют те топологические свойства графа, которые связаны с возможностью или невозможностью поместить его в плоскость. Известно, что евклидова плоскость гомео-морфна сфере, из которой удалена одна точка; соответствующее отображение можно осуществить, например, с помощью стереографического проектирования. Этим же отображением топологический граф на сфере переводится в изоморфный топологический граф на плоскости и наоборот. Граф, допускающий такие топологические представления, называется планарным, а его конкретное представление в плоскости - плоским графом.
Если Gs - топологическое представление графа G в плоскости S, то компоненты связности множества G \ S называются гранями плоского графа Gs, а множество граничных точек грани - ее краем] теоретико-множественное объединение краев всех граней равно Gs-, поэтому каждое ребро и каждая вершина принадлежат краю хотя бы одной грани, и ясно также, что никакое ребро (в отличие от вершины) не может принадлежать краям более чем двух граней. Ровно одна из граней плоского графаGs является внешней (бесконечной). Причем всегда можно так изменить расположение графа Gs в плоскости S (т. е. построить изоморфный ему граф G s), чтобы наперед заданная грань стала внешней: для этого достаточно сначала отобразить стереографически Gs на сферу, затем повернуть ее так, чтобы полюс N попал в образ выбранной в качестве внешней грани, и, наконец, спроектировать граф обратно на плоскость S.
Нерекурсивный алгоритм построения эйлерова Оі?-цикла
Данная задача появилась примерно на столетие позже задачи Эйлера. Гамильтонова игра (так она называлась в 1884 г.) заключается в нахождении такого маршрута по ребрам правильного додекаэдра, который проходит ровно один раз через каждую вершину додекаэдра (рис. 1.3). Уильям Гамильтон, который изобрел эту игру, обозначал двадцать вершин додекаэдра буквами, которые символизировали названия разных городов. Тридцать ребер додекаэдра - все возможные пути между городами. Бытовой смысл задачи - объехать «весь мир», а именно: начиная от какого-либо города, побывать в каждом городе один и только один раз и вернуться в начальный пункт, причем задан порядок, в котором следует посетить первые п городов, где п 5 [29].
Если ребрам графа приписаны некоторые веса и граф содержит несколько гамильтоновых циклов, то большой интерес представляет также задача нахож дения гамильтонова цикла с минимальным общим весом, названная задачей коммивояжера.
Представление о непосредственных применениях гамильтоновых цепей дает следующая ситуация [31]. Имеется машина и п заданий, каждое из которых она способна выполнить после соответствующей настройки. При этом необходимо затратить на переналадку tij единиц времени для того, чтобы после выполнения г-го задания выполнить j-e. В предположении, что tij = tji, требуется найти последовательность выполнения заданий, при которой время каждой переналадки не превосходит величины t. Если построить граф G, у которого V = {1, 2,... п}, Е = {i, j I t t}, то описанная задача сводится к отысканию гамильтоновой цепи в этом графе.
Задача выяснения существования гамильтонова цикла в данном неориентированном графе, а также задача нахождения такого цикла, если он существует, является важной задачей теории графов, как с практической, так и с теоретической точек зрения. Этой задаче и тесно примыкающей к ней задаче коммивояжера посвящено большое число работ [30]. Известно, что задачи, в которых определяется, содержит ли граф G = (V, Е) гамильтонов цикл, является Л/ Р-полной [30]. Задача остается таковой и в следующих случаях:
Несмотря на возможность нахождения эйлерова цикла за полиномиальное время и А/ Р-полноту задачи комивояжера, между эйлеровыми и гамильтоновы-ми циклами существует тесная взаимосвязь [45]. Например, в статье [5] приводятся различные взаимосвязи между эйлеровыми графами и прочими свойства ми графов (как то гамильтоновость, существование нигде ненулевых потоков, существование треугольных циклов и пр.).
В данной работе будем рассматривать вопросы построения наборов маршрутов, покрывающих все ребра графа. С данной проблемой наиболее тесно связаны задачи построения эйлеровых циклов.
Будем говорить, что набор реберно-непересекающихся цепей покрывает граф G, если каждое ребро графа G входит в одну из этих цепей. Из теоремы 1 фактически следует, что связный граф обладает открытой или закнутой покрывающей цепью тогда и только тогда, когда он имеет не более двух вершин нечетной степени.
Пусть связный граф G содержит т вершин нечетной степени. Очевидно, что т четно, т.е. т = 2к. Рассмотрим граф G , полученный добавлением к G новой вершины v и ребер, соединяющих v с вершинами графа G нечетной степени. Поскольку степени всех вершин графа G четны, то G содержит эйлеров цикл. Если теперь выбросить v из этого цикла, то получится к цепей, содержащих все ребра графа G, т.е. покрывающих G. С другой стороны, граф, являющийся объединением г реберно-непересекающихся цепей, имеет самое большее 2г вершин нечетной степени. Поэтому меньшим числом цепей граф G покрыть нельзя. Данный результат известен как теорема Листинга-Люка [4,72].
Теорема 2. Если связный граф содержит ровно 2к вершин нечетной степени, то минимальное число покрываюищх его реберно-непересекающихся цепей равно к.
Эйлеров граф содержит, как правило, несколько эйлеровых циклов. Зная один такой цикл, получить новый можно следующим простым приемом. Пусть С - исходный эйлеров цикл, и вершина v проходится в этом цикле более одного раза. Рассмотрим часть (подцикл) цикла С, состоящую из ребер и вершин, проходимых между к-ш и 1-м [к Ї) посещениями вершины v. Это будет некоторый цикл С\. Цикл С, как и всякий эйлеров цикл, задает некоторый порядок обхода ребер графа и индуцирует порядок прохождения ребер цикла С\. Итак, изменив указанным способом эйлеров цикл, получаем новый эйлеров цикл. Теорема Коцига [31] утверждает, что последовательности таких изменений достаточно для получения всех эйлеровых циклов из данного.
Теорема 3. [А.Коциг]. Если С и С - эйлеровы циклы графа G, то в G существует такая последовательность эйлеровых циклов С = С\, Сі-, , Ck = С, что С{+\ получается из СІ путем изменения порядка обхода ребер некоторого подцикла на обратный.
Таким образом, из теоремы Коцига можно заключить, что граф G как правило имеет много эйлеровых цепей, а, следовательно, и разложений на цепи. Поэтому имеется возможность построения разложений, удовлетворяющих дополнительным ограничениям.
Большое число примеров различных типов эйлеровых цепей приведено в первом томе монографии Г. Фляйшнера «Эйлеровы графы и смежные вопросы» [72], где систематизировано и достаточно подробно рассматриваются некоторые виды эйлеровых цепей, например:
О числе эйлеровых ОЕ-цепей для заданной системы переходов
Процедура Order использует переменную к как счетчик стадий и функцию rank() : Е — N, указывающую номер стадии, на которой ребро ставится в очередь М1-помеченных ребер. Содержаельный смысл функции rank заключается в том, что она определяет ранг ребра е (определение ранга ребра приведено в разделе 3.3). Заметим, что ранг любого ребра плоского графа может быть определен за время 0(i?) с помощью процедуры Order. Ек = Е\Е1, Данная процедура выполняется следующим образом. На первой стадии в очередь М1-помеченных ребер вводятся все ребра є Є Е, ограничивающие внешнюю грань /о, а их ориентация задается так, чтобы /і(е) = /о- На стадии к + 1 каждое ребро є Є Е, попавшее в очередь М1-помеченных на стадии к, переводится в состояние М2-помеченного и помещается в списки вершин vj(e), / = 1,2 (см. рис. 3.5), а в очередь М1-помеченных включаются все непомеченные
Доказательство леммы проведем методом математической индукции по к. Из описания алгоритма следует, что к принимает значение, равное 1, при выполнении процедуры Initiate, и значения rank() = 1 устанавливаются только на ребрах, вводимых в очередь М1-помеченных при первом выполнении тела внешнего цикла в процедуре Order. В соответствии с описанием процедуры Initiate ребра ео и е\ = /і(ео) ограничивают внешнюю грань /о графа G, значение переменной пе указывает на ребро Єї, а значение переменной v = г і(ео) -на вершину г і, инцидентную ребрам ео и е\. Поэтому при первом выполнении тела цикла Order в очередь М1-помеченных будут последовательно внесены все ребра цепи удовлетворяющей условиям
Таким образом, значение rank() = 1 будет определено на всех ребрах, ограничивающих внешнюю грань /о графа G. В этом случае справедливость утверждений леммы очевидна. Предположим, что доказываемые утверждения имеют место для А; К М. Рассмотрим множество
Из связности графа G, а также из того, что FK-I С \X\1{G{EK)) следует Fk-\ 7 0? поэтому, в соответствии с описанием алгоритма, значение функции rank() = К будут определены на ребрах максимальных по включению цепей и все цепи С(е), є Є F являются реберно-непересекающимися. Из СВЯЗНОСТИ графа G и отсутствия в нем висячих вершин следует, что в цепи С(е), є Є FK-I ее последняя вершина fm+i принадлежит V(Ex-i), где V(Ex-i) - множество вершин, инцидентных ребрам из Ex-i-
Если в цепи С(е), є Є FK-I имеет место равенство V\ = vm+\, то С(е) -цикл. Если же v\ fm+b т0? поскольку G (EK-I) — объединение непересекающихся по ребрам цепей, в цепи, содержащей ребро /і(ето), существует единственное ребро є Є FK-Ї- Щ(е ) = vm+\. Кроме того, по построению т.е. имеем противоречие с условием леммы. Лемма 2 доказана. Из леммы 2 следует, что алгоритм определит на каждом ребре є Є Е значение функции rank(), т.е. каждое ребро є Є Е будет включено в очередь М1-помеченных ребер. Так как после включения ребра є Є Е в эту очередь marki(e) 7 т0 такое включение возможно единственный раз. Каждое ребро, попавшее в очередь М1-помеченных ребер, переводится в состояние М2-помеченного включением его в стеки вершин Щ(е), к = 1,2 в порядке, определяемом очередью, т.е. в порядке возрастания величины rank(e). Поэтому после завершения процедуры Order для каждой вершины v Є V будем иметь
Для доказательства воспользуемся методом математической индукции по переменной к. Ребра множества Е\ образуют цикл, ограничивающий внешнюю грань /о графа G, поэтому они будут включены в построенный алгоритмом цикл. Кроме Algorithm 8 Процедура FormChain Учитывая выше изложенное, заключаем, что L = \Е\, а цикл, построенный процедурой FormChain, является эйлеровым Оі?-циклом. Очевидно, что вычислительная сложность этапов «Инициализация» (процедура Initiate) и «Формирование» (процедура FormChain) составляет величину 0{\Е\). Вычислительная сложность этапа «Упорядочение» (процедура Order) также составляет величину 0(\Е\), так как каждое ребро единственный раз ставится в очередь М1-помеченных ребер и затем переводится из нее в стеки вершин, а вычислительная сложность этих операций составляет величину 0(1). Таким образом, вычислительная сложность алгоритма - 0{\Е\).
В первой части алгоритма, когда требуется найти цикл из ребер подграфа, ограничивающих внешнюю грань текущего подграфа, возникает ситуация, когда поле Mark помещенного в очередь ребра указывает либо на само себя (висячая вершина текущей компоненты связности), либо это ребро не совпадает с начальным для данной компоненты связности, а указывает на уже помеченные ребра (мост). В обоих случаях необходимо продублировать данные ребра. Введение дополнительных ребер повлечет за собой такое изменение указателей, как показано на рис. 3.6.а) - для висячей вершины и 3.6.6) - для моста.
После выполнения соответствующих построений для всех ребер поле Mark на первой стадии выполнения алгоритма оказывается сформированным таким образом, что остальные функции алгоритма, разработанного для эйлерова графа, не будут требовать модификации. Таким образом, после введения некоторого числа дополнительных ребер, будет получен эйлеров граф, а найденный в нем цикл будет иметь упорядоченное охватывание. В исходном же графе будем иметь маршрут, в котором ни один цикл из уже пройденных ребер не будет охватывать еще не пройденных. Описанную модификацию алгоритма 3 будем называть алгоритмом СРР_0Е (см. алг.13) (этот алгоритм решает Оі?-задачу китайского почтальона). Рекурсивный вызов функции для каждого непомеченного ребра, инцидентного вершинам цикла, полученного на предыдущем этапе, производится без изменений. После построения обхода для соответствующей компоненты связности, он включается в результирующий обход.
Обобщим все сказанное выше в виде следующей теоремы. Теорема 10. Маршрут, построенный с помощью алгоритма СРР_0Е, является ОЕ-маршрутом. Сложность алгоритма составляет величину О(\E(G)\ \V(G)\).
Доказательство этой теоремы очевидно, т.к. на самом деле ребра, полученные в результате дополнительных построений, являются недостающими фрагментами выделяемых алгоритмом циклов. Потребуется не более чем 0(\E(G)\) добавлений ребер, а добавление одного ребра требует изменения шести указателей.
Эффективный алгоритм построения покрытия
Рассмотрим тот же граф, но с другой системой переходов Xc{G) (см. рис.4.7). Основным отличием этой системы переходов от представленной на рис.4.6 является наличие пересечений в вершинах V2 и з- В этом графе существует единственная Оі?-цепь Пример графа, система переходов которого имеет пересечения удовлетворяющия заданной системе переходов XQ(G). В случае выбора вершины v\ либо вершины г з получим цикл V\e\Vz&bV2&2V\ охватывающий еще не пройденное ребро ез- Несмотря на то, что вершины v\ и г з дважды встречаются в указанной цепи, возможно начать построение цепи только в одном случае.
Следствие 2. Если цепь Т имеет упорядоченное охватывание, то ее последнее ребро смежно внешней грани /о.
Доказательство. Предположим противное. Пусть Оі?-цепь завершается ребром е/ /о- Это означает, что все ребра, смежные внешней грани, пройдены раньше е/. Тогда существует цикл С/0, ограничивающий внешнюю грань и охватывающий непройденное ребро е/. Но согласно условию следствия Т является Оі?-цепью, т.е. ни одно из ее непройденных ребер не может быть охвачено циклом из пройденных ребер. Имеем противоречие условию следствия.
Займемся подсчетом числа Оі?-цепей для фиксированной системы переходов. Доказано (см. [61]), что любая Оі?-цепь начинается в вершине v Є /о и завершается ребром є Є /о (см. следствие 2). Каждая вершина Vj Є /о, j = 1,... г (/о) имеет ровно два инцидентных ей ребра, которые смежны внешней грани /о (конечно же, если эта вершина не является разделяющей). По одному из этих ребер цепь достигает вершину Vj, а по другому - покидает ее. Если оба этих ребра используются только для достижения вершины, тогда не выполнено условие упорядоченного охватывания (в этом случае одно из этих «ребер прибытия в вершину» оказывается пройдено раньше, чем были пройдены некоторые внутренние ребра). Если оба ребра используются только для покидания вершины, то в системе переходов XT{G) возникнут пересечения. Однако согласно условиям следствия 14 это невозможно. А так как А-цепь является замкнутой последовательностью ребер и вершин, то ее начало может быть помещено в любую вершину, например, в Vj Є /о, причем,в последовательности ej-iVjej ребро ej-i Є /о (в соответствии со следствием 2). Если предположить противное, тогда последнее ребро в цепи окажется охваченным циклом из ребер, смежных внешней грани. Так как начало цепи можно сдвинуть в любую вершину, смежную внешней грани, и в соответствии с предопределенным циклическим порядком 0+(G) можно выбрать только одно инцидентное ребро для покидания текущей вершины, то из произвольой вершины v Є /о может быть построена единственная возможная ОЕ-цепь. Так как существует 1 (/о) вершин, смежных внешней грани, тогда число ОЕ-цепей, соответствующих системе переходов для Л-цепи равно 1 (/о)- Теорема доказана.
Предположим, что в графе G(V, Е) имеются точки сочленения на некоторой грани. Тогда для системы переходов XT(G), соответствующей Л-цепи в данном графе, имеем следующее.
Следствие 3. Пусть в плоском графе G = (V, Е) с К точками сочленения V\,...VK Є /О существует А-цепъ Т с системой переходов XT(G), a V(fo) - множество вершин, смежных внешней грани, тогда существует ровно (/о) + i=1(deg( i)/2 — 1) цепей с упорядоченным охватыванием для XT{G).
Доказательство. В соответствии со следствием 14 плоский граф G без точек сочленения имеет ровно 1 (/о) цепей с упорядоченным охватыванием, обладающих свойствами Л-цепи. Рассмотрим точку сочленения Vi степени deg(fj) = 2М{. Существует М{ ребер для достижения данной вершины и столько же ребер для ухода из данной вершины в соответствии с заданным циклическим порядком. Так как при подсчете Оі?-цепей была учтена только одна пара ребер, инцидентных точке сочленения, то было упущено М{ — 1 способов выбора начального ребра цепи. Суммируя по всем точкам сочленения, получим выражение, указанное в формулировке следствия. Следствие доказано.
Следствие 4. Пусть в плоском графе G = (V, Е) существует непересекающаяся цепь Т. Пусть XT(G) - система переходов, соответствующая этой цепи Т. Пусть V(fo) - множества вершин, смежных внешней грани, av\}.. .VK Є /о - разделяющие вершины, смежные внешней грани. Тогда существует ров 122 но 1 (/о) + i=1 (deg( )/2 - 1) цепей с упорядоченным охватыванием для системы переходов XT(G).
Доказательство. Когда степени всех вершин графа не превосходят 4, имеем случай Л-цепи. Рассмотрим граф, хотя бы одна вершина которого имеет степень 6 или выше, и систему переходов XT(G), которая не соответствует А-цепи. В графе G допускается существование Л-цепи, но для некоторой другой системы переходов.
Покажем, что ребра низших рангов не охватывают ребер более высоких рангов в процессе построения цепи. В данном случае получим рассуждения, схожие с предложенными в доказательстве следствия 14. Если предположить, что условие упорядоченности охватывания нарушено, то в этом случае система переходов должна иметь хотя бы одно пересечение. Но наличие пересечений недопустимо согласно формулировке данного следствия. Аналогичным образом можно показать, что число ОЕ-цепей для системы переходов без самопересечений равно 1 (/о) для графа без разделяющих вершин.
Формула для подсчета числа цепей для графа с разделяющими вершинами непосредственно следует из следствия 3. Следствие доказано.
Рассмотрим пример. Граф на рис.4.8 не имеет Л-цепи, но система переходов, представленная на рисунке, не имеет пересечений. Для данного графа существует три ОЕ-цепи, и все начинаются в различных вершинах, смежных внешней грани:
Похожие диссертации на Построение маршрутов с ограничениями на порядок обхода ребер в плоских графах: алгоритмы и программное обеспечение
