автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Кодирование графов из наследственных классов

нижегородский государственный университет им. н. и. лобачевского

На правах рукописи ЛОЗИН Вадим Владиславович

КОДИРОВАНИЕ ГРАФОВ ИЗ НАСЛЕДСТВЕННЫХ КЛАССОВ

Специальность 05.13.17 — Теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Нижний Новгород, 1995

Работа выполнена на кафедре математической логики и высшей ал. гебры факультета вычислительной математики и кибернетики Нижегородского государственного университета им. Н. И. Лобачевского.

Научный руководитель — кандидат физико-математических наук, доцент В. Е. Алексеев.

Официальные оппоненты:

доктор физико-математических наук, профессор Р. И. Тышкевич; кандидат физико-математических наук, доцент М. А. Иорданский.

Ведущая организация—Московский государственный университет.

Защита состоится « О- 6 » с^-ОЗигР/_1995 г. в_

час.

на заседании специализированного совета КР 063.43.01 научно-нсследова-тельского института прикладной математики и кибернетики при Нижегородском госуниверситете им. Н. И. Лобачевского по адресу: 603005, Нижний Новгород, ул. Ульянова, д. 10.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного университета.

Автореферат разослан « » _ 1995 г.

Ученый секретарь специализированного совета, доктор технических наук

Ю. Л. Кетков.

общая характеристика работы

Актуальность темы- Вопрос о представлении комбинаторных объектов является главным в проблеме структуризации данных, которая составляет основу любых комбинаторных вычислений. Графы принято относить к наиболее сложным комбинаторным объектам. В диссертации рассматривается проблема представления графов в традиционной для теории кодирования постановке: представление словами в конечном алфавите.

Одним из главных аспектов проблемы кодирования является оптимизация длины кода. При этом выделяют два основных направления исследований данной проблемы.

Первое направление связано с поиском оптимальных представлений для графов из некоторых специальных классов. В диссертации данный вопрос рассматривается для графов из наследственных классов с нулевой энтропией. Алексеевым В.Е. предложен алгоритм универсального кодирования, асимптотически оптимальный для любого наследственного класса с ненулевой энтропией- Однако, асимптотическая оптимальность данного алгоритма не распространяется на классы графов с энтропией равной нулю. Для этих классов известны лишь отдельные примеры оптимальных кодирований. Вместе с тем, семейство этих классов весьма представительно, оно континуально и включает такие известные классы как леса, планарные, интервальные графы и многие другие. Эти классы интересны как с практической, так и с теоретической точек зрения, им посвящена обширная литература. Таким образом, разработка специальных методов кодирования для графов из этих классов представляет собой актуальнр проблему.

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

- г -

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

Цель работы. Целью работы является исследование и разработка методов оптимального кодирования графов из наследственных классов.

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

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

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

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

Апробация работы- Основные результаты диссертационной работы докладывались на семинарах кафедры математической логики и высшей алгебры факультета ВМК ННГУ и 3 отдела НИИ ПК при ННГУ. на Всесоюзных конференциях по теоретической кибернетике (Нижний Новгород, 1988 г., Саратов 1993 г.), на 1-ой Международной конференции "Математические алгоритмы" (Нижний Новгород. 1994 г.). на XVI цикле расширенных заседаний Одесского научно-исследовательского семинара по дискретной математике, посвященного теории графов и гиперграфов (Одесса,1994 г.). на межгосударственной школе-семинаре "Синтез и сложность управляющих систем" (Нижний Новгород, 1994 г.), на 3-ей конкурсной конференции факультета ВМК ННГУ (1995 г.), на 5-ом межгосударственном семинаре по дискретной математике и ее приложениями (Москва, 1995 г.).

Публикации- По теме диссертации опубликовано 8 работ.

Структура и объем работы. Диссертация 'состоит из введения, двр глав и списка литературы. Общий объем работы - 102 машинописные страницы, библиография - 44 наименования.

краткое содержание работы

