Свойства минимальных нумераций

Пусть G (V, E) граф, содержащий n вершин; A ={ a ₁, a ₂,..., a_n }, a_i < a_{i +1}, i =1,2,…, n -1 - множество из n натуральных чисел. Взаимнооднозначное отображение j: V (G) ® A называется нумерацией вершин графа G (нумерацией графа), а множество A – нумерующей последовательностью графа G. Рассматривается функционал

                     (5.1.1)

где суммирование производится по всем ребрам графа G. Любая нумерация, на которой достигается , называется минимальной нумерацией графа G. При решении задачи построения минимальной нумерации достаточно ограничиться рассмотрением связных графов G, поскольку в противном случае задача распадается на несколько независимых подзадач. Из вида минимизируемого функционала (5.1.1) следует, что, не ограничивая общности рассмотрения, можно полагать, что нумерующая последовательность содержит n первых натуральных чисел, т.е. A = { 1,2,..., n }. При этом  не больше, чем при выборе любой другой нумерующей последовательности.

Рассмотрим далее класс деревьев. Для задачи построения минимальной нумерации вершин деревьев в качестве исходных поддеревьев удобно взять цепи s (V, E), для которых эта задача решается наиболее просто.

Лемма 5.1.1. Нумерация j цепи s (V, E) является минимальной тогда и только тогда, когда j монотонна.

Доказательство. Рассмотрим линейную укладку графа s (V, E), разместив вершины цепи s (V, E) вдоль числовой прямой таким образом, чтобы каждая вершина попала в точку с координатой . При этом каждому ребру  будет соответствовать отрезок [ , ]. Из вида функционала (5.1.1) следует, что  равно сумме длин всех таких отрезков. Поскольку наибольшее и наименьшее значения номеров вершин фиксированы, то указанная сумма будет минимальной тогда и только тогда, когда отрезки [ , ], соответствующие различным ребрам, не пересекаются, т.е. когда нумерация монотонна.                                                                                ð

Каждое дерево можно, очевидно, рассматривать как результат объединения пореберно непересекающихся цепей. Для произвольной нумерации j структуру дерева t можно представить следующим образом (рис. 5.1.1). Поддеревья  порождены ребрами, не принадлежащими цепи s (V ₀ , E ₀), соединяющей вершины   и .

       s (V ₀ , E ₀)          

             ...  

Рисунок 5.1.1

Лемма 5.1.2. Если j  минимальная нумерация дерева t { V, E), то:

1) нумерация цепи s (V ₀ , E ₀) монотонна,

2) нумерующие последовательности  поддеревьев  сплошные.

Доказательство. Поскольку множества ребер цепи s (V ₀ , E ₀) и поддеревьев   попарно не пересекаются, то

              .                 (5.1.2)

Предположим, что минимальная нумерация j   не удовлетворяет условиям леммы, т.е. нумерация цепи s (V ₀ , E ₀) не монотонна и (или) найдется хотя бы одно поддерево , нумерующая последовательность которого не является сплошной. Построим по j   нумерацию , удовлетворяющую условиям леммы, что всегда возможно при сплошной нумерующей последовательности всего дерева, и обладающую следующими свойствами.

Вершины  и   совпадают соответственно с вершинами   и , порядок нумерации внутри каждого поддерева  сохраняется неизменным. Аналогично (5.1.2), можно записать

                   .                   (5.1.3)

Учитывая лемму 5.1.1, для нумераций j   и  на цепи s (V ₀ , E ₀) справедливо соотношение

.                (5.1.4)

Из вида оптимизируемого функционала (5.1.1) и способа построения нумерации  по нумерации j  следует что

                             (5.1.5)

Из предположения о нумерации j следует, что в (5.1.4) и (или) в (5.1.5) (хотя бы для одного поддерева) имеет место строгое неравен­ство. Отсюда, сопоставляя (5.1.3) и (5.1.2), получаем

,

что противоречит условию минимальности нумерации j.                                  ð

Следствие 5.1.1. Минимальная нумерацияj дерева t (V, E) является минимальной и на каждом его поддереве , т.е.

.                             (5.1.6)

Любой нумерации j графа G,  можно сопоставить двойственную нумерацию  такую, что . Очевидно, что . Вершины графа степени один будем называть для краткости висячими.

Лемма 5.1.3. Если j минимальная нумерация дерева t (V, E), то вершины   и   являются висячими.

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

Предположим, что вершина   не является висячей. Выделим в t { V, E)   цепь s (V ₀ , E ₀), соединяющую вершины   и , а также поддеревья . Вершине  соответствует поддерево .   Из леммы 5.1.2 следует, что его нумерующая последовательность состоит из чисел 1,2,…, .  Построим нумерацию j ₁, совпадающую с нумерацией j на всехвершинах , а на вершинах  совпадающую с двойственной нумерацией: . При переходе к нумерации j ₁ монотонность нумерации цепи s (V ₀ , E ₀), очевидно, сохранится. Поскольку , то . Так как , то, сравнивая разложения (5.1.2) для нумераций j и j ₁, получаем , что противоречит условию минимальности нумерации j.                                                                                    ð

Из лемм 5.1.2 и 5.1.3, учитывая равенства (5.1.6), получаем

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

1) концевые вершины цепей являются висячими в тех поддеревьях, в которых они выделяются;

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

Все нумерации, в которых можно выделить указанную последовательность цепей, образуют класс нумераций F ^*.

Таким образом, для реализации минимальных нумераций необходимо строить дерево t (V, E) из цепей s _j (V_j, E_j),  путем склейки графов-операндов по O ₁, причем чтобы отождествляемая вершина хотя бы в одном из графов-операндов имела четную степень (операции   - склейки). Пусть S - множество всех простых цепей, тогда для построения минимальной нумерации каждое дерево представляется в виде   - суперпозиции над S. Из леммы 4.1.1 следует, что при этом допустима и каноническая   - суперпозиция над S.