Введение к работе
Актуальность темы. В конце 50-х и начале 60-х годов началось интенсивное изучение степенных инвариантов графов, которое стало важным разделом теории графов. С этого времени наблюдается активное нарастание интереса к теории степеиних последовательностей графов. Это связано, в первую очередь, с естественным стремлением выявить зависимость структуры и свойств графа от легко вычисляемых инвариантов.
В работах П.Эрдеша, Т.Галлай, С Л Даними, В.Гавела, Г.Дя.Райзеря, Дж.Сеныора, Д.Тейпа, Д.Р.Фалкерсона, М.Х.Мак-Эндрю, А.Хофдмана, Дж.Эдаондса к Других авторов в 1950-1960 гг. было положено начало такого подхода к изучению графов. Полученные результаты касались не только графов, по и других близких к ним объектов (мультиграфов, пседографов, ( ОД)-" матриц). Получено большое количество результатов характерлза-ционного типа. Другом важной причиной этих исследований является прикладная значшоогь рассматриваемых вопросов. Достаточно указать на такие области, как химия структурных изомеров и теория надежности систем. Выявлена гаме связь теории степенных последовательностей с другими разделами дискретной математики.
Наиболее интенсивные исследования велись по изучению вершинных- степенных последовательностей и ассоциированных с ни/и объектов (степенные множества, частотные разбиения). Многие задачи были решены. Однако остается очень много открытых проблем. Например, проблема существования двудольного графа с заданной степенной последовательностью или с заданным степенным множеством.
Интерес или важность того или иного степенного инварианта во многом зависит от его информативности, болнлоэ значение которой определяется приложениями. Известны различные обобщенные степенные последовательности - реберные, дистанционное, цехшые, распределительные матрица. Однако, изучение этих инвариантов показало, что их дифференцирующая способность невелика даже в таких узких классов графов, как деревья. Отсюда понятна необходимость построения и исследования более сильных степенных характеристик графов.
С учетом сказанного тема диссертации представляется актуальной.
' Цель работы. Решение задач, связанных с циклическим отроением графа. Изучение зависимости структуры графа от степенных инвариантов о целью получить условия графичности и однозначной реализуемости.
. Научная новизна. I. Найдено иоеоє необходимое условие вынужденной п -рэскрашиваемости последовательности целых чисел, т.е. реализуемости'последовательности только в классе /z. -раскрашиваемых графов. Эти условия независимы от известных результатов на эту тему. Решена еще одна известная проблема: харастеризация вынужденно I -циклических последовательностей, 2±6 .в частности, усиливается изве-стпый результат Г.Иксу и Ф.Харари.о вынужденно і -циклических последовательностях. Дается полная характеризация степенных последовательностей кактусов.
2. Исследована Р -униграфичность в некоторых классах графов.
. Класс ' -униграфических последовательностей содержит как подкласс униграфические последовательности, реализации которых обладают свойством Р . Охарактеризованы / и
^ униграйические последовательности, где Т и U означают свойства "быть деревом" и "быть .связнш уницикличео-ким графом" соответственно.
Условия граГоичности и униграфичкоста пшроко.изучаются в работах Тышкевич Р.И. и Черняк А.А. 3 то ке время характериза-цконкых результатов, касающихся Р - укиграфичности последовательностей, практически нет. Хотя рассмотрение таких последовательностей естественно и тлеет практическое значение при генерировании графов с заданными свойствами, изучение изомеров некоторых химических соединений и т.д.
-
Получено одно дополнение к характеризации биуниграфов. Бешена задача характеризации несвязных биуниграфов. Для связных графов аналогичная задача биушіграфичности с разбиением на дола решена Р.И.Тншкевич к А.А.Чорнякоы.
-
Охарактеризованы пары ( о, р ), где О - множество натуральных чисел, р - число, для которых существует ациклический граф порядка р , степенное множество которого совпадает с 5 . Найдены условия однозначной реализуемости указанных пар в классе ациклических графов.
-
Охарактеризованії far -множества и найдено необходимое и достаточное условие при которых множество В является
Ь - множеством. Вычислен минимальный порядоку и - множества.
Практическая ценность. Результати диссертации могут бить использованы з теоретических исследованиях по теории графов. Из конструктивних доказательств результатов вытекают алгоритмы построения соответствующих реализаций.
Прикладное значение для химии изомеров имеют результаты, касающиеся Р - униграфичиости последовательностей.
Апробация. Основные результаты диссертации докладывались
на научно-исследовательском семинаре по теории графов в Белорусском государственном университете.
Публикации. Основные результати диссертации опублико
ваны в работах Д» 5-8/.
Структура и объем работы. Диссертация состоит из введения, двух грав и списка литературы (64 наименований).