Во введении дается общая характеристика работы, обзор литературы и приводится список основных понятия и обозначений. В частности, для произвольного класса графов х через ь{х) обозначена энтропия х. Известно, что для наследственных классов энтропия является вещественным числом вида 11(х)=1-\/с{х), где с{х) --натуральный параметр, называемый индексом класса.

Определение . Наследственные классы графов с индексом,

раВНЫМ 1, НаЗЫВаЮТСЯ унитарными.

Первая глава посвящена кодированию графов из унитарных классов. Обозначим через * множество /^вершинных графов из х. Классы графов х и у назовем логарифмически равновеликими, если iog|r| и

iog| у |, как функции от п, равны по порядку, т.е. величина ограничена сверху и снизу положительными константами. Очевидно, логарифмическая равновеликость есть отношение эквивалентности. Классы эквивалентности наследственных классов будем называть ярусами.. Если *>(л) - такая функция, что logiArj и р(п) имеют одинаковый порядок дая всякого х из некоторого яруса, то *>(я) назовем порядковой функцией этого яруса. Порядковая функция не определена однозначно, в каждом конкретном случае выбирается "наиболее простая" функция.

В то время как все неунитарные классы "слипаются" в один ярус с порядковой функцией *>-п. семейство унитарных классов на основе понятия яруса дифференцируется. Структурная характеризация нескольких "нижних" ярусов дана в работах Алексеева В.Е. В частности, там описан ярус с порядковой функцией *>«iogn, названный полиномиальным, и ярус с порядковой функцией р»л, названный экспоненциальным.

В разделе i.1 диссертации предлагаются алгоритмы универсального кодирования и доказывается их асимптотическая оптимальность для этих ярусов (теоремы 1.1 и 1.2).

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

Исследованию факгориального яруса посвящен раздел 1.2 диссертации. Начинается он с систематического описания конечно-определенны) классов факгориального яруса (раздел 1.2.1). Известно, что всякий наследственный класс х может быть описан некоторым множеством запрещенных порожденных подграфов м. Будем называть класс х

конечно-определенным, еСЛИ МН0Ж6СТВ0 М К0Н8ЧН0. ОпрвДвЛЯИЩЭЭ

множество м будем называть - (унитарно) тупиковым, если любое его собственное подмножество определяет неунэтарный класс. Обозначим через семейство унитарных классов, для которых определяющее множество является тупиковым и имеет мощность Теорема i. з, для любого к> з. Теорема 1.4 дает исчерпывающую характеризацию семейства р. Оно конечно и содержит восемь наследственных классов. Семейства я и р бесконечны. В диссертации изучены их конечные подмножества, а именно, описаны все факториальные классы из я и р , определяемые запрещенными подграфами, содержащими не более 4 вершин. Описанию этих классов посвящены теоремы 1.5-1.27. Результатом этого исследования явилось формирование двух структурных понятий. Изучению этих понятий и их применений для оптимального кодирования графов посвящены следующие два раздела.

В разделе 1.2.2 рассматриваются канонические разбиения графов. Обозначим через ve и eg множества вершин и ребер графа о соответственно, ív(v) - окрестность вершины v, для произвольного множества вершин vi<zvg через й обозначено vg\u.

Определение. Множество вершин <и.сvg графа о НаЗЫВаеТСЯ каноническим классом. , 6СЛИ И ДЛЯ ЛЮбОЙ

