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

1 ^ АКАДЕМИЯ НАУК БЕЛАРУСИ ИНСТИТУТ МАТЕМАТИКИ

На правах рукописи

СИПА АБРАХАМ

ИЗУЧЕНИЕ ЗАВИСИМОСТИ СТРУКТУРЫ ГРАФА ОТ СМЕННЫХ ИНВАРИАНТОВ

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

Автореферат

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

Минск - 1992

Работа выполнена в Белорусском ордена Трудового Красного Знамени государственном университете имени В.И.Ленина

Научный руководитель Официальные оппоненты

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

доктор физико-матеыатиче схих наук, профессор ТЫШКЕВИЧ Регина Иосифовна

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

наук, профессор

ТАНАЕВ Вячеслав Сергеевич

кандидат физико-математических наук САРВАНОВ Владимир Иванова1

Нижегородский госуниверситет (г.Нияпяй Новгород)

Защита диссертации состоится "22 " мая_ 1992 I

в часов на заседании специализированного совета

К 006.19.01 в Институте математики АН Беларуси (220072, г.Минск, ул. Сурганова, II )

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

Автореферат разослан » 3 " 1992 г>

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

кандидат фиэ.-маг.наук .Я^Цг^)- А.и.АстровскиЯ

ОВШ ХАРАКТЕРИСТИКА РАБОШ

■Актуальность темы. В конце 50-х и начале 60-х годов началось 'интенсивное изучение степенных инвариантов графов, которое стало важным разделом теории графов. С этого времени наблюдается активное нарастание интереса к теории степенншс последовательностей графов. Это связано, в первую очередь, с естественным отрешением выявить зависимость структуры и свойств графа от легко вычисляемых инвариантов.

