,

магистрант ИМЭИ ИГУ, e-mail: *****@***com

КОМБИНАТОРНЫЕ АЛГОРИТМЫ ДВОИЧНОГО КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ КОРНЕВЫХ ДЕРЕВЬЕВ

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

Основные определения

Деревом называем связный ациклический граф. Корневым деревом (или деревом с корнем) называем  дерево, в котором выделена одна вершина, называемая корневой вершиной, или просто корнем [5].

Через обозначаем множество корневых деревьев. Дерево представимо в виде матрицы смежности.

Алфавитом ∑ называем конечное непустое множество. Буквами (символами) называем элементы алфавита ∑. Словом над алфавитом ∑ называем конечную цепочку, состоящую из нуля или более букв из ∑, причем одна и та же буква может входить в слово несколько раз [6].

Через обозначаем множество слов над алфавитом со следующими свойствами:

слово всегда начинается с буквы «1», слово всегда заканчивается на букву «0».

Операции

Введем следующие операции над матрицей смежности:

Положим S=«1»,

- посещение j-ой строки матрицы.

- вычисление , где и текущее положение «1» в j-ой строке матрицы.

       (1)

где: , если в строке после позиции есть символ «1» или последняя строка матрицы в противном случае ;

- положение первого символа «1» в столбце выше строки ;

  (2)

- в строку S дописывание символов «0» и один символ «1».

Определим как преобразование матрицы смежности дерева в строку с действиями , и .

НЕ нашли? Не то? Что вы ищете?

,  (3)

где -  количество строк матрицы смежности дерева.

Введем следующие операции над словом:

Положим .

- берем j-ый символ «1».

- вычисляем

  (4)

где: равно единице, если за символом «1» идет символ «1» в исходной строке;

равно двойке, если за символом «0» идет символ «1» в исходной строке;

- положение единицы в строке с номером уже сформированной матрицы;

       (5)

здесь равно количеству символов «1» до текущей позиции в исходной строке;

- количеству символов «0» до текущей позиции в исходной строке;

- количеству символов «0» между текущим и предыдущим символом «1» в исходной строке;

.

- пишем в строку на позицию символ «1», остальные в этой строке символы «0», .

Определим  как преобразование строки в матрицу смежности дерева с действиями , и .

,  (6)

где - количество символов «1» в исходной строке.

Замечание. Преобразования и взаимно обратные.

Все выше сказанное доказывает следующее утверждение.

Лемма 1. Для любого и верны следующие соотношения:

,                (7)

.                (8)

Алгоритмы перевода

На основании леммы 1 и операций и построены следующие алгоритмы перевода в и обратный ему.

Алгоритм 1 перевода в .

Шаг 1. В строку пишем «1»,

Шаг 2. Цикл по матрице.

Шаг 3. Выполняем операцию .

Шаг 4. Выполняем операцию .

Шаг 5. Выполняем операцию .

Шаг 6. Конец цикла.

Шаг 7. В строку S дописываем символов  «0», где , равно количеству символов  «1» в строке , - количеству символов  «0» в строке .

Алгоритм 2 перевода в .

Шаг 1. , , .

Шаг 2. Цикл по строке со второго символа.

Шаг 3. Выполняем операцию .

Шаг 4. Выполняем операцию .

Шаг 5. Выполняем операцию .

Шаг 6. Конец цикла.

Оценка сложности алгоритмов

Сложность  обоих алгоритмов составляет .

Приведем оценки сложности базовых алгоритмов  обработки графов.

Сложность алгоритма поиска кратчайшего пути в графе составляет , где  количество вершин графа.

Сложность алгоритма поиска в глубину на графе составляет, где количество вершин и ребер графа.

Сложность алгоритма поиска в ширину на графе составляет, где количество вершин и ребер графа.

Вывод

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

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. еория графов. Алгоритмический подход. М.: Мир, 1978. – 432 с.

2. омбинаторика для программистов. М.: Мир, 1988. – 214 с.

3. омбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980. – с.

4. скусство программирования, Том 4, А/ Комбинаторные алгоритмы, часть 1 – Москва, 2013 – 963 с.

5. Кузьмин пирамиды Паскаля и их приложения. Новосибирск.: Наука. Сиб. изд. фирма РАН, 2000. – 294 с.

6. Шур слов. – Екатеринбург: Издательство Уральского университета, 2003. – 94 с.

7. Абрасимов расширения дополнений графов // Теоретические проблемы информатики и ее приложений, Вып. 4 – СГУ - Саратов, 2001 – С. 11-19.

8. - Алгоритмы. Построение и анализ. Издание 3. М.: Вильямс, 2013. – 1328 с.

9. Евсевлеева теория графов и молекулярные структуры/ , // Обозрение прикладной и промышленной математики. Т. 17. № 6. 2010. - С. 871-873.