ОПРЕДЕЛЕНИЕ ПЛАНАРНОСТИ МАТЕМАТИЧЕСКОЙ МОДЕЛИ СХЕМЫ И ЕЕ ПЛОСКАЯ УКЛАДКА

Процедура 2 (Алгоритм Ханана).

Процедура 1.

1. Все вершины х_i принадлежат Х проектируются на ось S(T).

2°. Расстояние от наименьшей до наибольшей координаты делится пополам, и из этой точки i принадлежит I или [i] при iне принадлежащем I проводится перпендикуляр (столб Штейнера).

3°. Из каждой вершины x_ieX опускается перпендикуляр до пересечения со столбом Штейнера.

4°. Построено ДШ. Конец работы алгоритма.

Данный алгоритм очень прост, ВСА равна О(п), но в смысле минимума суммарной длины проводников результаты далеки от совершенства.

1. Все множество вершин хiеX разбивается на классы S_o, S₁,... ..., S_i в порядке возрастания координаты Si, так, чтобы у всех вершин одного класса была одинаковая координата S_i.

2^е. Анализируется множество вершин класса S₀, и соединяются перпендикуляром все вершины этого множества с точкой S_min оси S.^тш

3°. Образуется множество I', состоящее из всех точек I, которые были до этого соединены с произвольной вершиной x_i, включая и вершины хi, строящегося ДШ.

4°. Выбирается следующее множество S_i+1, имеющее наимень­шую координату S. Определяются точка i_mel' и вершина хj еS_{i + 1}, для которых

Другими словами, хi, находится на кратчайшем расстоянии от рассматриваемого фрагмента ДШ в классе S_{i + 1}. Точка i_m

с координатами (s_m, tm) соединяется с вершиной Xj с координатами (s_j, tj) двузвенной ломаной линией. Причем звенья параллельны координатным осям S и Т.

5 . Для каждой вершины производятся операции, аналогичные 4 . При этом вершина соединяется с ближайшей в 1'.

6°. Пункты 4 и 5 повторяются для всех по порядку множеств Sj до построения ДШ.

Отметим, что существует большое число модификаций описан­ных процедур. Можно проводить упорядочивание координат не по увеличению S(T), а по уменьшению S(Т). Временная сложность алгоритма процедуры 2 составляет О (сn²). На рис. 4.8 показана реализация процедуры 2 с упорядочиванием вершин в 1 в порядке убывания координат S. Суммарная длина ДШ составляет 22 условные единицы, при этом число ТШ равно 2.

Для построения ДШ можно использовать методы ПВГ, ПВШ или ветвей и границ в зависимости от требований на ВСА.

Непланариый граф; максимально планарный граф; матрицы модифицированная смежности, описывающая орграф; ориентированное покрывающее дерево; обратное ребро; дуга

После определения перечня соединений, т. е. построения КПД на основе принципов Прима или Штейнера, решаются задачи определения планарности ММ КС. Предварительно производится анализ графовой модели КС. Для этого осуществляют разбиение всего множества связных неографов M(G) на три непересекаю­щихся подмножества М₁, М₂ и М₃. В подмножество М_х включаются все связные графы, для числа вершин и ребер которых выполняется неравенство

Подмножество графов М₁ объединяет все заведомо планарные графы. Для связных графов, входящих в подмножество М₂, число вершин и некратных ребер должно быть связано следующим соотношением:

m > 3(n - 2). (4.7)

Все графы, включенные в подмножество М₂, заведомо непланарны. Это следует из того, что число ребер максимально планарного графа равно 3(n-2). Подмножество М₃ включает те связные графы, у которых число ребер лежит в пределах

В подмножество М₃ входят как планарные, так и непланарные графы.

Рассмотрим методику определения планарности графов, входя­щих в подмножество М₃. Приведенный алгоритм содержит три части. Первая часть посвящена описанию построения ориентиро­ванного графа D, получаемого из исходного графа G в результате поиска в глубину. Структура орграфа D проще исходного, так как сразу видны все пути и циклы в нем. Во второй части рассматриваются вопросы, связанные с нахождением циклов в графе D. В третьей части описывается построение планарного графа путем перемещения обратных ребер, соответствующих ранее найденным циклам [38, 52].

Дан неориентированный простой связный граф G без петель с числом вершин п. Граф G описывается матрицей R= [r_i, j] п х р, где р — максимальная локальная степень вершины в графе. Элемент r(I, J) = n, если в графе существует ребро (I, п). Дерево, получающееся в результате поиска в глубину на исходном графе G, называется ориентированным покрывающим деревом (ОПД). Дуга орграфа D = (V, W) является обратным ребром, если в ОПД существует путь от вершины w к вершине v и ребра графа D, не принадлежащие ОПД, являются обратными ребрами.

