Минимальные плоские размещения

Рассмотрим свойства нумераций j Î F ^*, соответствующих реализациям дерева t (V, E) каноническими   - суперпозициями над S. Линейная укладка  дерева t (V, E) называется плоской, если она допускает геометрическую реализацию графа в полуплоскости. Соответствующая ей нумерация j  также называется плоской. Нумерация j   является плоской тогда и только тогда, когда между номерами вершин произвольной пары ребер (v, v_j) и (v_k, v_r) не существует соотношений:

j (v_i) < j (v_k) < j (v_j) < j (v_r) или j (v_k) < j (v_i) < j (v_r) < j (v_j).            (5.2.1.)

Не ограничивая общности рассмотрения, полагаем в (5.2.1) j (v_i) < j (v_j), a j (v_k) < j (v_r).

Класс плоских нумераций пересекается с классом нумераций Ф* (например, монотонная нумерация любой цепи s (V, E)), однако ни один из них не содержится целиком в другом (рис. 5.2.1.).

  

 

плоская j Ï F ^*

                                                    

неплоская j Î F ^*

                          Рисунок 5.2.1.

Теорема 5.2.1. Нумерация j Î F ^* вершин дерева t (V, E) является плоской тогда и только тогда, когда соответствующая ей последовательность цепей разложения s _j (V_j, E_j),  обладает следующим свойством

связно при                (5.2.2)

Доказательство. Необходимость. Покажем, что если нумерация j Î F ^* является плоской, то условие (5.2.1) выполнено. Предположим, что найдется хотя бы одно   такое, что     не имеет общей вершины с цепью s _k. Выделим в дереве цепь, соединяющую вершину   цепи s _k с вершиной   из , не содержащую ребер из s _k и . Пусть s_qÎ  - цепь (одна из цепей), содержащая вершину .

Так как j Î F ^*, то вершины   и   не могут быть концевыми в указанных цепях, поскольку они не являются висячими в поддеревьях, в которых выделяются цепи s_qи s _k. Обозначим через   и  (   и )вершины, смежные с ()на цепи s_q (s _k). Поскольку нумерация вдоль каждой цепи разложения монотонна, то, не ограничивая общности, можно положить

j ( ) < j ( ) < j ( ) и j ( ) < j ( ) < j ( ).     (5.2.3)

Отсюда, учитывая порядок выделения цепей и сплошность нумерующих последовательностей всех поддеревьев разложения, получаем соотношения

j ( ) < j ( ) < j ( ) и j ( ) < j ( ) < j ( )           (5.2.4)

Из (5.2.3) и (5.2.4) следует, что при любом соотношении между номерами j ( ) и j ( ) среди ребер множества {(, ),(, ),(, ),(, )} всегда найдутся такие два ребра, для которых будет справедливо одно из неравенств (5.2.1), т.е. нумерация j не будет плоской.

Достаточность. Пусть нумерация j Î F ^*  вершин дерева t (V, E) удовлетворяет условию теоремы. Разместим вершины   вдоль целочисленной прямой в точках с координатами j ( ) и соединим дугами смежные вершины. Дуги, соответствующие ребрам одной цепи, очевидно, не пересекаются, так как нумерация вдоль каждой цепи s _j,  монотонна. Покажем, что не могут пересекаться и дуги, соответствующие различным цепям. Действительно, из сплошности нумерующих последовательностей всех поддеревьев разложения следует, что внутри отрезка, заключенного между номерами концевых вершин любой цепи s _j,   содержится номер лишь одной вершины , входящей в цепи множества { s ₁,..., s _{j -1} }.  Учитывал связность , вершина   обязательно принадлежит и цепи s _j,т.е. дуги цепи s _j не пересекаются с дугами це­пей из множества { s ₁,..., s _{j -1} }. Рассматривая последовательно дуги цепей s _j, , убеждаемся в справедливости утверждения о том, что j плоская нумерация.                                                               ð

