О сложности сборки и вложения графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Московский государственный университет имени М В Ломоносова

Механико-математический факультет

На правах рукописи УДК 519 714 6

Зайцев Денис Владимирович

О сложности сборки и вложения графов

01 01 09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертация на соискание ученой степени кандидата физико-математических наук

(

Москва 2008

003171728

Работа выполнена на кафедре Математической теории интеллектуальных систем Механико-математического факультета Московского государственного университета имени М В Ломоносова

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

профессор Александр Сергеевич Подколзин

Официальные оппоненты доктор технических наук,

профессор Александр Борисович Фролов, кандидат физико-математических наук, доцент Алексиадис Никое Филиппович

Ведущая организация

Тверской государственный университет

Защита диссертации состоится 20 июня 2008 года в 16 часов 40 минут на заседании диссертационного совета Д 501 001 84 при Московском государственном университете им M В Ломоносова по адресу 119991, Российская Федерация, Москва, ГСП-1, Ленинские горы, Московский государственный университет имени M В Ломоносова, Механико-математический факультет, аудитория 14-08

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание, 14 этаж)

Автореферат разослан 20 мая 2008 года

Д 501 001 84 при МГУ

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

профессор

Ученый секретарь диссертационного совета

А О Иванов

Общая характеристика работы. Актуальность темы.

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

Многие практические задачи связаны с необходимостью экономить ресурсы Традиционными целями являются экономия времени и экономия занимаемого места В связи с этим возникает интерес к проблеме задания графов с минимизацией определенных затрат В диссертации рассматривается два подхода к заданию графов

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

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

*Харари Ф , Теория графов - М Мир, 1973, 300 с

2Яблонский С В Введение в дискретную математику - М Высш шк , 2002, 384 с

3В англоязычной литературе используется термин mduced-universal graph см , например, Alstrup S , Rauhe Т Small Induced-Universal Graphs and Compact Implicit Graph Representations - Annual Symposium on Foundations of Computer Science Vol 43, IEEE Computer Societu Press, 2002, p 53-62

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

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

Подграфы решетки можно задавать матрицами Кратко поясним идею такого задания на примере прямоугольной решетки на плоскости Пусть у нас есть алфавит из четырех символов {0,1,2,3} Рассмотрим вершину решетки V, которая инцидентна четырем рёбрам Поставим данной вершине V в соответствие два (из четырех) инцидентных ребра е\ и ег, которые не принадлежат одной прямой Рассмотрим класс остовных подграфов решётки Каждой вершине подграфа из этого класса поставим в соответствие ячейку матрицы, содержащую символ алфавита, следующим образом Если вершине г; подграфа инцидентны е\ и ег, то записываем в ячейку символ "3", если инцидентно ег, то записываем "2", если ел, то "1", если ни одного, то "О" Когда требуется задавать подграфы решетки с вершинами, имеющими пометки из алфавита Л, можно рассматривать матрицы над алфавитом Л х {0,1,2 3} Таким образом, задачу нахождения подграфа прямоугольной решетки, универсального для некоторого класса графов, можно свести к задаче нахождения универсальной матрицы

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

Отметим также, что в работах, посвященных данной теме, обычно накла-

4Холл М Графические методы Последовательности де Брейна. - В кн Комбинаторика - М Мир, 1970, с 128 - 139, <3е Вгиуп N в , А СотЪтаЬта} РгоЫеш - Ргос Хес1ег1 Ака<1 \\НепзсЬ 49, 1946, р 758-764

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

Получена лучшая по порядку универсальная матрица Она может представлять интерес при определении топологии универсального реконфигури-руемого чипа

Цель работы.

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

Научная новизна.

Основные результаты диссертации являются новыми и состоят в следующем

1 Получены порядки сложности схем построения некоторых конкретных графов Получен порядок функции Шеннона для сложности схем построения класса деревьев

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

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