В работах П.Эрдеша, Т.Галлай, С.Л.Хакши, В.Гавела, Г.Дя.Райзеря, Дд.Сеньгора, Д.Тейла, Д.Р.Фалкерсона, М.Х.Мак-Эндрю, А.Хофдмапа, Дж.Эдаоидса к других авторов в 1950-1560 гг. было положено начало такого подхода к изучению графов. Полученные результаты касались не только графов, по и других близких к ним объектов (мультиграфов, пседографов, ( ОД)-" матриц). Получено большое количество результатов характерлза-ционного типа. Другом важной причиной этих исследований является прикладная значимость рассматриваемых вопросов. Достаточно указать на такие области, как химия структурных изомеров и теория надежности систем. Выявлена гаме связь теории степенных последовательностей с другими разделами дискретной математики.

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

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

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

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

. Научная новизна. I. Найдено новое необходимое условие вынужденной п -раскрашиваемости последовательности целых чисел, т.е. реализуемости'последовательности только в классе п. -раскрашиваемых графов. Эти условия независимы от известных результатов на эту тему. Решена еще одна известная проблема: харастеризация вынужденно í -циклических последовательностей, 6 .в частности, усиливается известный результат Г.Иксу и Ф.Харари.о вынужденно i -циклических последовательностях. Дается полная характеризация степенных последовательностей кактусов.

2. Исследована Р -униграфичность в некоторых классах графов.

. Класс Р -униграфических последовательностей содержит как подкласс униграфические последовательности, реализации которых обладают свойством Р . Охарактеризованы Т и

4

унаграйичвские последовательности, где Т и С/ означают свойства "бить деревом" и "быть .связнш ункциклпчео-ким графом" соответственно.

Условия граГаичиости и униграфичкоета широко.изучаются в работах Тышкевич Р.И. и Черняк A.A. 3 то не время характериза-ционкых результатов, касающихся Р - униграфичности последовательностей, практически нет. Хотя рассмотрение таких последовательностей естественно и имеет практическое значение при генерировании графов с заданными свойствами, изучение изомеров некоторых химических соединений и т.д.

3. Получено одно дополнение к харахтеризацми биуниграфов, Бешена задача характеризацш несвязных биуниграфов. Для связных графов аналогичная задача биуниграфичносги с разбиением на доли решена Р.И.Тшкевич и А.А.Черяякоы.

4. Охарактеризованы пары ( 5, р ), где 5 - множество натуральных чисел, р - чгело, для которых существует ациклический граф порядка р , степенное шокество которого совпадает с 5 . Найдены условия однозначной реализуемости указанных дар в классе ациклических графов.

5. Охарактеризованы ¿г -множества и найдено необходимое

и достаточное условие при которых множество В является

р Г^'-^р

Ь - множеством. Вычислен минималышй порядокУ (г - множества.

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

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

¡. Основные результаты диссертации докладывались

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

■ Публикации. Основные результата диссертации опубликованы в работах /Ь 5-8/.

Структура и объем работы. Диссертация состоит из введения, двух грав и списка литературы (64 наименований).

■ Основное содертание диссертации изложено на 60 страницах машинописного текста.

Содержание работы

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

Все 'рассматриваемые в работах графы конечные, неориентированные, без петель и кратных ребер.

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

Список степеней вершин графа называется степенной последовательностью этого графа. Целочисленная последовательность

( 4 , с/2, . .., «4,),г.;?* сГ,Ъ . . . - ъ 4>о.(1)

называется графической, если существует граф с множеством вершин у О — {А, • ^ » такой, что сте-

пень вершины г£ " равна . ^ = ; £ в .

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

5Г . Наиболее известные критерии трафичностк - теорема Эр-деша-Галлаи и Гавела-Хакили - приведены в /12/.

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

6

хорошо известна Д7/. Такие последовательности называются вынужденно р -графическими и широко изучаются (см., например/ /2-4, 13, .9 ,17 Д В диссертации рассматриваются следующие' свойства Р :

I) а - раскрали ваекость: каждая реализация & последовательности ЗГ~ вида (I) имеет хроматическое число Д-^ц.

■ 2) С -цикличность: каждая реализация (¡г последовательности С]Г вида (I) шеет_ ровно ь -простых циклов.

Получено новое необходимое условие вынувденной Я. -рас-крашиваемости последовательности. Око независимо от известного необходимого условия /3/.

' Назовем последовательность вида (I) тривиально^

/2.-раскрашиваемой, если она г-рафкчна и либо ре. л. , либо

р?/1+1 и с/ & п~х • Очевидно, что все тривиально П. -I П+х

раскрашиваемые последовательности являются вшукден-

ко 1г -раскрашиваемыми.

Георема 1.2. Графическая последовательность вида

(I) вынужденно реализуется о -циклическим графом (лесом) тогда и только, тогда, когда 1Р~2), р 2.

Доказан ряд характеризадаопннх теорем с вынужденно (■ -циклических последовательностях, из которых, в частности, следует результат Г.Шоу и у.Харарл /Г5/.

Связь между задачей аарастеризации вынужденно /г. -раскрашиваемых и вшуадемю г' -щжличеоких последовательностей 'заключается в следующем. При малых значениях 1 каддзя вынужденно I -циклическая последовательность является вынужденно 3 -раскрашиваемой, а вынузденно 3-раскрашиваемы'е последовательности полностью описаны в /2/.

7

Теорема. 1.1. Всякая вынужденно п. -раскрашиваемая последовательность, не являющаяся тривиально а. -раскрашиваемой, удовлетворяет условию

°а<-2 Спри Р м п + 1 считаем, что

Леша 1.1. в главе I дает нам возможность видеть, что если графическая последовательность <ЗГ вида (I) Еынуаденно реализуется г -циклическим графом, , то тогда

вое реализации последовательности являются связными гра-

фами.

Имеет место следующая

Теорема 1.3. Графическая последовательность вида

(I) вынуаденно реализуется -циклическим кактусом при

г>, X тогда и только тогда, когда

(р,х,гг1', ±р-21~>)} + ч

а при -С =. I , кроме того, с)г , с/3 , 1р>"3),

¡> + ? = с/, ч с/2 +- о/3 , р

Из теоремы 1.3 вытекает результат Г.Иксу и ФДарари.

Назовем квази-какгусом граф, в котором найдутся три цикла С' , СЯ , С3 > вершины которых индуцируют граф гео-меоморфный графу к ~е » а остальные циклы не имеют общих ребер ни с каким другим циклом.

Теорема 1.4. Графическая последовательность У/ вида ^1) вынуаденно реализуется I -циклическим квазикактусом 1при ь ^ 4- тогда и только тогда, когда 5Г* / (гг -5, з, *г£-3). (р. 1

Так как любой квази-кактуо является 3-раскрашиваемш графом, то из /2/ следует, что ^ ¿2 » ГД0 элемент последовательности .

.В § I гл. I приведены несколько, результатов, которые дают необходимые и достаточные условия, при которых последовательность вида (Д) вынужденно 4-циклична, 5-циклична, 6-цшслична.

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

В § 1.2 гл.1 охарактеризованы Т и ^ - униграфи-ческие последовательности, где Т* и "О означают свойства "быть деревом" и "бить связным ункциклическнм графом" соответственно.

последовательность зида (I) называется Р -уни-

графической, если ровно одна ее реализация обладает свойством

Р . . .....

Обозначим через О"^) (соответственно ^ (ЗГ) ) мно-

Р

жество всех ■ реализаций последовательности 5Г » обладающих свойством Р .

Последовательность- Л вида (I) называется вынужденно .

Р -графической (соответственно, Р -униграфической), если; ф фЦТ) й. ( соответственно,

Г) 1р \ ~ 1) « гДе Цр обозначает класс всех графов, . обладающих свойством Р . В случае когда сва" ство Р тривиально (ему удовлетворяют все графы), го понятия вынужденной Р -графичности и Р -упиграфичности превращаются в обычные' понятия графичности и упиграфичности.