В качестве примера будем рассматривать фрагмент КС (рис. 4.9); модификация матрицы смежности которого приведена ниже.

Первая часть алгоритма заключается в построении матрицы В= [bij], описывающей орграф D. Орграф D строится на неориентированном простом связном графе G, представленном матрицей R с помощью поиска в глубину (см. 1.3). Алгоритм построения орграфа D приведен ниже.

Пусть v_t — номер вершины, рассматриваемой в настоящей момент времени. Сформулируем алгоритм.

1 .Построение начинается с вершины v_h i=1, n.

2°. В результате прохождения по ребру (v_i, vj), i не равно j инцидентно­му рассматриваемой вершине v_i происходит переход к следующей вершине Vj.

3°. Определяется, является ли Vj новой вершиной (или она была уже ранее пройдена), т. е. принадлежит ли ребро (v_i; vj) ОПД или нет. Если вершина ранее не посещалась, то переход к 4°, иначе — к 5°.

4 . Ребро (vi, vj) является дугой в ОПД. Рассматриваем новую вершину Vj т.е. v_i: = Vj, переход к 2°.

5°. Ребро (vi Vj), по которому был осуществлен переход в Vj, является обратным.

6°. Определяется, имеет ли рассматриваемая вершина v_t еще одно инцидентное ребро, которое не было ранее пройдено. Если да, то переход к 2°, иначе — к 7°.

7°. Осуществляется проверка, полностью ли построен орграф D, т. е. все ли ребра исходного графа G были пройдены во время построения. Если нет, то переход к 8°, иначе — к 9 .

8°. Происходит возвращение на ранее пройденную вершину v_i-1 по дуге ОПД, по которой осуществлялся переход в рас­сматриваемую в настоящий момент времени вершину vi„ и рас­сматривается уже вершина v_i_₁(v_i: = v_i-1) переход к 6°.

9°. Алгоритм прекращает работу. Построение орграфа D за­вершено.

Матрица В имеет ту же размерность, что и R. Элемент b(I, J) = к, если дуга (I, k)принадлежит ОПД, и b(I, J) = — к, если дуга (I, к) является обратным ребром. Рассматривается первая строка матрицы R, элементу матрицы В присваивается значение первого отличного от нуля элемента матрицы R,

стоящего в этой строке, т. е. процесс начинается с первой вершины, осуществляется переход по ребру (1, к) в вершину

к, так как к никогда ранее не посещалась. Производится формирование последовательностей S(L), L= 1, n, в которую входят номера пройденных вершин C(L), L=\,n, и номера столбцов, где стоят просмотренные вершины в матрице R, и SP(L), в которую входят вершины в порядке построения ОПД. Последовательности S(L) и C(L), L=1, n, используются, когда возникает необходимость вернуться назад на пройденную вершину и продолжать исследовать ребра, инцидентные ей. Последовательность SP(L) нужна во второй части алгоритма при построении матрицы, описывающей циклы в орграфе D. Далее все будет повторяться, как было описано выше, до тех пор, пока не будут исследованы все ребра исходного графа, т. е. построен орграф D (рис. 4.10), описываемый матрицей В, приведенной ниже:

Вторая часть алгоритма состоит в определении всех циклов в орграфе D и построении матрицы R_c, описывающей эти циклы. Число циклов в орграфе D равно числу обратных ребер в нем, т. е. числу отрицательных элементов в матрице В, так как все циклы в D состоят из пустого пути в ОПД и одного обратного ребра. Определение циклов в D происходит следующим образом.

Первыми находят циклы, соответствующие обратные ребра которых начинаются в вершине, исследованной последней при построении ОПД, затем циклы, обратные ребра которых исходят из вершины, пройденной предпоследней при построении ОПД, и т. д. Поиск цикла начинается из конечной вершины v соответст­вующего ему обратного ребра. При прохождении по дуге (v, w) ОПД, посещается некоторая вершина w. Если эта вершина не является началом какого-либо обратного ребра, то осущест­вляются переход по дуге, инцидентной ей в ОПД, и проход в следующую вершину и т. д. Если же w есть начало какого-либо обратного ребра, то определяется, является ли его конечная вершина той, с которой начали поиск. Если да, то цикл найден, если нет, то проходится следующая дуга, инцидентная w. Когда все дуги, инцидентные вершине w, пройдены, а цикл не найден, то возникает необходимость вернуться по дуге (и, w), по которой

