Введение к работе
Актуальность темы.
Графы представляют большой интерес и находят применение в самых разных областях В их числе физика, химия, электроника, экономика, лингвистика, машиностроение и другие Теория графов может служить математической моделью для всякой системы, содержащей бинарное отношение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 в соответствие два (из четырех) инцидентных ребра е\ и ег, которые не принадлежат одной прямой Рассмотрим класс остовных подграфов решётки Каждой вершине подграфа из этого класса поставим в соответствие ячейку матрицы, содержащую символ алфавита, следующим образом Если вершине г; подграфа инцидентны ei и Є2, то записываем в ячейку символ "3", если инцидентно ег, то записываем "2", если еі, то "1", если ни одного, то "О" Когда требуется задавать подграфы решетки с вершинами, имеющими пометки из алфавита Л, можно рассматривать матрицы над алфавитом Л х {0,1,2 3} Таким образом, задачу нахождения подграфа прямоугольной решетки, универсального для некоторого класса графов, можно свести к задаче нахождения универсальной матрицы
В связи с этим в третьей части работы изучается сложность универсальных матриц, которые позволяют получать матрицы заданного класса в качестве подматриц Под сложностью понимаем размер универсальной матрицы
Подобные объекты рассматривались в работах, посвященных циклам, последовательностям и торам де Брейна4 Важное отличие данной работы заключается в том, что разрешается варьирование универсальной матрицы при идентификации подматрицы
Отметим также, что в работах, посвященных данной теме, обычно накла-
4Хоял М Графические методы Последовательности де Брейна. - В кн Комбинаторика - М Мир, 1970, с 128 - 139, de Bruyn N G , A Combmatmal Problem - Proc Nederl Akad Wetensch 49, 1946, p 758-764
дывались более жесткие условия, в частности, требовалась однозначность выделения подматрицы, поэтому получение минимальных универсальных матриц с размерностью три и больше не удавалось5 В отличие от работ, посвященных торам де Брейна, здесь не требуется однозначность выделения матрицы в универсальной матрице и допускается произвольная размерность матриц
Получена лучшая по порядку универсальная матрица Она может представлять интерес при определении топологии универсального реконфигури-руемого чипа
Цель работы.
Целью настоящей работы является изучение сложности схем построения графов при помощи двух операций склейки графов, а также сложности универсальных графов, которые позволяют получать графы заданных классов в качестве подграфов, порожденных подмножествами их вершин При рассмотрении порожденных подграфов допускается некоторое варьирование ребер
Научная новизна.
Основные результаты диссертации являются новыми и состоят в следующем
Получены порядки сложности схем построения некоторых конкретных графов Получен порядок функции Шеннона для сложности схем построения класса деревьев
Получены порядки и асимптотики сложности универсальных графов для некоторых классов помеченных графов Получен порядок также в случае с разрешенным варьированием ребер
В рамках изучения специальных классов графов получен порядок сложности универсальной матрицы произвольной размерности с разрешенным варьированием
5Hurlbert G , Isaak G On tiie de Brmjn torus problem - Journal of Combinatorial Theory, Series A, 1995
Основные методы исследования.
В диссертации использованы методы и результаты теории графов, комбинаторики, математического анализа
Теоретическая и практическая ценность работы.
Диссертация имеет теоретический характер Полученные в диссертации результаты могут быть полезны для специалистов, занимающихся вопросами построения минимальных схем, могут быть интересны при решении задач, связанных со сжатием информации, а также при проектировании чипов
Апробация работы.
Результаты диссертации докладывались на семинарах и конференциях механико-математического факультета МГУ им М В Ломоносова
На семинаре "Теория автоматов" под руководством академика, проф В Б Кудрявцева (2002 - 2007 г),
На семинаре " Элементы кибернетики" под руководством д ф-м н , проф. А С Подколзина (2002 - 2007 г),
На конференции "Ломоносовские чтения" (апрель 2007 г),
На конференции аспирантов кафедры МаТИС (июнь 2005 г)
Публикации автора по теме диссертации.
Основное содержание диссертации опубликовано в трех работах, список которых приведён в конце автореферата [1-3]
Структура и объём диссертации.
Диссертационная работа изложена на 106 страницах и состоит из введения и трёх глав Библиография включает 14 наименований
Похожие диссертации на О сложности сборки и вложения графов.
