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

ндциондаьндя академия наук Беларуси

институт математики

\ л

/ г"

УДК 51Э.1

МЕТЕЛЬСКИЙ ЮРИЙ МИХАЙЛОВИЧ

РЕБЕРНЫЕ ГРАФЫ ГИПЕРГРАФОВ ОГРАНИЧЕННОГО РАНГА

01.01.09 - Математическая кибернетика

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

Минск -1356

Работа выполнена в Белорусском га су д а р ст в в к к о г университете.

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

профессор Тышкевич Р.И.

Официальные оппоненты: доктор физико-математических наук.

доцент Гордон B.C.

кандидат физико-математических наук, доцент Сарванов В.И.

Оппонирующая организация: Нижегородский государственный

университет

Защита состоится да&вралЛ 1998 г. в "iL? часов у

' /

заседании совета по защите диссертаций Д 01.02.02 в Институт математики HAH Беларуси по адресу: 220072. г.Мине ул.Сурганова,11.

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

Автореферат разослан ЛК^^ргЯ. 99s года.

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

кандидат физ.-мат. наук А.И.Астровски

ОБЩАЯ ХАРАКТЕРИСТИК РАБОТЫ

Актуальность теиы диссертации. Диссертационная работа относится к тому разделу теории графов, в котором граф представляется как производная структура от другого математического объекта (корня). Наличие соответствующего представления нередко означает, что рассматриваемый граф обладает рядом "полезных" дополнительных свойств. С другой стороны, производный граф несет некоторую информацию о корне, поскольку этот граф служит в данной ситуации инвариантом корня.

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

Пусть С - граф порядка п, а 1(&) - некоторый список эго инвариантов. Это могут быть степенная последовательность, список п-1-вершинных порожденных подграфов графа С, список окружений вершин втого графа или что-либо другое. Возникают следующие две проблемы:

1. Реализуемость. Задан список I. Является ли он реализуемым, т.е. существует ли такой граф что I = 1(С)?

2. Единственность - При каких условиях равенство :(С ) = I(С3) влечет изоморфизм С^

В одной из недавних работ Айгнера и Триша (1994) подчеркивается важность исследования графов и их инвариантов по тсазанной выше схеме.

Значения функции I - "реберный граф" являются инвариантами, определенными на множестве всех гиперграфэв без изолированных :ершин. При этом каждый граф является реберным для некоторого таперграфа (Марчевский, 1945). Поэтому, оставаясь в рамках риведенной выше схемы, естественно фиксировать какое-либо еоретико-гипергрзфовое свойство Р и рассматривать две следующие роблемы:

1. Реализуемость. Задан граф С. Существует ли гиперграф € Р, такой что С = Ь(Н)?

2. Единственность. При каких условиях равенство (Нг) = Ь(Н2), , Н2 е Р, влечет изоморфизм Н^ Н2?

Диссертация посвящена главным образом решению задачи

реализуемости.

Л.Ловас (1977) выдвинул задачу характеризации класса I реберных графов гиперграфов ранга не выше грех, положив тем самь начало исследованиям задачи реализуемости для свойства Р - "быа гиперграфом ранга не выше г" при г а 3.

Известно, что класс 1 при любом газ нельзя охаракте

Г

ризовать конечным списком запрещенных порожденных подграфов. I

о

спасает в этом случае и сужение Ь до класса Ь графов, имении

г г

линейные корни ранга не выше г.