вершины few справедливо либо N(v)(f¿=et либо ЖТУ^гг-ю:

Множество канонических классов графа g обозначим через лчю. Канонические классы, состоящие более чем из одной вершины, будем называть нетривиальными. Граф. у которого каждый канонический класс тривиален, называется неприводимым.

Лемма 1.1. Если V.t,'Uz<£K(G) и UjyifQ, по UjfL¿z K(G). Лемма 1.2. Если и ,U <¡K(G), и гш гсф то и Ш еk(g).

12 i1 ' Z I1 1 2 i 2

Лемма 1.3. Если У. ,11 <=A'(G), U гШ • У-{Щ > по и Ф •

12 1' 1 2 i11 2 i11 г

Лемма 1.4. Если Ui,U2eK(G) и Ujp.^'Q, то {UyUJ{\BO~0 либо

и у.и Я Ей. 1 2

Определение. Разбиение множества вершин графа в на канонические классы называется каноническим разбиением.

Пусть .....у - каноническое разбиение графа в. Из

леммы 1.4 следует, что для любых классов к, v^wa^j) справедливо либо (Ихю(\ео=0, либо v.xvzeg. Обозначим через граф , для которого и (к.пекг^ тогда и только тогда, когда

vxvseg. Будем говорить, что граф т порождается разбиением w.

i j v

Определение. Граф я называется канонической основой графа g, если существует каноническое разбиение w графа в такое, что я изоморфен г^ и я неприводим.

Теорема 1.2 8 Любые две канонические основы графа изоморфны

В диссертации приводится алгоритм трудоемкости оЦо\*) для поиска канонической основы произвольного графа о.

каноническим числом eco) графа о будем называть порядок его канонической основы. Поскольку граф * не имеет канонических разбиений, то с(в)>г для любого графа в порядка | в\>г. Положим с(£)-о.

Граф G будем Называть 1-каноническим, еСЛИ C(G)<¡, (1,а)-почти каноническим, 6СЛИ G СОДерЖИТ J-КаНОНИЧвСКИЙ ПОрОЖ-

денньш подграф порядка не меньше |с|-ш.

Обозначим через класс всех графов, каждый порожденный подграф которых является u.m)-почти каноническим.

В работе описывается универсальное кодирование ф3 , зависящее от натурального параметра s, и доказывается

Теорема 1.29. <í>s является оптимальным по порядку

кодированием для любого класса m с 1>3, О<n¿S.

В разделе 1.2.3 рассматриваются локально-ограниченные покрытия и их применение для кодирования графов.

Множество графов я.....объединение которых совпадает с в,

называется покрытием в. Множество, содержащее для каждого графа оех одно из покрытий g, будем называть покрытием для х. Пусть х -бесконечный класс графов.

Определение. Покрытие дом сбудем называть локально -ограниченным, 6СЛИ существует ТЭКОв га, ЧТО ДЛЯ КЭВДОГО Графа ОбАГ и

кавдой его вершины у число графов, покрывающих V, не првосходит ш.

ТвОреМа 1.30. Если для класса графой X существует локально-ограниченное покрытие графами из У. где 1ов| У | -0(п1ойп) ,

п

то 1ов| К |«0(п1с^/)),

п

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

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

Пусть &>(у,в) - обыкновенный граф с матрицей смежности л - конечный алфавит. * - натуральное число. \ - отображение

(Ак)2 В {0,1}.

Определение. вершинным кодированием графа о относительно называется отображение V-/, при котором *к (»>(«) ,*>(и))-М (о.и) для любых различных и.иеУ.