5Hurlbert G , Isaak G On tiie de Bnxyn torus problem - Journal of Combinatorial Theory, Senes A, 1995

Основные методы исследования.

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

Теоретическая и практическая ценность работы.

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

Апробация работы.

Результаты диссертации докладывались на семинарах и конференциях механико-математического факультета МГУ им М В Ломоносова

1 На семинаре "Теория автоматов" под руководством академика, проф В Б Кудрявцева (2002 - 2007 г),

2 На семинаре " Элементы кибернетики" под руководством д ф-м н , проф. А С Подколзина (2002 - 2007 г),

3 На конференции "Ломоносовские чтения" (апрель 2007 г),

4 На конференции аспирантов кафедры МаТИС (июнь 2005 г)

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

Основное содержание диссертации опубликовано в трех работах, список которых приведён в конце автореферата [1-3]

Структура и объём диссертации.

Диссертационная работа изложена на 106 страницах и состоит из введения и трёх глав Библиография включает 14 наименований

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

Диссертация состоит из введения и трех глав Во введении даются необходимые определения и формулируются основные результаты работы

Вспомогательные определения.

Пусть 1р(п) и ф(п) - вещественные положительные функции от натуральной переменной п

Положим </з(п) ^ ф{п) при п —> +оо, если существует константа С ^ 1 и существует N такие, что при любом п ^ N выполнено ¡р(п) ^ Сф(п) Говорим, что 1р(п) по порядку меньше или равна ^(п)

Положим 1р(п) ж ■ф{п) при п —► +оо, если одновременно ¡р(п) & ф(п) и ■ф(п) ^ 1/>(п) при п +оо Говорим, что </>(п) и т/)(п) равны с точностью до порядка

Положим <р(п) < ф{п) при тг —> +оо, если для любого е > 0 существует N такое, что при любом п^ N выполнено ¡р(п) < (1 + е)1р(п) Говорим, </з(п) асимптотически меньше или равна -0(п)