Р.Н.Найк, С.Б.Рао, С.С.Шрикханд и Н.М.Сингхи (1980, 1982

о

получили конечные характеризации графов из Ъ при условии, 41

г

степени вершин (или ребер) рассматриваемых графов достаток велики. Эти конечные характеризации свидетельствуют о решаемое^ проблемы Ловаса и аналогичных проблем для г г 4 при подходящ« выборе релаксирущего условия.

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

Связь работы с крупными научными программами, темами. Рабо-над диссертацией проводилась на кафедре уравнений математичесж физики Белорусского государственного университета в соответствз с темой "Методы и алгоритмы комбинаторной оптимизации вычислительной геометрии" в рамках Государственной програш фундаментальных исследований Республики Беларусь "Методы алгоритмы вычислительной и дискретной математики (Алгоритм (Головная -организация Институт, математики АН Беларуси).

Диссертационная работа является частью плановой госбюджет» НИР 1.1.16 "Структурный: анализ графов, гиперграфов и булев] функций" (N0 гос. регистрации 19951144).

в

Цель и задачи исследования. Как отмечалось выше, класс 1

Г

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

Задачи исследования:

1. Исследовать возможность характеризации графов из

о

^ конечным списком запрещенных порожденных подграфов в классе тзафов с минимальной степенью вершин менее 69.

2. Подтвердить или опровергнуть гипотезу, выдвинутую Найком

»

[ др. (1982): для любого целого с классы Ь , г г 4, нельзя оха-

ТГ

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

3. Исследовать возможность получения аналогичных результатов

(ля гиперграфов из классов ^ г , 3.

г Л.

4. Охарактеризовать графы из Ь и Ъ посредством конечных

Г г

¡писков запрещенных порожденных подграфов в классе расщепляемых ■рафов.

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

Научная новизна полученных результатов. Научная новизна

езультатов диссертации обусловлена следующим. Впервые получены

.онечные списки запрещенных ■ порожденных подграфов,

о

арактеризувдие графы из 1з в классе графов со степенями вершин

е ниже 19 и в классе расщепляемых графов, а также доказано

£

уществование подобных конечных характеризаций для графов из Ь в

г Л.

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

Практическая значимость полученных результатов. Полученные в

иссертационной работе конечные списки и алгоритмы поставляют

флективные необходимые и достаточные условия для вхождения

А.

рафов в исследованные в етой работе классы Ъ^. Граф, априори ринадлежащий■втому классу, обладает рядом "полезных" свойств. В астности, полный список максимальных клик такого графа может ать построен за полиномиальное время. Последнее важно для громного количества теоретических и прикладных задач теории рафов.

Экономическая значимость полученных результатов. Экономическую значимость разработанных в диссертации методов I алгоритмов оценить в настоящее время не представляется возможным.

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

1. Получены конечные списки запрещенных порожденные подграфов, характеризующие:

- графы из в классе графов со степенями вершин не ниж<

19;

- графы из Ь^ и Ь в классе расщепляемых графов.

3. г

2. Подтверждена гипотеза Найка и др. (1982) о невогможностз

Ь

аналогичной характеризации для графов из Ь при г г 4 для любог<

Г

целого с, ограничивающего снизу степени вершин рассматриваемы: графов.

3. Получены список и теоремы, обобщающие приведенные выш< результаты (со степенными ограничениями) для реберны: гиперграфов.

4. Доказано существование рассматриваемой конечно:

Л

характеризации для графов из I в классе расщепляемых графов пр:

г

любом г.

5. Приведен аналог теоремы Уитни об изоморфизмах реберны графов простых графов для расщепляемых графов из I» , г а 3

Г

тлеющих достаточно большую плотность.

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

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

Апробация результатов диссертации. Результаты, вошедшие диссертационную работу, докладывались и обсуждались к Международной конференции "Алгебра и математическая ■кибернетика" посвященной 80-летию со дня рождения академика Д.А.Супрунень (21-22 ноября 1995 года, Минск) и на VII Белорусской математической конференции (13-22 ноября 1996 года, Минск).

Опубликованность результатов. Результаты диссертации опуб-шкованы в 5 научных статьях и тезисах конференции.

Структура и объем диссертации. Диссертация состоит из ¡ведения, четырех глав, разбитых на .8 разделов, выводов и списка [спользованных источников из 41 наименования. Полный объем сиссертационной работы - 96 страниц машинописного текста, включая (3 иллюстрации.

СОДЕРЖАНИЕ РАБОТЫ

Во введении содержится оценка современного состояния

досматриваемой проблемы, обосновывается необходимость проведения

:сследований по теме диссертации.

В первой главе продолжен обзор литературы, начатый во

¡ведении. Даны основные используемые в работе понятия и

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

:редставлений графов. Среди них: теорема Краусса (1943), дающая

'лобальную характеризацию реберных графов простых графов в

о

ерминах покрытий клмками; ее обобщения для классов Ь и 1

г г

юберных графов г-униформных и линейных г-униформных гиперграфов,

оответственно (Берж, 1989 и Найк, Рао, Щрикханд, Сингхи, 1980);

еорема Байнеке (1968), характеризующая реберные графы простых

рафов в терминах запрещенных порожденных подграфов; теорема

:ерзха (1973), описывающая для произвольного графа й полный

рообраз Ь_1(С) при отображении Ь - "реберный граф гиперграфа";

еорема о "большой" клике (Левин, Тышкевич, 1993).

Вторая глава диссертации посвящена проблеме характеризации о

рафов из классов Ь , г г 3, в терминах запрещенных порожденных

Р

одграфов при релаксирующем условии "иметь достаточно высокие гепеяи вершин".

Термин "граф" ("простой граф") означает конечный

еориентированный граф без петель и кратных ребер.

Реберный граф Ь(Н) гиперграфа Н определяется как граф

ересечений ребер гиперграфа Н, т.е. У1(Н) = ЕН, вершины и е2

межны в Ь(Н), если и только если ребра е и е„ пересекаются в Н.

1 2

Произвольный полный подграф графа назовем кликой.

Максилальная клика максимальна относительно включения.

Для каждого целого числа г обозначим г*= г2- г + 2. Клика К называется т-йолыиой, если |К| г г*.

Гиперграф называется линейны*, если никакие два его ребра не имеют более одной общей вершины. Гиперграф называется г-унифорлныл, если степени всех его ребер равны г. Тем самым, граф - вто линейный 2-униформный гаперграф (мультиграф 2-униформный гиперграф).

Объединение С2 гиперграфов , С2 определяется как теоретико-множественное объединение

с2) = тс^ ТС2, Е^и С2) = ЕС^ ЕСа.

Конечное семейство С = (С : 1 е I) клик графа С называется покрытием, если С является объединением этих клик.

Сформируем список графов А, полоаога А = «4 и А^ ... и «4?, где классы графОЕ А определяются следующим образом.

А - множество графов порядка 20, имеющих доминирующую

вершину и не содержащих К .

8

А„ - множество графов вида К - Е(К ), 1 < ш £ 4.

2 9 1 » го

<43 - множество графов, представимых в виде

или

С = й и а, йе й е К „, 2,5 УС I £ 3

1 2 1 2 В '1 2'

С = й и Си Р, Са Се К „, ^ л = 3,

1 2 1 2 В ' 1 2

V? £ У(Си С„), ЕР л Е(С и С„) =

12 12

где Р = гаК2 - граф порядка 2т с ш попарно не смежными ребрами,

1 5 1 5 6.

{ к<

4 1,4

<4, Аг и <4„ - множества графов, представимых в виде

Б & 7

объединения

С = В и й и Си ... иС и? 12 р

эафов, попарно нэ имеющих общих ребер и удовлетворяющих условиям , II и III соответственно.

I. a) - максимальная клика графа G, 1= 1.....р;

) VF с V(G u G и ... и G );

1 2 р

) в У нет ребер, оба конца которых входят в В; ) VB л VG;# а, 1=1.......

) В входит в список графов, запрещаемых теоремой Байнеке (см.

рис. 1); ) 8 s |G11 £ 11, 1= 1.....р;

