Оптимальное кодирование графов

Пусть Á - некоторый класс графов, Á _{n , m} – подмножество графов из Á, содержащих n вершин и m ребер; B ={0,1}, B ^* -множество слов в алфавите B. Кодированием графов из класса Á   называется семейство взаимно однозначных отображений F = { j _{n , m}: n =1,2,…; m =1,2,…;}, где j _{n , m}: Á _{n , m} ® B ^*. Слово из B ^*, сопоставляемое графу G Î Á _{n , m}, называется кодом графа. Величина | j _{n , m} (G)| - длина кода графа G Î Á _{n , m}. При любом способе кодирования имеет место соотношение

log₂| Á _n,m | £   max(| j _n,m (G)|, G Î Á _n,m ).     (3.4.1)

Для обоснования приведенного соотношения достаточно заметить, что если перечислить в двоичной системе счисления графы из множества Á _{n , m}, то наибольшая длина кодов будет не менее log ₂ | Á _{n , m} |бит. Поскольку коды графов должны обеспечивать еще и возможность их однозначного восстановления, то это в общем случае потребует дополнительного увеличения длины кода.

Если в соотношении (3.4.1) для любых n и m выполняется равенство, то соответствующее кодирование называется оптимальным. Если имеет место

 ,                 (3.4.2)

то кодирование называется асимптотически оптимальным.

Из соотношения (3.4.1) следует, что оценить качество предлагаемого кодирования графов и возможности сокращения длины кода можно, лишь подсчитав или хотя бы оценив мощность множества кодируемых при этом графов.

Подсчет числа (перечисление) графов, обладающих заданными свойствами, представляет собой в общем случае довольно сложную комбинаторную задачу, требующую для своего решения полного изучения структуры перечисляемых графов. С решением этих задач можно познакомиться в [4].

Ограничимся здесь задачами перечисления помеченных графов, вершинам которых приписаны различные метки (например, номера). По всеми рассмотренным выше способам задания графов однозначно восстанавливаются именно помеченные графы, и по каждому помеченному графу однозначно строится его задание (код). Таким образом, разнообразие кодов, а, следовательно, и их наибольшая длина определяются числом различных помеченных графов.

Рассмотрим степень оптимальности кодирования простых неориентированных графов с помощью матриц смежности. Подсчитаем число простых неориентированных графов, содержащих по n вершин. В полном n -вершинном графе n (n -1)/2  ребер. В каждом конкретном графе любое из этих ребер может отсутствовать или присутствовать независимо от других ребер. Поэтому число рассматриваемых графов равно числу всех подмножеств множества, содержащего n (n -1)/2  элементов, т.е. 2 ^{n ( n -1)/2}. Значение log ₂ 2 ^{n ( n -1)/2} = n (n -1)/2, оносовпадает с длиной кода, формируемого по матрице смежности, позволяющего однозначно восстанавливать граф.   Таким образом,  кодирование простых неориентированных графов с помощью матриц смежности является оптимальным и не может быть улучшено на множестве всех таких графов. Если рассматривать не все простые неориентированные графы, а лишь некоторые подмножества, то можно сократить длину кода.

В качестве примера оптимального кодирования подмножества множества всех простых неориентированных n -вершинных графов рассмотрим класс помеченных n - вершинных деревьев. Английским математиком Кэли в середине 19 века была доказана следующая теорема.

Теорема 3.4.1. Число помеченных деревьев с n ³ 2 вершинами равно n^{n -2}.

Доказательство. В задачахподсчета часто используется прием, при котором искомое множество заменяется вспомогательным, число элементов в котором устанавливается достаточно просто, а затем показывается, что исходное и вспомогательное множества равномощны.

В качестве вспомогательного множества рассмотрим множество слов n - буквенного алфавита длины n -2, предложенное немецким математиком Прюфером (эти слова называют кодами Прюфера). Поскольку в каждой из n -2 позиций может стоять любая из n букв, то число таких слов равно n^{n -2}.

Установим, что вспомогательное множество равномощно искомому. Для этого покажем, что каждому помеченному дереву с n вершинами однозначно соответствует код Прюфера и наоборот.

Переход от деревьев к словам

Для построения кода Прюфера достаточно n -2 раза выполнить следующую процедуру:

1. Выберем в текущем (исходном) дереве висячую вершину с наименьшим номером. 