Бесконечную последовательность *-{*к1 ^'1,2 — > отображений Ф : (/^-»{0,1} будем называть декодирующей функцией В алфавите А.

Будем говорить, что граф допускает ^-кодирование,

если для некоторого натурального * существует вершинное кодирование р-.у-*лк графа о относительно При этом величину * будем называть размерностью кодирования Р, а множество ю ч-ковом графа о размерности к.

В разделе г ■1 рассматриваются примеры и некоторые свойства вершинных кодирований.

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

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

Последовательность универсальных л'-графов их~ rw * . л= i, 2,... > будем называть асимптотически оптимальной, еСЛИ

niog|ta |

1 • n 1

1 1 m-;-. ,-= 1 .

n-»oo I og ( К I п

Лемма 2.1. Дая всякого наследственного класса X с энтропиен

ii=h(x), отличной от нуля, последовательность универсальных

Х-ерафов UX={UX , л= 1,2, ...} является асимптотически оптимальной в

л. , -

том и только том случае, если |КА^|=2

ИнЪективное отображение <? vg* vh , при котором е изоморфен и<р (vg)>, будем назьвать вложением в вн.

Универсальный граф их^ будем назьвать правильным, если множество его вершин может быть разбито на « классов таким образом, что для любого графа fe* существует такое вложение с в ихп. при котором образы различных вершин принадлежат различным классам. Данное разбиение назовем правильным, а классы правильного разбиения - секторами. Очевидно, не уменьшая общности, можно считать, что каждая сектор порождает в w пустой подграф.

Лемма 2.2. Если для некоторого наследственного класса X с энтропией h=h(X), отличной от нуля , существует асимптотически оптимальная последовательность универсальных Х-графов, тогда для X существует асимптотически оптимальная последовательность правильных универсальных Х-графов.

Лемма 2.г позволяет в дальнейшем при построении асимптотически оптимальных универсальных графов для наследственных классов с ненулевой энтропией ограничиться изучением только правильных универсальных графов.

Композицией классов л* и л* называется класс х=о(/,хг), состояний из всех таких графов, множество вершин которых можно разбить на два подмножества, одно из которых порождает граф из V, а другое - граф из

Пусть х,у - бесконечные наследственные классы графов, г=х)(дг, п.

Лемма 2.з. с(7)»с(«+с(г).

Леммы 2.4 и 2.5 описывают некоторые свойства универсальных двудольных графов, используемых в дальнейшем при построении универсальных графов композиций.

Теорема 2.1 определяет правила построения универсальных графов для композиции л1, а2 ), а теорема 2.2 устанавливает асимптотическую оптимальность этих графов.

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

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

Рассмотрим автомат а=</1,<?,к> с двумя входами, алфавитом л, множеством состояний с и функцией переходов ,р:л2х<м> . симметричной относительно переменных х.уеЛ: Р(х,у, г)*Р(у, х.г) .

Будем говорить, ЧТО СИМВОЛЫ а,/?еЛ неразличимы 0ТН0СИТ8ЛЫЮ автомата а=<л.<?,к>, если Яа,ьг)»Р((1,у,2) для любого уел и любого ■

Функцию у по индукции распространим на (ик)2х<?.

Обозначим через о (<го .</) автомат а, в котором выделено состояние ч еу и множество состояний </с<Л

- 10 -

Для произвольных и <?<=<? определим функцию (/)2ч{0,1} следующим образом:

, м > о

о

1, если ллг, г, <г )€<?

о

.0, если нх. г.ч0)е<7

для любых X, ке/ (Ь»1 ,2, . ..).

Одним из главных вопросов относительно любого способа представления графов является вопрос о его универсальности, т.е. возможности представить произвольный граф.

В разделе 2.3.2 данный вопрос решен для декодирующих автоматов с двумя состояниями о{0,1} и алфавитом произвольной мощности.

Теорема 2.3. Для того, чтобы автомат $2=</4,<?, К> с двумя состояниями и алфавитом из К попарно различимых символов был универсальным, необходимо и достаточно, чтобы для некоторых различных символов а ,/зел при аг«2 выполнялись условия (1), (2), (3), а при К>2 - условия (1), (2):

Р(а,(1,0)*Р(а,р, 1) , (1) /Ча.а.О^а.оМ) , (2)

Р(а,а,г)*Р((3,(1,г), (3).

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

Обозначим через наименьшую размерность кодирования

графа о относительно а; ах (« .

|о| = п

Определение . Автоматы и й2 будем называть экйы-

валентными (С^ча.,), если и (л) = (п) для каждого натурального п.

1 2 12 ,

Пусть о - автомат с функцией переходов р. Обозначим через а

и ют автомата с функциями переходов (х, у, г)=/•(*, у, г) и

, * т

/(х.г.г)^*./.?) соответственно. Очевидно, что да ) =дат) =а.

»

Теорема 2.4.

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

а

о.

а.

а

а

о

/(о, о, ¡г) f^o,í,z) /(1.1.2)

г г г

г г г

г г 1

г г 1

г г 1

г г 1

Теорема 2.5.