Условие (5.2.2) означает, что все нумерации j Î F ^*, соответствующие каноническим   - суперпозициям над S, являются плоскими.

Лемма 5.2.1. Всякая минимальная плоская нумерация j  дерева t (V, E) принадлежит классу F ^*.

Доказательство. Разложим дерево t (V, E) на пореберно непересекающиеся цепи s _j (V_j, E_j), , соединяющие в каждом поддереве разложения вершины с наименьшими и наибольшими номерами. Покажем, что если j минимальная плоская нумерация, то указанное разложение обладает всеми свойствами  нумераций из класса Ф* и, следовательно q = l.

Если нумерующая последовательность хотя бы одного поддерева разложения, образующегося в процессе выделения цепей s _j (V_j, E_j) не является сплошной, то нумерация j не будет плоской, поскольку нумерующая последовательность всего дерева сплошная и каждое поддерево разложения связно.

Если хотя бы одна из концевых вершин некоторой цепи s _j (V_j, E_j), не является висячей в поддерева, в котором она выделяется, то, не выходя из класса плоских нумераций, можно уменьшить значение функционала (5.1.1), перейдя к двойственной нумерации на поддереве, "висящем" на такой концевой вершине.

Если хотя бы на одной из цепей s _j (V_j, E_j),   нарушена монотонность, то нумерация j не будет плоской, поскольку концевые вершины всех цепей s _j (V_j, E_j),   являются висячими и имеют наименьший и наибольший номера в поддереве, в котором эта цепь выделяется. ð

Рассмотрим, какие канонические   - суперпозиции надS соответствуют минимальным плоским нумерациям. Выделим в дереве t { V, E)   произвольную вершину   степени s (v_i)= p и все инцидентные ей ребра (v_i, v_r), . Любая вершина v_q ¹ v_i связана с вершиной v_i единственной  цепью. Будем говорить, что вершина v_q принадлежит ветке, выходящей из вершины v_i  по ребру (v_i, v_r), , если в v_q можно попасть из v_i по цепи, содержащей ребро (v_i, v_r). Число вершин ветки определяет её вес.

Теорема 5.2.2. Плоская нумерация j Î F ^*   произвольного дерева t (V, E) является минимальной тогда и только тогда, когда цепи s _j (V_j, E_j),  проходят через вершины дерева по веткам наибольшего веса.

Доказательство. Необходимость. Пусть j   минимальная плоская нумерация дерева t (V, E). Для вершин  степени s (v_i) £ 2 необходимость условия теоремы очевидна. Рассмотрим произвольную вершину   степени s (v_i) ³ 3. Выделим два случая.

1.Цепь s ₁ проходит через вершину v_i. При этом из теоремы 5.1.1, леммы 5.1.4 и свойств нумераций класса F ^* следует, что нумерующие последовательности всех веток к v_i будут сплошными. Взаиморасположения их вдоль числовой прямой приведены на рис.5.2.2.

1 j ( )           _{· · ·} j ( )   j (v_i) j ( ) _{· · ·}     j ( )    n

                                     

                                          p - четно

1 j ( )          _{· · ·}    j ( )        j (v_i)         j ( )        _{· · ·}   j ( )    n

                                                                                           

 

                            n _{p- 2}               n_p                                                             n₂

                                               p – нечетно.

 

Рисунок 5.2.2.

Поскольку минимальная плоская нумерация j  дерева t (V, E) принадлежит классу F ^*, то и ,   - число вершин в ветках, по которым k -ая цепь разложения проходит через вершину v_i. При нечетном p указаны две возможности для нумерации вершины v_i, поскольку последняя цепь разложения проходит через v_i только по одной ветке (с числом вершин п_р) и в зависимости от выбора направления нумерации на этой цепи последняя ветка может быть занумерована как до, так и после вершины v_i (в последующих расчетах выбран вариант, когда последняя ветка занумерована до вершины v_i).