Положим <р(п) ~ 1р(п) при п —» +оо, если (р(п) < ф{п) и ф(п) < </з(п) при п —> +оо Говорим, что </э(п) асимптотически равна ф(п)

Глава 1.

В первой главе изучается сложность схем построения графов

Пусть 0 - класс неориентированных связных графов без петель и кратных ребер Пусть й €

Определим две операции склейки графов Двуместная операция склейки 0\ - отождествление двух заданных вершин пары графов, не имеющих общих элементов Одноместная операция склейки О2 - отождествление двух заданных вершин одного графа Всегда производится удаление петель и кратных ребер

Сборкой графа б назовем конечную последовательность графов 0\, (?2, , От, удовлетворяющую следующим условиям Во-первых, От изоморфен б, и Сг состоит из пары вершин, соединенных ребром Во-вторых, каждый граф 03 (1 < й ^ Т) в последовательности получен в результате применения одной операции склейки следующим образом одноместная операция применяется к графу изоморфному одному из бь ,<3«-ъ двуместная операция склейки применяется к паре графов, каждый из которых изоморфен одному из С?1, То есть каждый новый граф склеен из изоморфных

предыдущим В-третьих, потребуем, чтобы каждый граф (кроме (?х) использовался, то есть участвовал в получении хотя бы одного графа с большим номером в данной последовательности

Пусть длина последовательности сборки С - количество операций склейки, затраченных для построения последовательности, то есть Т — 1

Назовем последовательность сборки в минимальной, если данная последовательность имеет наименьшую длину среди последовательностей сборки графа С

Сложностью Х/(б) сборки С назовем длину минимальной последовательности сборки С

Введем функции Шеннона, характеризующие сложность класса графов Пусть Ьд{п) — тах Ь(<3) - максимальная сложность в классе графов с п |0|=п

вершинами Обозначим через О подкласс деревьев в классе графов С? Пусть Ьр(п) = шах Ь(С) - максимальная сложность в классе деревьев с п вершинами

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

Пусть К-рр - полный двудольный граф с р вершинами в каждой доле, Кп - полный граф с п вершинами

Теорема 1. Имеет место Ь(КМ) х р при р —» +оо

Теорема 2. Имеет место Ь(Кп) х п при п —» -Ьоо

Теорема 3. Имеет место ^ Ьа(п) £ — при п —> -Ьоо

Ю£3 П » \ / у/Ъ&х п

Теорема 4. Имеет место Ьц{п) х при п —> +оо Глава 2.

Во второй главе изучается сложность универсальных графов

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

Пусть и £ IV - некоторый граф с N вершинами Для любого подмножества М вершин графа и порожденным6 (индуцированным) подграфом (М) называется подграф графа С?, у которого множество вершин совпадает с Л/, а множество ребер состоит из всех ребер графа и, обладающих концами из М Иначе говоря, две вершины из М смежны в (М) тогда и только тогда, когда они смежны в и

Пусть задан некоторый класс графов V С IV, в графах которого разные вершины имеют разные пометки Будем рассматривать два вида универсальности графов Договоримся обозначать универсальность первого вида одним

"Харари Ф , Теория графов - М Мир, 1973, 300 с

штрихом, второго - двумя Граф и' Е Ш называется универсальным для класса V, если он обладает следующим свойством' для любого графа С из класса V можно указать подмножество вершин М графа (/' такое, что этим подмножеством порождается граф (М) изоморфный графу С Теперь определим универсальность графа второго вида, которую будем называть также А-универсальностью Пусть т — \М\, и пусть Л - целое число такое, что 0 ^ ^ А {С т(™~1) Пусть Ем - подмножество множества неупорядоченных пар различных вершин из М, \Ем\ — А Ем определяет места, где можно добавлять ребра после задания М Граф и" называется А-универсальным для класса V, если для любого графа С? £ К существует подмножество вершин М графа и" и подмножество Ем такие, что в порожденный граф (М) достаточно добавить не более А ребер, чтобы граф (М) стал изоморфным (5, причем пары концов этих ребер должны принадлежать Ем Изоморфизм графов рассматривается с учетом пометок вершин

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

Пусть К С V - класс т-вершинных неориентированных графов, у которых вершины помечены числами из множества {1,. ,т} Обозначим через Дйг(т) сложность задания класса К с помощью универсального графа первого вида Обозначим через А) сложность задания класса К с помощью А-универсального графа

Пусть Т С V - класс т-вершинных неориентированных помеченных деревьев с пометками из множества {1, , т} Обозначим через Агт(т) сложность задания класса Т универсальным графом первого вида

Теорема 5 Для любого тп > 0, верно

а) при тп нечетном для класса К можно построить минимальный универсальный граф и Мк(т) = т2г15~,

б) при т четном для класса К можно построить минимальный по порядку универсальный граф и Л^(т) х то2? при тп —*■ +оо

Теорема 6 Для любых целых тп и X таких, что 0 < т, 0 ^ А ^

для класса К можно построить минимальный по порядку А-универсальный граф и'к и Мк{т, А) х при ш —> +оо

Теорема 7. Для любого тп > 0, для класса Т можно построить асимптотически наилучший универсальный граф и'Т и Лгу(т) ~ т2 при т —► +оо

Глава 3.

В третьей главе изучается сложность универсальных матриц

Пусть задано конечное непустое множество А, которое будем называть алфавитом Обозначим через А мощность алфавита А Можно считать, что наш алфавит состоит из чисел А — {О, ,А — 1}

Словом над А назовем конечную последовательность символов алфавита А Пусть а - слово над А Будем задавать а так а = а^, , ап, где а\ 6 А а„ £ А

Длина слова - число вхождений букв из А

Конкатенация двух слов а = а\, , ат и Ь = Ьх, , Ьп - слово с = аЬ —

Обозначим через Л слово, удовлетворяющее для любого слова а соотношениям Ла = аЛ = а Будем называть Л пустым словом Длина Л равна нулю

Назовем Ь подсловом а, если а можно получить конкатенациями слова Ь с некоторыми словами с\ и сг так а = с\асч

Пусть Р — {1, , п} ~ начальный отрезок натурального ряда Конечная последовательность а - это отображение начального отрезка натурального ряда Р в алфавит А, а {1, , п} —► А

Пусть заданы Р\, ,РГ, где Рг = {1, ,п1} - начальные отрезки натурального ряда г-мерная матрица М размера т^, пГ над А это отображение М РгХ х РТ —> А

Обозначим набор размеров г-мерной матрицы щ, , пг через п Число вхождений букв из А в щ, ,пг-матрице М обозначим через У{М) Величину У(М) также будем называть числом элементов матрицы или объемом по аналогии с длиной слова У(М) — Ул = щ пт

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

Введем конкатенацию двух матриц по выбранному г-тому (1 ^ г < г) направлению Рассмотрим щ, , пи п,+1, , пг-матрицу М и щ

п,_1 п[,пг+1, ,пг-матрицу М' Для конкатенации двух матриц размеры матриц должны быть согласованы Рассмотрим матрицу М" размера "ь + п'г,п1+1, ,пг Для удобства будем говорить о строках Ко-

гда задано направление, не важно, как называть последовательности элементов заданного направления в матрице размерности г. Итак, назовём матрицу М" конкатенацией матриц М и М' по г-тому направлению, если одномерные строки г-го направления матрицы М" представляют собой конкатенации соответствующих строк г-го направления матриц М и М'. Формально можно записать это следующим образом Пусть для любого к такого, что 1 ^ к ^ г и к г, ]к принимает значения от 1 до щ Получаем строку матрицы М" с индексами ]и , , о1+1, , > так

а31, Л-1.1,Л+1, Л-'

>а31, Л-1ДЛ+1, Л-! •

Конкатенация матриц по фиксированному направлению ассоциативна

Назовем матрицу М\ размерности г подматрицей (или блоком) матрицы М размерности г, если существует такой набор матриц {Мх, , М2Г+х} размерности г, что М можно получить в результате конкатенации следующего вида

М = (М2г (М4(М2М1Мз)М5) М2г+1),

где применяются конкатенации по направлениям 1 , г в соответствующих скобках

Расположение подматрицы определяется расположением начального элемента этой подматрицы в матрице

Пусть заданы переменные , Хк, принимающие значения из алфавита А Рассмотрим матрицу, в которой зафиксировано к непересекающихся подмножеств элементов Элементы каждого подмножества принимают значение соответствующей переменной Подмножества могут иметь разное число элементов и могут быть пустыми Будем называть элементы таких подмножеств переключателями, зависящими от соответствующей переменной

Класс матриц над алфавитом А с переключателями от переменных Хи ,ц обозначим через С(А,хх, ,Хк)

Будем говорить, что М вкладывается в матрицу 17 е С (А, х\, , ху) (или и порождает М), если существует такой набор значений переменных XI, ,Хк, что М является подматрицей 17

Обозначим класс щ , пг-матриц над алфавитом А через Ся Универсальная матрица для класса Сл - это такая матрица II € С(А,х\ , х^) что любая матрица М из класса Сп вкладывается в 17

Пусть Тк(Сп) С С (А, хи , Хк) - множество универсальных матриц для класса матриц Ся

Минимальная универсальная матрица II для данного класса матриц Сп -это универсальная матрица из Т&(СЙ), имеющая наименьшее число элементов

Сложностью вложения класса матриц Сд в универсальную матрицу из Тк(Сй) назовём число элементов в минимальной универсальной матрицей 6 е Тк(Сц) Обозначим сложность через Ьс{п к)

Пусть п , пг>а = п., - последовательность наборов натуральных чисел, задающих размеры г-мерных матриц Пусть к3 - последовательность натуральных чисел, задающих число переменных

Теорема 8. Для любого алфавита А, для любой размерности г, если а) Уй, +оо,

в) Уг (1 ^ г < г) пм > 2