. Условия графичности и уиитрафичносгн широко изучаются в

9

работах Тепеввкч Р.И., Черняк А. А. В то ко время харзктериза-цкон-шх результатов, асасазэщкея Р -унул?ра$ических последовательностей, практически нет, хотя рассмотрение таких послз-дователыгастей дозольно естественно.

Обозначим через Т кноЕестхзо всех деревьев.

Теорема 1.6. Графнчоская последовательность вида (I) является Т - униграфической тогда и только тогда, когда р

¿7- «.-£

и Л удовлетворяет хотя бы одному из условий:

О ) р-2 или с1х=£;

(¿¿) с£, - = <±5>{% с1<, = 1\

(Ш)

Обозначим через С/ класс связных унщиклических графов.

Теорема 1.7. Последовательность вида (I) является \] - униграфичесхой тогда и только тогда, когда удовлетворяет одног«1у из условий.

(I) р>5 я = с1р-&

Си) а^-З *

Теорема 1.6 и теорема 1.7 характеризуют Т и С/ -униграфическяе последовательности, где Т и (/ означают свойства "быть деревом" и "быть связным унициклическим графом" соответственно.

При исследовании униграфов Р.Й.Тынкевич и Д.АДерняк /9/ решили задачу характеризации двудольных униграфов с задан-нем разбиением. Двудольный граф с долями А и В называется двудольнш униграфом с заданным разбиением, если он до изоморфизма определяйся неупорядоченной парой ,

последова тельпостей степеней долей , .

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

. Заметим, что проблема нахождения двудольной реализации ■ последовательности в общем случае значительно сложнее, чем нахождение двудольной реализации паря последовательностей (см. /II/).

.Заметим, что условие отсутствия в графа изолированных вершин (в формулировке теоремы 1.7) не ограни-сигает общности, так как удаление изолированных вершин приводит либо к связному графу,: либо к рассмотренному случаю.

3 главе П рассматриваются вопросы графичности и унигра-фачности .в теории степенных множеств.

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

Итак, множество натуральных чисел вида } где о*. ■&, •• называется степенным множеством графа (у , если оно совпадает. с ыноас-ством степеней вершин графа (у- .

Для графа С- обозначим через степенное

множество.

Хотя степенная последовательность графа удовлетворяет определенным условием, однако степенным множеством графа может

II'

(быть произвольное множество /16/.

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

1) Пусть 5 - конечное множество натуральных чисел, р - натуральное число, Р - теоретико-графовое свойство,

ч Является ли дара р) Р - графической, т.е. существует ли граф Сз порядка р со степенным множеством 3 - реализация пары ( 5, р) , обладавший свойством Р ?

2) Определить наименьший порядок графов со степенным множеством Б , имеющих свойство Р .