Из сплошности нумерующих последовательностей всех веток к v_i следует возможность перехода на каждой из них к двойственной нумерации. При этом  сумму длин всех ребер, инцидентных вершине v_i - величину , можно оценить сверху следующим образом:

              (5.2.4)

при p четном

                                                                      (5.2.5)

при p нечетном.

Необходимым условием минимальности каждого из выражений (5.2.4) и (5.2.5) является, очевидно,  выполнение для первой взвешенной суммы   соотношений , а для второй взвешенной суммы соотношений . В противном случае, поменяв порядок нумерации вершин соответствующих веток, можно уменьшить величину , что противоречит минимальности нумерации j. Таким образом, для всех вершин v_i, через которые проходит цепь s ₁,условия теоремы выполнены, то есть все цепи разложения s _j (V_j, E_j),   проходят через вершины v_i  по веткам с наибольшим числом вершин.

2.Цепь s ₁   не содержит вершину v_i. Пусть  - первая цепь разложения, проходящая через v_i.   Так как связно при , то цепь s _k  обязательно проходит через v_i по ветке, содержащей предыдущие выделенные цепи . Число вершин в этой ветке больше, чем в какой-либо другой ветке к v_i, так как она содержит цепь s ₁, проходящую через вершины дерева по веткам с наибольшим числом вершин. Следовательно, нарушение условий теоремы невозможно ни на какой паре веток к v_i, одна из которых содержит цепь s ₁. Поскольку нумерация остальных веток к v_i производится сплошными нумерующими последовательностями, то дальнейшее доказательство проводится аналогично первому случаю. Итак, и  для всех вершин v_i, через которые не проходит цепь s ₁,условия теоремы также выполнены, то есть все цепи разложения s _j (V_j, E_j),   проходят через такие вершины v_i  по веткам с наибольшим числом вершин.

Достаточность. Нетрудно видеть, что если способ выделения цепей s _j (V_j, E_j),   удовлетворяет условиям теоремы, то ,  связно. По теореме 5.2.1 любая нумерация j Î F ^*  является при этом плоской. Все такие нумерации обладают, кроме того, одинаковым значением минимизируемого функционала (6.1.1). Действительно, если нумерации отличаются лишь направлением роста номеров вдоль некоторых цепей s _j (V_j, E_j), , то справедливость доказываемого утверждения непосредственно следует из свойств нумераций класса Ф* и вида минимизируемого функционала (5.1.1).

Если меняется разложение на цепи s _j (V_j, E_j), , то это влияет лишь на порядок нумерации веток с одинаковым числом вершин для некоторых . Из способа выделения цепей следует, что ветки к любой вершине v_i, содержащие одинаковое число вершин, имеют сплошные нумерующие последовательности. Поэтому, меняя порядок их нумерации, всегда можно перейти от одного разложения к другому, сохранив неизменным значение функционала (5.1.1).

Поскольку минимальные плоские нумерации содержатся среди рассматриваемых (это следует из необходимости условий теоремы), получаем отсюда минимальность всех нумераций, удовлетворяющих условиям теоремы.                                                                                        ð

Алгоритм построения минимальной плоской нумерации

На основе теоремы 5.1.2 можно предложить алгоритм  построения минимальной плоской нумерации вершин произвольного дерева. Основу его составляет следующая процедура:

1. Выбрать в текущем поддереве разложения (исходном дереве) произвольную вершину дерева v ₀.

2. Перейти от вершины v ₀  по веткам с наибольшим числом вершин в некоторую висячую вершину v ₁.

3. Начиная от вершины v ₁, построить по веткам с наибольшим числом вершин цепь  в некоторую другую висячую вершину v ₂.

4. Присвоить вершинам v ₁  и   v ₂ наибольшие и наименьшие номера из диапазона, выделенного под текущее поддерево разложения (1 и n для исходного дерева).