пришли в w, и продолжать двигаться по другой дуге, инцидент­ной u, до тех пор, пока не выйдем на обратное ребро, соответствующее искомому циклу.

Матрица Мхп, где М — число обратных ребер в D; п—n число вершин, входящих в цикл максимальной длины, т.е. число вершин в графе. Известно, что М=т—n+1, где т — число ребер в исходном графе G.

В общем случае максимальное число обратных ребер в планарном орграфе D равно 2n — 5. Для того чтобы орграф стал планарен, число его дуг должно быть меньше или равно (in — 6). Это число слагается из суммы ребер в покрывающем дереве и обратных ребер. Следовательно, максимальное число обратных ребер

В строку матрицы R_c последовательно входят вершины, образующие цикл в D, т. е. каждая строка представляет собой набор вершин, последовательно входящих в отдельный цикл. В первом столбце этой матрицы стоят вершины, которые являются конечными вершинами обратных ребер, в последнем — находятся начальные вершины обратных ребер.

Третья часть алгоритма заключается в построении планарного графа из D с помощью перестановки его циклов, т. е. соответству­ющих им обратных ребер. Так как D состоит из ОПД и обратных ребер и каждый цикл в нем состоит из ребер в ОПД и одного обратного ребра, то построение планарного графа сводится к размещению обратных ребер в его орграфе D без пересечений. Предположим, что обратные ребра могут располагаться по отношению к покрывающему дереву в двух плоскостях. Одну из них пометим знаком « + », другую « —». Допустим, обратное ребро, идущее из вершины, пройденной последней при построении основного дерева, и соответствующий ему цикл, расположенный в первой строке матрицы R_c, раз­мещаются в «положительной» плоскости. Попытаемся разместить в этой плоскости цикл, стоящий во второй строке матрицы R_c. Алгоритм размещения нового цикла с ранее уложенными в одной плоскости приводится ниже.

1°. Если в новом цикле есть вершина, являющаяся конечной вершиной любого ранее расположенного обратного ребра, то переход к 2 , если нет — к 6°.

2°. Если начальная вершина этого ранее расположенного обратного ребра принадлежит новому циклу, то переход к 6 ,

иначе — к 3°.

3°. Если вторая вершина ранее уложенного цикла принадлежит новому, то переход к 4°, если нет — к 6°.

4°. Если начальная вершина в размещаемом обратном ребре является разветвлением в покрывающем дереве, т. е. имеет локальную степень исхода больше единицы, то переход к 6°, в противном случае — к 5°.

5°. Ранее уложенный цикл переносится в другую плоскость. Знаки элементов в строке матрицы R_c, соответствующей этому перемещенному циклу, меняются на противоположные, т. е. с « + » на « —» и с « —» на « + ».

6°. Новый цикл размещается с ранее уложенными в одной плоскости.

Если цикл располагается в «положительной» плоскости с ранее размещенными в ней, то рассматривают следующий новый цикл. Если нет, то ранее уложенный цикл перемещаем в отрицательную плоскость и аналогично проверяем, может ли он быть расположен с ранее уложенными циклами. Если нет, то ранее размещенный цикл переносят в положительную плоскость, знаки элементов в соответствующей строке матрицы R_c меняют с « —» на « + ». Затем аналогично проверяют возможность расположения переме­щенного в положительную плоскость цикла с ранее уложенными в ней. Далее процесс повторяется, как было описано выше. Если перенесенный в положительную плоскость цикл вызывает переме­щение в отрицательную плоскость первоначального цикла, с кото­рого началось рассмотрение на данном шаге, то считаем, что граф не планарен. Процесс будет продолжаться до тех пор, пока не окажется, что граф не планарен, либо пока не будут расположены все обратные ребра в D без пересечений, т. е. построен планарный граф (рис. 4.11), описанный матрицей R_c' приведенной ниже:

Необходимо отметить, что в общем случае при заданном фиксированном размещении элементов после получения плоской

укладки графа схемы возможно увеличение общей суммарной длины связи. Поэтому целесообразным является совмещение процессов определения планарности графа схемы и размещения его вершин по критерию суммарной длины ребер.

Алгоритм позволяет при исследовании матричного представле­ния неориентированного графа получить матрицу, определяющую ориентированный граф, структура которого проще, чем в исход­ном графе, найти все циклы в нем и перемещением соответству­ющих им обратных ребер получить планарный граф. Так, для рассматриваемого примера имеем плоскую укладку графа КС (рис. 4.12) и КС примет вид рис. 4.13.

Алгоритм используется для получения плоского изображения графа КС, ВСА равна О(an²).