Рис.1. Графы Байнеке

) какдая вершина графа В входит хотя бы в одну, но не более чем в две клики С1; II. а) и б) из I; ) В = Рз - простая трехзершинная цепь; I = 8, 1= 1,2,3; р = 3;

) центральная вершина цепи В входит в С1 и з С2, но не в С , а

обе концевые вершины входят в Сз, но не входят ни в G ни в С2.

III. а) - г) из I;

д) В совпадает с одним из графов 3= 1,2,3, изображенных з рис. 2;

е) 8 s |Gj| s 9, i= 1,—,р;

ж) каждая вершина графа В входит хотя бы в одну, но не более ч( в две клики G 4, причем каждая вершина степени 2 входит в дв< клики.

Рис.2. Графы Я^ Очевидно, что список 4 конечен.

В разделе 2.1 доказано, что этот список являете

о

характеризационным для графов из с 5(С) г 19. А именно, верь

Теорема 2.1. Для графа й с 6(С) ь 19 эквивалент следупще два утверждения: (I) Оеф

({I) ни один из порожденных подграфов графа С не входит список 4.

Доказательство теоремы 2.1 вплотную используе в

характеризацию класса Ь в терминах покрытий кликами, теорем

Краусса и Байнеке, и основывается на технике 3-больших клик.

Л А.

Класс Ь3 выделяется из классов Ь , о чем

свидетельствует

Теорема 2.3. Для г > 3 и произвольной константы с графи

в

из Ъ нельзя охарактеризовать в классе графов со степенями вершин не ниже с посредством конечного списка запрещенных порожденных подграфов.

Назовем порогом 5 наименьшее целое число, такое что графы

гг 0

из Ь3 допускают конечную характеризацию запрещенными порожденными

подграфами в классе графов со степенями вершин не ниже 5о. Из

теоремы 2.1 вытекает верхняя оценка для порога: 5о£ 19. В этом

разделе известная нижняя оценка За 4 также улучшена. Приведено

бесконечное запрещенное семейство графов с минимальной степенью

вершин равной 5. Суммируя сказанное, получаем: б £ 5о 5 19.

В разделе 2.2 приведен полиномиальный алгоритм распознавания с

графов из I, в классе графов со степенями вершин не ниже 19.

Третья глава диссертации посвящена проблеме характеризации Л,

графов из I и 1 , г а 3, запрещенными порожденными подграфами

Г Г

при релаксирующем условии "быть расщепляемым графом".

Граф С называется расщепляемым, если существует такое разбиение множества его вершин Уй = А и В, что порожденный подграф б(А) является полным, С(В) - пустым. В разделе 3 -1 доказаны

Теорема 3.1. Для расщепляемого графа й следующие два утверждения равносильны: (I) С € Ъ ;

. г

(I £) С не содержит порожденного подграфа К£ .

Теорема 3.2. Существует конечный список 5 графов, такой

о Г

что расщепляемый граф С принадлежит классу Ь , если и только

Г*

если ни один граф из & не я&ляется порожденным подграфом 8 С.

Г

Рассмотрим список Я всех графов С порядка г*+ 1,

Г*

удовлетворяющих условиям:

- существует V е УС, такая что УС \ {V} - клика в й;

- Г 4 1 £ V £ Г*- 1.

В разделе 3-1 также показано, что принадлежность расщепляемой

* JL

графа С плотности p(G)a г классу 1 , г г 3, можно описать

Г

только в терминах запрещенных порожденных подграфов, но степенной последовательностью графа:

Следствие 3.3. Для расщепляемого графа G плотное, p(G) г г* со степенной последовательностью

й = ( üjP d2.....dn), 4,2 4^ 1, i= 1,2,...,n-1

следующие утверждения эквивалентны:

(i) G e Ъг l

r

(ii) й не содержит порожденных подграфов, изоморфных граф из множества Яг и { К4 г+1>;

(Ш) ^ s <p<G>+ г - 2, г.

Пусть Н( и Н2 - гиперграфы без кратных ребер, a:VHi-» VH2 биекция. Для подмножества е = iv,, v ,..., v > £ VH полок

12 г 1

а(е) =ia(vi), «<v ),..., a(Vr)>.' Изоморфизм а:Н -» Н2 гиперграф

Hj и Н2 индуцирует изоморфизм ß:L(H )+ Ь(Н2), если )3(е) = а(

для любого ребра е гиперграфа Н .

1

В разделе 3.3 доказан аналог известной теоремы Уитни изоморфизмах реберных графов простых графов:

Теорема 3.8. Пусть G - связный расщепляе.шй граф плотное (ß(G) г Г*. Если Ь(Н ) а I(H2) s С, где Kf ti - некотор линейные т-унифор.тые гиперграфы без изолированных вершин, то

(1) Н1= Н2;

(2) для любого изоморфизма ß: L(H1) ■* L(Ha) существу изоморфизм а: Н Н2, индуцирующий ß, причем

(3) эквивалентны два следующие утверждения:

(L) изоморфизм а, индуцирхрещхй ß, определен однозначн (ii) никакое ребро гиперграфа Ht не содержит бол одной вершины степени 1.

Четвертая глава диссертации посвящена . дальнейше исследованию реберных гиперграфов, впервые введенных А.Г.Левин и Р.И.Тышкевич (1993), обобщающих реберные графы гиперграфов.

В разделе 4.1 приведено определение реберного гиперграфа, дана необходимая теоретико-гиперграфовая терминология.

Гиперграф Б называется частью (частичные. гиперграфол) гиперграфа Н, если УС е та, Е£ е ЕН. Простой (т.е. без кратных ребер) гиперграф Б называется полныл т-унифоршъл, если ребрами его служат все г-влементные подмножества множества УС и только они. Кликой гиперграфа называется любая его полная г-униформная часть, гг 1; одновершинная часть также считается кликой. №акси.еа.>.ъная клика максимальна относительно включения.

Обозначим через Е(у) = Е„(у) множество ребер гиперграфа С,

О

инцидентных вершине V е УС; <leg V = |Е(V)| - степень вершины V.

Пусть Н - гиперграф без изолированных вершин. Определим цеберный гиперграф £(Н) (точнее, семейство реберных гиперграфов). Пдя каждой V е УН зафиксируем целое число й , соблюдая

V

следующие условия:

- если йен V = 1, то О 5 й 5 1,

V

- если V г 2, то 2 а V.

1усть И = (<1 : V е УН), С - полный <1 -униформный гиперграф с

V V V

люжеством вершин Е(у). Положим

2(Н) = а (Н) = и с .

V е ун у

Иегко видеть, что ^(Н) = 1(Н), если выбрать й^е {0, 2} для побой V е УН.

Для гиперграфа Н все значения функции #(Н) называются )еберны.«и гиперграфам, (гиперграфа Н).

В разделе 4.2 результаты раздела 2.1 обобщены для ■■иперграфов из классов И^, г г 3, при дополнительном ограничении

г

1а ранг рассматриваемых гиперграфов.

Скажем, что два ребра э , е2 гиперграфа С со степенями е4|= р, |92|= д удовлетворят, условию А, если либо р * q, либо ) = q и существует множество 9 £ в и е2 мощности р, такое что I в ЕС.

Под 2-секцией гиперграфа С (обозначение Ю32) понимаем граф, ¡ля которого У1С]2= УС, и вершины и,у смежны в (СЗ2, если и 'олько если они смежны в й.

Часть С гиперграфа Н порождается лножестйол вершин X £ VI-

если

УС = X, ЕС = < е € ЕН : в £ X)

(обозначение С = Н(Х)). Такие частичные гиперграфы называ« просто порожденными, если не нужно конкретизировать множество 5 Ясно, что если Н - простой граф и X £ УН, то Н(Х) - порожденнь подграф в Н. Для гиперграфа Н и множества ребер Y £ I обозначим через Н(У) часть гиперграфа Н, такую что

УН(У) = и 0, ЕН(У) = У.

в € У

Каждому гиперграфу Н поставим в соответствие два гиперграфа Н1 Н2, которые определяются следующим образом:

Н^ = Н({ е е ЕН : |е|* 2)), Н2= Н({ е е ЕН : |е|= 2>).

Пусть й - некоторое число, не меньшее двух. Рассмотр] список гиперграфов А, положив А = А и А и ... и А , где клас<

12 В

А гиперграфов ранга не выше <3 определяются следующт.1 образом.

А , Аг и Аз - множества гиперграфов С, для котор] частичный гиперграф С2 принадлежит классам графов »4 , А2 и < из разд. 2.1, соответственно, и УС = УС2.

А- множество гиперграфов С, которые содержат четы;

попарно удовлетворяющие условию А ребра е , в2, ед, е4, так

что УС = е1и е2и е3и е^ и ^л е | = { V >, 1,3 = 1,2,3, 1 для некоторой вершины V е УС.

4 , А и А„ - множества гиперграфов, представимых в ви

5 о 7

объединения

С = В и С и Си ... и С и Р

12 р

гиперграфов, имеющих 2-секции с попарно непересекагащши множествами ребер и удовлетворяющих условиям I, II и I соответственно.

I. а) С - максимальная клика гиперграфа G, i= 1,...,р;

б) VP s V(G и G и ... и G );