5. Занумеровать монотонно цепь, соединяющую вершины v ₁  и   v ₂, оставляя под каждое выделяемое поддерево разложения соответствующие диапазоны номеров.

Процедура повторяется до тех пор, пока не будут занумерованы все вершины. 

Пример 5.2.1. Для нижеприведенного дерева одна из возможных минимальных плоских нумераций имеет следующий вид:

 

 

 

Для реализации алгоритма необходимо предварительно вычислить веса веток ко всем вершинам дерева и упорядочить их. Для  произвольного n – вершинного дерева это можно сделать с линейной трудоемкостью O (n), используя дополнительную память объема O (n log n) [12].

Для небольших деревьев с n £ 15 минимум функционала (5.1.1) в классе плоских нумераций совпадает с глобальным минимумом в классе всех нумераций. Для больших значений n минимум в классе плоских нумераций в общем случае не позволяет достичь глобального минимума, достигаемого на нумерациях, которым соответствуют реализации деревьев   - суперпозициями надS, не являющимися каноническими.

Пример 5.2.2. Для следующего дерева t (V, E) с числом вершин n =16 минимальная нумерация не является плоской.

 

минимальная плоская нумерация j          минимальная нумерация j

          26                        25

Оценки длин деревьев

Алгоритм построения минимальной нумерации произвольного дерева имеет сложную рекурсивную структуру с трудоемкостью [13]. Относительно простой алгоритм построения минимальной плоской нумерации можно рассматривать как способ приближенного решения задачи построения минимальной нумерации. В работе [12] показано, что минимум в классе плоских нумераций может превосходить глобальный минимум не более чем в полтора раза.

Каково значение самого минимума, насколько оно отличается, например, от среднего значения функционала (5.1.1) на множестве всех n! нумераций. Оценим минимум сверху через максимальное значение функционала (5.1.1) на множестве всех n – вершинных деревьев при использовании нумераций j Î F ^*.

Геометрическая интерпретация нумераций класса F ^*

Рассмотрим линейную укладку дерева t (V, E), | V |= n соответствующую произвольной нумерации j Î F ^*. Для этого  разместим  вершины дерева вдоль числовой прямой таким образом, чтобы каждая вершина попала в точку с координатой . Выделим вершины, являющиеся концевыми для цепей разложения s _j (V_j, E_j), , и соединим их дугами. Для цепи s _j (V_j, E_j),  номера концевых вершин  обозначим через  и . Каждой цепи s _j (V_j, E_j),   будет соответствоватьотрезок [ , ], . Так как j Î F ^*, то отрезки различных цепей не пересекаются и не имеют общих точек (рис. 5.3.1).

...      ......           

        1                                                                           n

                                          Рисунок 5.3.1

Разобьем множество всех дуг на ярусы. К первому яру­су отнесем внешнюю дугу, соединяющую, очевидно, точки с коорди­натами 1 и n и соответствующую цепи s ₁ (V ₁ , E ₁). Ко второму ярусу отнесем дуги, которые становятся внешними после удаления дуги пер­вого яруса. Они соответствуют цепям, выделяемым в поддеревьях, образующихся после выделения цепи s ₁ (V ₁ , E ₁) и т.д.

Обозначим через q - общее число ярусов, n_i -число цепей i -го яруса,   - цепь, соответствующая k -ой дуге i -го яруса.

Теорема 5.3.1. Для любого дерева t (V, E), | V |= n и нумерации j Î F ^*

  ë n ² /4 û

Доказательство. Поскольку цепи s _j (V_j, E_j),   пореберно не пересекаются, то можно записать рассматриваемый функционал  так

.                              (5.3.1)

Так как нумерация j на каждой цепи  монотонна, то величина   равна длине отрезка [ , ].  Отрезки, соответствую­щие цепям одного яруса, очевидно, не имеют общих точек.   Тогда, учитывал способ разбиения цепей на ярусы, получаем

           .           (5.3.2)