2. Запишем в слово (слева-направо) номер смежной с ней вершины.

3.  Удалим висячую вершину вместе с инцидентным ребром.

Пример 3.4.1.Помеченное 7- вершинное дерево и его код Прюфера

                           

                           ® 57517

                                        

Переход от слов к деревьям

Запишем вспомогательный массив, содержащий числа от 1 до n и выполним n -2 раза следующую процедуру:

1. Удалим из вспомогательного массива минимальное число, которого нет в слове (исходном, а затем в текущем).

2.Удалим из текущего (исходного) слова первый элемент.

3. Составим ребро, концевыми вершинами которого являются вершины с номерами, соответствующими  удаленным числам.

Последнее (n -1) -ребро составляется из двух вершин с номерами, оставшимися во вспомогательном массиве после выполнения n -2 раза предыдущей процедуры. Из всех ребер получаем дерево, отождествляя вершины с одинаковыми номерами.

Пример 3.4.2.Код Прюфера и восстановленное по нему дерево.

73442                                                                          6

n =7        (1,7)(3,5)(3,4)(4,6)(2,4)(2,7) 5  3        2   7 1

1 2 3 4 5 6 7                                                                                 4   

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

Введем обозначения:      b ₁ b ₂ … b_{n -2}   -  код Прюфера;

a ₁ – минимальное число, не входящее в b ₁ b ₂ … b_{n -2} , генерируемое ребро (a ₁, b ₁)

a ₂ – минимальное число, не входящее в b ₂ b ₃ … b_{n -2} , генерируемое ребро (a ₂, b ₂)

...

a_{n -2} – минимальное число, не совпадающее с b_{n -2} , генерируемое ребро (a_{n -2}, b_{n -2})

(a_{n -1}, a_n) – последнее (n -1) - ребро.

Ацикличность конструируемого графа покажем индукцией по числу ребер, перечисляя ребра в порядке обратном их генерации:

1.Граф с одним ребром (a_{n -1}, a_n), очевидно, не содержит циклов.

2. Предположим, что добавление к графу ребер (a_{n -2}, b_{n -2}), …, (a_{n - i}, b_{n - i}) не образует циклов.

3. Покажем, что добавление к графу ребра (a_{n - i -1}, b_{n - i -1}) не сможет образовать цикл в текущем графе. Действительно, учитывая способ генерации ребер, номер a_{n - i -1} не совпадает ни с одним из номеров b_{n - i -1} , b_{n - i}, …, b_{n -2}. Кроме того, числа a_i ¹ a_j при i ¹ j. Таким образом, хотя бы одна из концевых вершин добавляемого ребра (a_{n - i -1}, b_{n - i -1}) не принадлежит уже построенному графу и цикл при этом образоваться не может.  

Связность графа покажем методом от противного. Пусть граф содержит k компонент связности. Каждая из них является деревом, поскольку граф не содержит циклов. При этом число вершин n_i и ребер m_i каждой из k компонент удовлетворяют соотношениям m_i = n_i -1. Просуммировав их, имеем следующие равенство , где  и . Таким образом, получаем, что . Но в построенном графе . Следовательно,  и граф содержит лишь одну компоненту связности.                                              ð

Зная число помеченных n - вершинных деревьев, можно оценить степень оптимальности кода Прюфера. Пусть T_n класс всех n - вершинных деревьев. Для графов, являющихся деревьями, будем пользоваться обозначением t, учитывая (3.4.1), получаем для деревьев соотношение  

log ₂ | T _n | £ max (| j _n (t)|, t Î T _n).

По теореме 3.4.1 имеем | T_n |= n^{n -2} и следовательно log ₂ | T _n | ³ (n -2) ë log ₂ n û. Так как код Прюфера состоит из (n -2) чисел, каждое из которых принадлежит диапазону от 1 до n, то его длина | j _n (t) | £ (n -2) é log ₂ n ù. Объединяя оценки, имеем (n -2) ë log ₂ n û £ log ₂ | T _n | £ max (| j _n (t)|, t Î T _n) £ (n -2) é log ₂ n ù.

При этом предел (3.4.2) равен единице

.

Следовательно, рассмотренное кодирование помеченных деревьев является асимптотически оптимальным. На подпоследовательности n =2 ⁱ, i =1,2,… кодирование является оптимальным.