Задача (I) созвучна' задаче о потенциально Р-графических последовательностях. Однако с задачами (I) и (2) связано значительно меньше завершенных исследований.' Это объясняется как отсутствием подходов к их решению, так и относительной молодостью этого раздела теории.

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

Графические дары описаны Шипкой /18/. Ранее Капур, Поп-лени и Уолл /16/ доказали реализуемость множества й вершинным графом, где - максимальный в 5 элемент.

Униграфические пары, т.е. пары с единственной реализацией, описаны А.А.Черняком /13/. Р.К.Тышкевич /20/ отметила, что множество 3 имеет единственную пороговую реализацию, причем число вершин в ней равно .

Н.Э. Зверовичем было замечено, что реализуемость пары ( 5, р ) деревом равносильна разрешимости в целых положительных числах уравнения р

1-г

Хотя распознавание разрешимости этого уравнения является NP -полкой задачей, тем не менее сведение задачи с существования дерева к распознавании разрешимости уравнения (4) позволяет получить алгоритмы с временной сложностью О (пхп.) , устанавливающий реализуемость п^ры деревом и строящий (при положительном ответе) такую реализацию /7/.

Б нашей диссертации исследуется задача характеризации пар (5, р ) , где S - некоторое множество натуральных чисел и р - число реализуемых в классе графов со свойством . Здесь в качестве J рассматриваются свойства "бить ациклическим графом". Найдены необходимое л достаточное условия циклической ушгграфичности указанных яар.

Для рассматриваемого нами вопроса сформулируем задачу dpi

более точно. Пусть J - некоторое теоретико графовое свойство и будем писать

fs,p)— Г если J граф G 6 имеющий порядок а степепенное множество S . Скажем, что пара (S, р) является - униграфической, если существует единственный (с.точностью до изоморфизма) граф G 6 имеющий, порядок Р и степенное множество S

В теореме 2.1 полностью охарактеризованы пары CS, р) , удовлетворяющие условию

где

Л - множество

ациклических графов.

Теорема 2.1 С5, р) '—-'Л

тогда и только тогда,

когда выполняется одно из условий:

1) ир+пв : ¿>i}

2) i и множество S содержит четный элемент и вылол-

п

нкегея условие

2: а£ : ы I >

L'i

где i0~ пгш.{&.6 $ z & i четно } .

Хотя эта задача близка к задаче рассмотренной в /?/ идя деревьев, результаты по существу различные. Из тэоромн 2.1

еле дуэт линейный алгоритм проверки ( р ) -—— Л ( Л - множество ациклических графов), а распознавание условия ( 5 , р) —Т , где Т множество.всех деревьев, является полной задачей /7/.

В теореме 2.2 охарактеризованы Л - униграфические пары для свойства Л - "ци. личность".

Теорема 2.2. ^ 5, р ) —- Л Тогда пара (5,р) униграфична, если и только если выполняется одно из условий:

1) ( -('{*}

2) С 3,р) =({¿,2^1}, 2^0, <Х4г 1\

3) *=({1,га}, 2сс+2т-1), ¿¿пг^а;

4) Г5,р) = Г{*,2а}, 4а};

5) ( Б.р)= 5 + с), ¿¿6±с.

В работе /14/ введено понятие - степени вершины V" как числа мостов, инцидентных вершине V . Очевидно, что ЬсСе^ V 4 сСе^гг В/14/изучаются множество & - степеней вершш графа.

Множество назовём -шокеством, если оно реализуется как список & - степеней вершин расщепляемого графа. В § 2.2 охарактеризованы Ь - множества. Стандартной задачей теории 'степенных множеств является вычисление минимального порядка реализации, обладащей заданным свойством /16,6, 8, 7, 12/. Минимальный порядок'расщепляемой реализации множества вычислен в До/. Мы решили эту задачу для Ь - множеств.