Учитывая, что n_i ³ 1, , q £ ë n /2 û, из (5.3.1) и (5.3.2) следует

n ë n/2 û - ë n/2 û é n/2 ù + ë n/2 û =ë n/2 û é n/2 ù = ë n²/4 û

при n нечетном,

 n (n/2)- (n/2) (n/2+1) + n/2= n/2(n/2-1)+ n/2=n²/4

при n четном.

Таким образом, утверждение теоремы справедливо при любом n.       ð

Подсчитаем среднее значение минимизируемого функционала (5.1.1) для произвольного графа G (V, E), / V /= n на множестве всех n! нумераций - величинуравную

                   (5.3.3)

При последовательном построении n! нумераций на концах любого ребра e Î E каждая пара номеров  побывает 2(n -2)! раз. Длина ребра e принимает при этом значения | i - j | равные  по (n - k) раз. Общий вклад ребра e в числитель выражения (5.3.3) равен

.

Поскольку это верно для произвольного ребра e Î E, то числитель в (5.3.3) равен  и среднее значение длины графа G на множестве всех n! нумераций равно .

Так как в дереве t (V, E), | V |= n число ребер | E |= n -1, то среднее значение длины дерева на множестве всех нумераций равно (n ² -1)/3. Учитывая утверждение теоремы 5.3.1, получаем, что при  значение минимизируемого функционала 5.1.1 на множестве нумераций из класса F ^*, по крайней мере, на четверть меньше среднего значения на множестве всех нумераций. При использовании минимальных нумераций или минимальных плоских нумераций сокращение длины дереваможет быть еще значительнее.

Список литературы

1. Мельников О.И. Занимательные задачи по теории графов. - Минск: НТ ООО "ТетраСистемс", 2001. - 144 с.

2. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. - М.: Наука, 1990. - 384 с.

3. Мальцев И.А.Дискретная математика. - СПб.: Изд-во «Лань», 2011. - 304 с.

4. Перечисление графов / Харари Ф., Палмер Э. – М.: Изд-во «Мир», 1977. – 324 с.

5. Иорданский М.А. Конструктивные описания графов // Дискретный анализ и исследование операций. - 1996. - Т. 3, № 4. - С. 35 - 63.

6. Бурков Е.В. Операционные базисы замкнутых классов графов // Материалы IX международного семинара "Дискретная математика и её приложения" (Москва, 18-23 июня 2007г.). - М.: Изд-во мехмата МГУ. 2007. - С. 105-116.

7. Иорданский М.А. Конструктивная классификация графов // Моделирование и анализ информационных систем. - 2012. - Т. 19, № 4. - С. 144 - 153.

8.  Alon N. Tough Ramsey Graphs Without Short Cycles // Journal of Algebraic Combinatorics. – 1995. – V.4, № 3. – P.189 - 195.

9. Бурков Е.В. Конструктивные описания планарных и эйлеровых графов // Вестник Нижегородского государственного университета. Математика. - 2010. № 5(1). - С. 165 - 170.

10. Иорданский М.А. Конструктивные описания гамильтоновых графов // Вестник Нижегородского государственного университета. Математика. - 2012.,№ 3(1). - С. 137 - 140.

11. Иорданский М.А. Избыточность конструктивных описаний гамильтоновых планарных графов // Материалы XI Международного семинара «Дискретная математика и её приложения» (Москва, МГУ, 18-22 июня 2012 г.) – М: Изд-во механико-математического факультета МГУ. 2012. - С. 285-288.

12. Иорданский М.А Минимальные плоские размещения деревьев // Методы дискретного анализа в решении экстремальных задач. - 1979. выпуск 33. - С. 3 - 30.

13. Chung F.R.K. On optimal linear arrangement algorithm for undirected trees // SIAM J. Comput.- 1984. -V. 8, № 1. - P. 15 - 32.