при й —» +оо, то имеет место Ьс(пе, к3) ж \А\хг*>~к'

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

Благодарности.

Автор выражает глубокую благодарность научному руководителю доктору физико-математических наук, профессору Александру Сергеевичу Подкол-зину за постановку интересных задач, заведующему кафедрой Математической теории интеллектуальных систем академику, профессору Валерию Борисовичу Кудрявцеву за внимание и помощь Автор выражает благодарность коллективу кафедры за рабочую атмосферу и поддержку

Работы по теме диссертации

[1] Зайцев Д В О сложности сборки полных и полных двудольных графов - Дискретная математика Т 20, №2 - М , 2008, с 89

[2] Зайцев Д. В О сложности сборки графов - Интеллектуальные системы. Т 9, вып 1-4 - М , 2005, с 381 - 395

[3] Зайцев Д В О сложности вложения графов - Интеллектуальные системы Т И, вып 1-4 - М , 2007, с 473 - 492

Издательство ЦПИ при механико-математическом факультете МГУ им М В Ломоносова

Подписано в печать ¿?5~. О В Формат 60x90 1/16 Уел печ л 0,7Ь Тираж /ОС экз Заказ £0

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

Введение

1 О сложности сборки графов

1.1 Порядки сложности сборки полного двудольного и полного графов.