Обозначим через ~ порядок минимальный по

числу вершин расщепляемого реализации мшюства В .

Те орет 2.3. Множество

бв^,...;^, / является

' -Множеством тогда и только тогда, когда либо

либо * « 6 , '

Теорема 2.4. 4

Пусть ) " * 1

либо , либо ¿> . Тогда

■ Л(в>

1 , если I* а $ и ^ Л х.

»

£

» если £ = ■ и

£

2 ■£. если х. к.

21-£с если ¿«2, и

^ 2 С' в осгальныХ случаях.

д=»

ЛИТЕРАТУРА

1. Зверович В.Э., Зверович Н.Э., Силла А. Насколько результатов о вынужденно а -раскашиваемых и вынуздеяно I - циклических последователях J J Минск, 1988. Дед. в ВИНИТИ 12.04.1988,

J 2790, 88, 13 с.

2. Зверович И.Э. Вынужденно 3-раскрашиваемых степенные последовательности. Вопросы алгоритмического анализа структурной информации. Новосибирск, 1987. Вып. 119. Вычислительные системы. С.34-42.

3. Зверович И.Э. Доказательство гипотезы о подграфах регулярно-толерантных графов и необходимое условие вынужденной

П - раскрашиваемое™ последовательностей // Редк. ж. Вестн. Белорус, ун-та. Сер. I, физ.-мат., мох. Минск, 1988. 6 с. Деп. в ВИНИТИ 13.01.1988, J2 204-В88.

4. Зверович И.Э. О неравенствах Эрдеша-Гаякаи // Изв. АН БССР. Сер. физ.-мат.н., IS89, Л I.C. 28-36.

5. Зверович Н.Э., Силла А. Р - униграфичность в некоторых классах графов JJ Вестн. Белорус, ун-та. Сер. I.I99I. $ I.

С. 41-44.

6. Силла А, В - степенные множества. Деп. в ВИНИТИ, .1990.

7. Силла к. Л- циклическая графичность и униграфичность пар в теории степенных множеств графов. Деп. в ВИНИТИ, 1991.

8. Силла А. Одно дополнение к характеризации биуниграфов. Деп. в ВИНИТИ, 1991.

9. Тышкевич Р.И., Черняк A.A. Униграфы Л // Изв. АН БССР. Сер. физ.-мат. н. 1979, & I. С.5-12.

10. Тышкевич Р.И., Черняк A.A., Черняк Ж.А. О вынужденно Р -графических последовательностях J J АН БССР. 1981. У» 8. С. 677-680.

11 ТишквЕНч Р.И., Черняк А.А.., Черняк 2. А. Графы и степенный последовательности. Кий., J6 6. С.12-19.

12 Харари Ф. Теория графов. !Л., 1973. С.

I 3 Черняк А.А. Степенное мно;пэство графа и гамильтоновость.// Докл. АН БССР. 1987, T.3I, J5 12, C.I005-I068.

14 Chartrand G., Saba F. Bridge and cycle degrees of vertices of graphs. Internat. J. Math, of Math.Sci. 1984. V.7,

Ко 2, p.351- 360.

15 Exgo P., Harary P. iChe forcibly tree and unicycles degree sequences. // Elem. Math., 1982, V.37. No 2, p. 41-46.

16 Li S.X.R. Graphic sequences with unique realizations // J.Comb. Theory, ser.B, 1975, V.19, No 1, p.42-68.

17 Rao S.B.A. Survey of the theory of potentially P-graphic and forcibly P-graphic degree sequences // Lect. Notes Math., 1981, V.385, p. 417-440.

18 Bipka T.A. The orders of graphs with prescribed degree sets.// J.Graph Theory, 1980, V.4, Ho 3,p.301-307.

19 Teylor R. Constrained switchings in graphs // Lect. Hotes Maths., 1981, V.834, p.314-336.

20 Tyskevish H.I, Onoe more on matrogenic graphs // Disor. Math, 1984, 7.51, p. 91-100.