Введение к работе
Актуальность чвиа диссертации. Диссертационная работа относится к тому разделу теории графов, в котором граф представляется как производная структура от другого математического объекта (корня). Наличие соответствующего представления нередко означает, что рассматриваемый граф обладает рядом "полезных" дополнительных свойств. С другой стороны, производный граф несет некоторую информации о корне, поскольку этот граф служит в данной ситуации инвариантом корня.
Один из естественных подходов к исследованию теоретико-графовых инвариантов заключается в следующем.
Пусть G - граф порядка n, a 1(G) - некоторый список эго инвариантов. Это могут быть степенная последовательность, эписок n-1-вершинных порожденных подграфов графа С, список окружений вершин етого графа или что-либо другое. Возникают следующие две проблемы:
-
Реализуемость. Задан список I. Является ли он эеализуемым, т.е. существует ли такой граф G, что I = 1(G)?
-
Единственность. При каких условиях равенство 1(G) = I(G ) влечет изоморфизм С a G ?
В одной из недавних работ Айгнера и Триша (1994) юдчеркивается важность исследования графов и их инвариантов по тсазанной выше схеме.
Значения функции I - "реберный граф" являются инвариантами, определенными на множестве всех гиперграфов без изолированных :ершин. При этом каждый граф является реберным для некоторого иперграфа (Марчевский, 1945). Поэтому, оставаясь в рамках риведенной выше схемы, естественно фиксировать какое-либо еоретико-гиперграфовое свойство Р и рассматривать две следующие роблемы:
1. Реализуемость. Задан граф G. Существует ли гиперграф
е Р, такой что G = Ь(Н)?
2. Единственность. При каких условиях равенство
(Н ) = Ь(Н ), Н , Н« Р, влечет изоморфизм На Н ?
Диссертация посвящена главным образом решению задачи
реализуемости.
Л.Ловас (1977) выдвинул задачу характеризации класса I реберных графов гиперграфов ранга не выше трех, положив тем самъ начало исследованиям задачи реализуемости для свойства Р - "быа гиперграфом ранга не выше г" при г а 3.
Известно, что класс 1 при любом г а 3 нельзя охаракте
ризовать конечным списком запрещенных порожденных подграфов. I
о спасает в этом случае и сужение L до класса L графов, имеквд
г г
линейные корни ранга не выше г.
Р.Н.Найк, С.Б.Рао, С.С.Шрикханд и Н.М.Сингхи (1980, 1982
о получили конечные характеризации графов из L при условии, чі
степени вершин (или ребер) рассматриваемых графов достатош велики. Эти конечные характеризации свидетельствуют а решаемое^ проблемы Ловаеа и аналогичных проблем для г г 4 при подходящ? выборе релаксирущего условия.
В диссертации результаты Найка и др. (1982) существен! улучшены и перенесены на реберные гиперграфы. Кроме тоге решены задачи реализуемости при других релаксирующих условиях.
Связь работы с крупными научными програшами, темами. Рабо-над диссертацией проводилась на кафедре уравнений математичесю физики Белорусского государственного университета в соответствз с темой "Методы и алгоритмы комбинаторной оптимизации вычислительной геометрии" в рамках Государственной програмі фундаментальных исследований Республики Беларусь "Методы алгоритмы вычислительной и дискретной математики (Алгоритм (Головная .организация .- Институт, математики АН Беларуси).
Диссертационная работа является частью плановой госбюджет» НИР 1.1.16 "Структурный анализ графов, гиперграфов и булеві
функций" (No гос. регистрации 19951144).
о Цель и задачи исследования. Как отмечалось выше, класс 1
может быть охарактеризован конечным списком запрещена: порожденных подграфов. Целью работы является получение подоби конечных характеризации графов втого класса при следукщ релаксирующих условиях: "иметь достаточно высокие степе, вершин", "быть расщепляемым графом".
Задачи исследования:
1. Исследовать возможность характеризаций графов из
* конечным списком запрещенных порожденных подграфов в классе
чзафов с минимальной степенью вершин менее 69.
2. Подтвердить или опровергнуть гипотезу, выдвинутую Найком
Л [ др. (1982): для любого целого с классы Ь , г г 4, нельзя оха-
У*
зактеризовать посредством конечных списков запрещенных порождении подграфов в классе графов со степенями вершин не ниже с.
3. Исследовать возможность получения аналогичных результатов
(ля гиперграфов из классов
г I.
4. Охарактеризовать графы из L и L посредством конечных
г Г
писков запрещенных порожденных подграфов в классе расщепляемых рафов.
5. Разработать алгоритмы распознавания классов реберных
иперграфов линейных гиперграфов ограниченного ранга.
Научная новизна полученных результатов. Научная новизна езультатов диссертации обусловлена следующим. Впервые получены .онечные списки запрещенных порожденных подграфов, арактеризующие графы из І в классе графов со степенями вершин
е ниже 19 и в классе расщепляемых графов, а также доказано
L уществование подобных конечных характеризаций для графов из L в
г А. лассе расщепляемых графов при любом г. Полученные для классов L
езультаты в случае ограничений на степени вершин перенесены на
еберные гиперграфы. Разработаны полиномиальные алгоритмы
аспознавания некоторых классов реберных гиперграфов линейных
иперграфов ограниченного ранга.
Практическая значимость полученных результатов. Полученные в иссертзционной работе конечные списки и алгоритмы поставляют
Эффективные необходимые и достаточные условия для вхождения
А. рафов в исследованные в етой работе классы L . Граф, априори
ринадлежащийвтому классу, обладает рядом "полезных" свойств. В
астности, полный список максимальных клик такого графа может
ать построен за полиномиальное время. Последнее важно для
громного количества теоретических и прикладных задач теории
рафов.
Экономическая значимость полученных результатов. Экономическую значимость разработанных в диссертации методов і алгоритмов оценить в настоящее время не представляется возможным.
Основные положения диссертации, выносимые на защиту.
1. Получены конечные списки запрещенных порожденные
подграфов, характеризующие:
графы из І в классе графов со степенями вершин не ниж< 19;
графы из L и L в классе расщепляемых графов.
3. г
2. Подтверждена гипотеза Найка и др. (1982) о невозможное!]
Ь аналогичной характеризации для графов из L при г г 4 для любоп
целого с, ограничивающего снизу степени вершин рассматриваемы: графов.
3. Получены список и теоремы, обобщающие приведенные выш<
результаты (со степенными ограничениями) для реберны:
гиперграфов.
4. Доказано существование рассматриваемой конечно:
j характеризации для графов из І в классе расщепляемых графов пр:
любом г.
5. Приведен аналог теоремы Уитни об изоморфизмах реберны
і, графов простых графов для расщепляемых графов из I» , г а 3
тлеющих достаточно большую плотность.
6. Разработаны полиномиальные алгоритмы, распознающие класс
реберных гиперграфов линейных гиперграфов ограниченного ранга.
Личный вклад соискателя. Все основные результаты диссертаци получены автором лично. В совместных печатных работах автора научным руководителем последнему принадлежат постановки задач идея большой клики.
Апробация результатов диссертации. Результаты, вошедшие диссертационную работу, докладывались и обсуждались ъ Международной конференции "Алгебра и математическаякибернетика" посвященной 80-легию со дня рождения академика Д.А.Супрунень (21-22 ноября 1995 года, Минск) и на VII Белорусской магематк ческой конференции (1S-22 ноября 1996 года, Минск).
Опубликовашость результатов. Результаты диссертации опуб-шкованы в 5 научных статьях и тезисах конференции.
Структура и объем диссертации. Диссертация состоит из шедения, четырех глав, разбитых на 8 разделов, выводов и сшюка гспользованных источников из 41 наименования. Полный объем сиссертационной работы - 96 страниц машинописного текста, включая ІЗ иллюстрации.