1.2 Оценки функции Шеннона для класса 0.

1.3 Порядок функции Шеннона для класса деревьев.

2 О сложности вложения графов

2.1 Сложность вложения графов класса К.

2.2 Порядок сложности Л-вложения графов класса К.

2.3 Асимптотика сложности вложения графов класса Т.

3 О сложности вложения матриц

3.1 Порядок сложности вложения матриц.

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

Многие практические задачи связаны с необходимостью экономить ресурсы. Традиционными целями являются экономия времени и экономия занимаемого места. В связи с этим возникает интерес к проблеме задания графов с минимизацией определённых затрат. В диссертации рассматривается два подхода к заданию графов.

В первом подходе изучается сложность схем построения графов при помощи двух операций склейки вершин, которые заключаются в отождествлении пары вершин с удалением петель и кратных ребер. Первая операция применяется к паре вершин одного графа, вторая - к паре вершин двух графов, не имеющих общих элементов. В качестве простейшего берется граф, состоящий из пары вершин, соединённых ребром. Любой промежуточный результат, т. е. построенный на каком-то этапе граф, разрешено использовать неоднократно. Под сложностью схемы понимается число применений операций над графами. Схемный подход к заданию графов уже рассматривался ранее, например, в работе С.В. Яблонского [7], но в ней не изучался вопрос о сложности схемы построения графов, и использовались другие операции. В этой работе получены порядки сложности схемного задания для полного двудольного и полного графа. Получен порядок функции Шеннона для класса деревьев. Также получена асимптотика логарифма функции Шеннона для класса неориентированных связных графов, в которых нет петель и кратных рёбер.

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

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

Подграфы решётки можно задавать матрицами. Кратко поясним идею такого задания на примере прямоугольной решётки на плоскости. Пусть у нас есть алфавит из четырёх символов {0,1,2,3}. Рас

В англоязычной литературе используется термин induced-universal graph [8], [12]. смотрим вершину решётки у, которая инцидентна четырём рёбрам. Поставим данной вершине у в соответствие два (из четырёх) инцидентных ребра е\ и ег, которые не принадлежат одной прямой. Рассмотрим класс остовных подграфов решётки. Каждой вершине подграфа из этого класса поставим в соответствие ячейку матрицы, содержащую символ алфавита, следующим образом. Если вершине г; подграфа инцидентны е\ и б2, то записываем в ячейку символ "3", если инцидентно б2, то записываем "2", если е^ то "1", если ни одного, то "О". Когда требуется задавать подграфы решётки с вершинами, имеющими пометки из алфавита А, можно рассматривать матрицы над алфавитом Ах {0,1.2,3}. Таким образом, задачу нахождения подграфа прямоугольной решётки, универсального для некоторого класса графов, можно свести к задаче нахождения универсальной матрицы.

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

