Сужение, К-дефицит и раскраска гиперграфов

• Автор: Хачатрян, Мурад Арутюнович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Кишинев
• Количество страниц: 100 c. : ил

Глава I, Свойства гиперграфа инвариантные относительно

сужения ребер

§ I. Сужение ребер и к-дефицит гиперграфа

§ 2. Свойство ЇГС(КІ8) и сужение ребер гиперграфа

§ 3. Свойство ИКХСк,^) и К-дефицит

§ 4. Алгоритм вычисления К-дефицита

Глава II. Раскраска гиперграфов

§ 5. Оценка хроматического числа гиперграфа

§ 6. Раскраска ребер гиперграфа в смысле

Нэш-Вильямса

§ 7. Матроиды на гиперграфах

§ 8. Алгоритмы
Заключение
Литература

Требования современной науки и техники, развитие экономики поставили перед математикой большое количество задач, решение которых невозможно методами анализа непрерывных величин. Это привело к тому, что методам дискретной математики и комбинаторно-логическому анализу уделяется все возрастающее внимание. Современные модели экономических процессов, социальных процессов, биологических и химических процессов все чаще формулируются в терминах дискретных величин. Среди сложившихся отраслей науки, которые пользуются методами дискретной математики - исследование операций, теория игр, теория расписаний, математические методы проектирования электронно--вычислительной техники, математические методы в экономике и т.д.
Особая роль теории графов и гиперграфов в решении этих и других проблем во многом обязана простым и наглядным формулировкам различных задач в терминах теории графов. Притом круг задач, охватываемых этой теорией необычайно широк, среди них как практические задачи, так и теоретические [20] . Непрерывному развитию теории графов и гиперграфов способствуют и проблемы, возникающие и в самой теории графов.
Возникновение теории графов как самостоятельного раздела математики часто связывается с проблемой четырех красок. Если кто-то в этом может и усомниться, то наверняка можно утверждать, что "Раскраска", как раздел теории графов, обязан своим появлением именно проблеме четырех красок, и во многом благодаря сложности ее решения [ 23,24,II,12,19^

Попытки решить проблему четырех красок привели к понятиям раскраски графа, хроматического числа графа, рода графа, и к целому ряду результатов по раскраске графов. Среди таких результатов можно отметить два направления: оценка хроматического числа графа заданного класса, и разработка алгоритма, находящего "хорошую” в некотором смысле раскраску графа заданного класса. Особое значение эти направления приобрели в связи с открытием класса - полных проблем и тем, что задача раскраски принадлежит этому классу. Этот факт еще больше усилил важность теорем оценочного типа и приближенных, но эффективных алгоритмов раскраски.
Продолжительные исследования по проблеме раскраски привели к целому ряду обобщений классической задачи раскраски графа. Среди них можно отметить следующие: раскраска ребер графа так, чтобы смежные ребра были окрашены в разные цвета, сильная раскраска гиперграфа, раскраска гиперграфа в смысле Эрдеша - Хайнала (слабая раскраска), раскраска ребер графа в смысле Нэш-Вильямса (так, чтобы не было одноцветных циклов) и т.д. Возможны и многие другие обобщения понятий раскраски графа и гиперграфа.
Настоящая работа посвящена исследованиям по раскраске гиперграфа в смысле Эрдеша - Хайнала и обобщению на гиперграфы раскраски в смысле Нэш-Вильямса.
Напомним, что гиперграфом называется тройка Н -(Х^ К) N , где Л - множество вершин, и - множество ребер, а Я - двуместный предикат, задающий инцидентность между вершинами и ребрами. Множество вершин, инцидентных заданному ребру 71 е II и множество ребер, инцидентных заданной вершине

Щ(У) 4 к/У+$-1.
Но (У) ^ /17г (У) , поэтому
/ПН(У) й К,/У/ + Ь
откуда следует, что И удовлетворяет условию 7?? (л/, £,-^) • Противоречие доказывает следствие 3.2.