12 р

в) каждое ребро степени 2 гиперграфа F имеет непустое пересечение с VG\VB, а любое другое ребро содержится в VGNVB;

г) VB л VGj^ в, 1= 1,...,р;

д) В входит в список графов, запрещаемых теоремой Байнеке (см. рис. 1);

е) если rank Gt= 2, то 8 s |VGS | s 11, иначе

¡VGJ s max i 11, d >, i= 1,...,p;

ж) каждая вершина графа В входит хотя бы в одну, но не более чем в две клики Gj;

II. а) и б) из I;

в) В = Рэ - простая трехвершинная цепь; р = 3;

г) если rank G = 2, то IVG£ | = 8, иначе IVGJs шах { 3, d }, i= 1,2;

д) rank G3= 2, |VG3| = 8;

е) центральная вершина цепи В входит в G[ и в С2, но не в G3, а

обе концевые вершины входят в G3, но не входят ни в G ,

ни в С . 2

III. а) - г) из I;

Ю В является одним из графов R^, 1,2,3, изображенных на

рис. 2;

г) если rank Gt= 2, то 8 s jGJ s 9, иначе |VG(| s max { 9, d >, i= 1.....p;

e) каждая .вершина графа В входит- в одну или в две клики G , причем каждая вершина степени 2 входит ровно в две клики G t.

- множество гиперграфов G, которые содержат два гдовлетворяющие условию А ребра е^ э0, такие что VG = ^и в2 и etA е2| 2 2.

Список Л конечен, ибо конечен каждый класс А в силу меющихся ограничений на ранг (и на порядок) входящих в него иперграфов.

Теорема 4.4. Для гиперграфа G с S(G)a 19 u rank G s d

'ледухщае два утверждения эквивалентны.:

(i) G « ф

(it) никакая из г.орохбенкых частей гиперграфа. G не б ходит t список А.

Зафиксируем теперь произвольное целое г а А. Утверждение, аналогичное доказанному выше, невозможно в отношении класса И^.

г

Действительно, для любых чисел d & 2 и с имеет место включении { G : G е if, cS(G)a с } s { G : G € 5(G)a c, rank Gs d>.

Поэтому из теоремы 2.3 вытекает

Teopeua 4.5. Для произвольного целого г г 4 и любых чисе. d г 2 и с гиперграфи из нельзя охарактеризовать 6 классt гиперграфов со агзпенляи вершин не ниже с и ранге, не выше i посредством конечного списка запрещенных порожденных частички, гиперграфов.

В разделе 4-3 разработаны алгоритмы, решающие з полиномиальное время задачу распознавания "G € ¿(H)", где Н гиперграф с фиксированным свойством Р, а строящие одлн из Н. качестве Р рассматривались следующие свойства: "быть линейннм" "быть ягостк?.} гргхсм", "быть линейным г-униформным г:шерграфо?л с степенями вершин не ниже г* Креме того, предложе.

полиномиальный алгоритм, решающий задачу распознавания "G е в классе гиперграфов со степенями вершин не ниже 19.

ВЫВОДЫ

1. Для графов из Ъэ получена конечная характеризация в

грминах запрещенных порожденных подграфов в классе графов со

?епенями вершин не ниже 19; уточнены границы порога характе-

Л

[зуемости для класса 1 . Приведена аналогичная характеризация

£

ш графов из класса Ьз со степенями вершин не ниже 5.

2. Доказано, что подобных конечных характеризаций для графов

о

\ классов Ь , г > 3, не существует при любом ограничении снизу

Р

I степени вершин втих графов.

3. Предлагается полиномиальный алгоритм, распознающий

о

ойство "б е I, " в классе графов со степенями вершин не ниже 19.

в

4. Полученные для классов I , г г 3, результаты в случае

т*

раничений на степени вершин перенесены на реберные пергрэфы.

5. Доказано существование конечных характеризаций в терминах

в

прещенных порожденных подграфов для графов из Ь и Ь при

Г г*

ловии, что рассматриваемые графы являются расщепляемыми. Для ассов Ь . и Ь^ приведены соответствующе списки.

г 3

6. Доказано, что принадлежность расщепляемого графа б

♦ а

отности р(С) 2; г классам Ъ можно описать не только конечным

Г*

иском запрещенных порожденных подграфов, но и степенной

о

следовательностью графа С. Для таких расщепляемых графов из Ь ,

Г

г 3, получен аналог теоремы Уитни об изоморфизмах реберных эфов простых графов.

7. Предложены алгоритмы, решающие за полиномиальное время дачу распознавания "С е £(Ю", где Н - гиперграф с ссированным свойством Р, и строящие один из Н. В качестве Р курируют свойства: "быть линейным", "быть простым графом", иь линейным г-униформным гиперграфом со степенями вершин не ?е г ".

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦМ ОПУБЛЖОВАНЫ В РАБОТАХ

1. Метельский Ю.М. Расщепляемые реберные графы от гиперграфог ограниченного ранга // Весц! АН Беларус1. Сер. ф1з.- мат. навук.- 1997-- N 3.- С.117-122.

2. Метельский Ю.М. Реберные гиперграфы от линейных 3-униформшо гиперграфов // Becqi .АН Беларусл.. Сер. Ф1з.- мат. навук.-1998.- N 1.- С.72-76.

3. Метельский Ю.М., Тышкевич Р.И. О реберных графах линейныз гиперграфов ограниченного ранга // Тезисы докладов VI: Белорусской Математической конференции,- Минск, 1996.- Ч.З.-С.132-133.

4. Метельский Ю.М., Тышкевич Р.И. Реберные графы линейны: З-униформных гиперграфов // Докл. АН Веларус!.- 1996.-Т-40, К 3.- С.26-30.

5. Тышкевич Р.И., Мельников О.И., Метельский Ю.М. Распознавание реберных гиперграфов от гиперграфов с предписанным] свойствами // Весц1 АН Беларус!. Сер. ф1з.- мат. навук. -1996.- N 2.- С.101-105.

6. Metelsky Yu., Tyshkevich R. line Graphs oi Linear 3-Unifori Hypergraphs // J. Graph Theory - 1997.- Vol.25.- P.243-251.

РЕЗЮМЕ

Метельский Юрий Михайлович

"Реберные графы гатерграфов ограниченного ранга"

Ключевые слова: реберный граф, порожденный подграф, покрытие

«ликами, г-больиая клика, реберный гиперграф.

Известно, что класс 1Л" реберных графов линейных гиперграфов

занга не выше г не может быть охарактеризован конечным списком

!апрещенных порожденных подграфов для любого г а 3. Целью

дассертации является получение подобных конечных характеризаций

'рафов втого класса при следующих релаксирущих условиях: "тлеть

(остаточно высокие степени вершин", "быть расщепляемым графом".

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

получены конечные списки запрещенных порожденных

а

юдграфов, характеризующие графы из Ь3 в классе графов со '.тепенями вершин не ниже 19 и в классе расщепляемых графов;

- доказана гипотеза Найка, Pao, Шрикханда и Сингхи (1982) о

о

«возможности аналогичной характеризации для графов из 1Л" при ■ а 4 для любого целого с, ограничивающего снизу степени вершин ассматриваемых графов;

упомянутые выше результаты (в случае. степенных граничений) обобщены для реберных гиперграфов;

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

г

юбом г;

- приведен аналог теоремы Уитни об изоморфизмах реберных

о

рафов простых графов для расщепляемых графов из L , г г 3,

г*

чеющих достаточно большую плотность;

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

Полученные в диссертации конечные списки и алгоритмы

вставляют эффективные необходимые и достаточные условия для

о

гождения графов в исследованные в этой работе классы L . Граф,

Г

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

РЗЗЮМЗ

Мяцельею. Юрый М1хайлав1ч

"Кантавыя графы гшерграфау абмежаванага рангу"

Ключавыя оловы: кантавы граф, 1ндудыраваны падграф, пакрыцп

KJiiKaMi, г-вял1лсая кл1ка, кантавы гшерграф.

JL

Вядома, што клас L. кантавых графау л1нейных г!перграфа

Г

рангу не вышэй г нельга ахарактарызаваць канечным cnica забароненых 1ндуцыраваных падграфа^ для кожнага г г 3. Мэта дасертацы! з'я$ляецца атрыманне TaKix канечных характарызацк графау гвтага класа пры настушых дадатковых умовах: "меи дастаткова высок!я ступен! вяршыняу", "быць расшчашшльш, графам".

Аеноуныя bhhíkí работы:

- атрыманн канечныя cnicu забароненых 1ндуцыраван1 падграфау, як!я характарызуюць графы з ъ\ У клаое графау ступеням! вяршыняу не н!зкэй 19 i у класе расшчапляльных графау;

- даказана гллотэза Найка, Pao, Шрыкханда i CiHrxi (1982) i

„ j

немагчымасц1 аналаг!чнай характарызацы! для графау з L пры г г

Г

для кожнага цэлага с, якое абмяжоувае зн1зу ступен! вяршыш гетых графау;

- згаданыя вышей bühíkí (у вшадку ступеневых абмежавання; абагульнены для кантавых гшерграфау;

- даказана ¿снаванне разглядаемай канечнай характарызащ

j

для графа$ з L у класе расшчапляльных графау пры кожным г;

Г

- даказаны аналаг тэарэмы ¡/ithí аб 1замарф1змах кантав] графау простых графау для расшчапляльных графау з^г, 3, як:

' Г

маюць дастаткова вял!кую шчыльнасць;

- распрацаваны пал!номныя алгарытмы, як!я распазнаюць кла кантавых гзлерграфау л!нейных г!перграфау абмежаванага рангу.

Атрыманыя у дысертацы! канечныя cnicu i алгарытмы даю вфектыуныя неабходаыя i дастагковыя умовы для уваходжання граф

в

у даследаваныя у гетай рабоце класы L^. Граф, як1 апрыо належыдь такому класу, валодае шэрагам "карысных" уласц!васдяу. прыватнасцЗ., поуны cnic максимальных кл1к такога графа мож пабудаваць за пал1Иомны час. Апошняе icTOTHa для вялгк колькасц! тэарвтычных i дастасоуных задач теоры1 графау.

summary,

Metelsky Yury Mikhailovioh "Line graphs of hypergraphs of restricted rank" Key words: line graph, induced subgraph, clique covering, r-large clique, edge hypergraph.

It is known that the class L of line graphs of linear

V

hypergraphs of rank at most r can not be characterized by a finite list of forbidden induced subgraphs for every r a 3. The aim of the thesis is to obtain such finite characterisations of graphs in this class under the following additional conditions: "to have sufficiently large vertex degrees","to be a split graph". Main results of the thesis are:

- finite lists of forbidden induced subgraphs characterising

e

graphs in Lg both in the class of graphs with vertex degrees at least 19 and in the class of split graphs are obtained;

- the hypothesis of Nailt, Rao, Shrikhande and Singhi (1982)

■L

on impossibility of a similar characterization for graphs in L

r

with vertex degrees at least c for each r a 4 and arbitrary c is confirmed;

- the above mentioned results (in case of degree restrictions) are generalised to edge hypergraphs;

- the existence of such a finite characterisation for

o

graphs in L in the class of split graphs for each r is proved;

- a version of the Whitney theorem on isomorphisms of line

s

graphs of simple graphs is proved for split graphs in L^, r a 3, rvith sufficiently large density;

- polinomial algorithms recognizing the classes of edge iiypergraphs of linear hypergraphs of restricted rank are jonstructed.

The obtained finite lists and algorithms give efficient lecessary and sufficient conditions for belonging the graphs to

a

jonsidered classes L . A graph in this class has a number of

r

•useful" properties. In particular, the list of maximal cliques )f such a graph can be constructed in polynomial time. This is Important for numerous theoretic problems and applications of jraph theory.