Пусть 1-о4.....у - перестановка на множестве а.....а-}.

Определение. Автомат о будем называть симметричным,

если для любой перестановки г и любых ф (*..........ук)

......yí.....у ). и асимметричным - в противном случае.

Теорема 2.6. Автолаты Е^ ,Е*э - симметричные,

С!^, С^,Оа - асимметричные.

Для симметричных автоматов в диссертации получены точные значения функции размерности.

Теорема 2.7. ^ (л)-п-1.

1

По определению значение ^(/0 характеризует размерность кодирования л-вершинных графов относительно а в худаем случае. При кодировании относительно а1, как следует из доказательства

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

Теорема 2.8. Для любого графа в с гйЗ веригинали,

отличного от Р , (С) < л-1. п !и

1

г л

Теорема 2.9. (п)=—.

3 I J

Для асимметричных автоматов получение точных значений функции размерности представляет существенно более трудную' задачу, чем в симметричном случае. Для них в диссертации получены некоторые асимптотические оценки.

Теорема 2.11. (л)>л.

Теорема 2.12. (л)<л.

4

Определим /?(<?) как минимальное число классов в таком разбиении множества вершин графа о, при котором каждый класс является кликой либо независимым множеством. Положим д(л)-тах .

|0(=П

Утверждение теоремы 2.12 является следствием следующих лемм.

л

ЛеММа 2.9. Р(п)<а--, где а - константа.

1о8П

к-1

Лемма 2.10. Вели К(С)<к, то 1^ <.0<п—^-+ск (с - константа)

4

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

..........V7!.....V- гда

Вершинное кодирование р графа о будем называть линеиныл, если

1р(/)1=с/ для любой вершины ¿еус, где с - константа-

Автомат о будем называть лшешыл, если дай любого графа о существует линейное кодирование в относительно о.

Теорема 2.13. Все автоматы представленные 6 таблице , кроме Оа, являются линейными.

Основные результаты работы

1. Описаны алгоритмы универсального кодирования, асимптотически оптимальные для полиномиальных и экспоненциальных классов графов.

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

3. Установлено существование в классе вершинных кодирований асимптотически оптимальных представлений и описано бесконечное семейство таких кодирований.

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

5. Получены оценки размерности кодирования относительно универсальных декодирующих автоматов с двоичным входным алфавитом.

Основные результаты диссертации опубликованы в следующих работах:

1 . Лозин В. В. Вершинное кодирование графов при автоматном декодировании // Комбинаторно-алгебраические методы в прикладной математике. - Горький, 1986. - С.73-83

2. Лозин В. В. О /г-значном кодировании графов// Проблемы теоретической кибернетики. Тезисы докладов УЩВсесоюзной конференции (июнь 1988г. -Горький, 1988.

3. Лозин В. В. О кодировании графов в к-значном алфавите// Комбинаторно-алгебраические методы в дискретной оптимизации. ■^Нижний Новгород, 1091.-С. 80-95

4. Лозин В. В. Асимптотически оптимальные универсальные графы// Методы и системы техн. диагностики.-Саратов,1093.-С. 112-114

5. Лозин В. В. Канонические разбиения графов и их применение для кодирования графов// Сибирский журнал исследования операций. -1994. -1, N3. -С. 49-39

6. Лозин В. В. Сжатые кодирования графов// Труды 1-ой Международной конференции "Математические алгоритмы'Чавгуст 1994г. ).-Нижний Новгород, 1994.

7. Лозин В. В. О кодировании графов из факториальных классов (тезисы доклада школы-семинара "Синтез и сложность управляющих систем", Нижний Новгород, 1994)// Дискретный анализ и исследование операций. -1995. -2, №.. -С. 76-77

8. Лозин В. В. Локально-ограниченные покрытия и кодирование графов//Вестник Нижегородского университета. Спец. выпуск. -1995

Автор выражает искреннюю признательность научному руководителю кандидату физико-математических нар доценту Алексееву В.Е. за внимательное отношение и помощь в работе.