Подобные объекты рассматривались в работах, посвященных циклам, последовательностям и торам де Брёйна [6], [9], [11]. Важное отличие данной работы заключается в том, что разрешается варьирование универсальной матрицы при идентификации подматрицы.

Отметим также, что в работах, посвященных данной теме, обычно накладывались более жёсткие условия, в частности, требовалась однозначность выделения подматрицы, поэтому получение минимальных универсальных матриц с размерностью три и больше не удавалось [11]. В отличие от работ, посвященных торам де Брёйна, здесь не требуется однозначность выделения матрицы в универсальной матрице и допускается произвольная размерность матриц.

Получена лучшая по порядку универсальная матрица. Она может представлять интерес при определении топологии универсального ре-конфигурируемого чипа.

Основные определения и результаты.

Пусть (f(ri) и ф(п) - вещественные положительные функции от натуральной переменной п.

Положим ср(п) ^ ф(п) при п —> +оо, если существует константа С ^ 1 и существует N такие, что при любом п^ N выполнено ip(n) ^ ^ Сф(п). Говорим, что (f(n) по порядку меньше или равна ф(п).

Положим (р(п) х ф(п) при п —► +оо, если одновременно ip(n) ^ &ф(п) и ф(п) при п —► +оо. Говорим, что </?(п) и ф{п) равны с точностью до порядка.

Положим ip(n) < ф(п) при п —> +оо, если для любого е > 0 существует N такое, что при любом п^ N выполнено (р{п) ^ (1 + £)ф{п). Говорим, ip(n) асимптотически меньше или равна ф(п).

Положим (f(n) ~ ф(п) при п —¥ +оо, если у?(п) < ф(п) и ф(п) < < <р(п) при п —¥ +оо. Говорим, что ifi(n) асимптотически равна ф(п).

1. Зыков А.А. Основы теории графов. - М.: Наука. Гл. ред. физ.-мат. лит., 1987, 384 с.

2. Коршунов А.Д. О числе неизоморфных подграфов в п-вершинном графе. Математические заметки. Т. 9, № 3, - М., 1971, с. 263 -273.

3. Уилсон Р. Введение в теорию графов. М.: Мир, 1977, 208 с.

4. Харари Ф., Теория графов. М.: Мир, 1973, 300 с.

5. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. 327 с.

6. Холл М. Графические методы. Последовательности де Брёйна. -В кн.: Комбинаторика. М.: Мир, 1970, с. 128 - 139.

7. Яблонский С.В. Введение в дискретную математику. М.: Высш. шк., 2002, 384 с.

8. Chung F. R. K., Graham R. L. On Graphs which Contain All Small Trees. ~ Journal of Combinatorial Theory Series, Series B, 1978, p. 14 23.

9. Hurlbert G., Isaak G. On the de Bruijn torus problem. Journal of Combinatorial Theory, Series A, 1995.

10. Lozin V., Rudolf G. Minimal Universal Bipartite Graphs. RUTCOR-Rutgers Center for Operations Research RRR 1, 2005.Работы автора по теме диссертации.

11. Зайцев Д. В. О сложности сборки полных и полных двудольных графов. Дискретная математика. Т. 20, №2 - М., 2008, с. 72 - 89.

12. Зайцев Д. В. О сложности сборки графов. Интеллектуальные системы. Т. 9, вып. 1-4. - М., 2005, с. 381 - 395.

13. Зайцев Д. В. О сложности вложения графов. Интеллектуальные системы. Т. 11, вып. 1-4. - М., 2007, с. 473 - 492.