Содержание к диссертации
Введение
Глава I. Основные определения и понятия 13
I. Основные оцределения теории графов 13
2. Раскраска графов. Хроматический многочлен графов 19
Глава II. Однозначно и локально однозначно раскрашиваемые графы 24
I. Однозначно раскрашиваемые графы с наименьшим числом ребер 24
2. Класс 1С -деревьев 33
3« Элементарные двудольные мультиграфы 45
4. Локально однозначно раскрашиваемые графы 52
Глава III. Хроматический многочлен графов 62
I. Хроматически эквивалентные и биэквивалентные графы 62
2. Сильно и слабо циклические графы с целочисленными хроматическими спектрами 71
3. Хроматически единственные графы и классы графов 78
Литература 85
- Раскраска графов. Хроматический многочлен графов
- Класс 1С -деревьев
- Локально однозначно раскрашиваемые графы
- Сильно и слабо циклические графы с целочисленными хроматическими спектрами
Введение к работе
В настоящее время графы и связанные с ними методы исследований органически цронизывают на разных уровнях едва ли не всю современную математику. Теория графов эффективно используется в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине. Теория графов находит широкое применение в таких областях прикладной математики, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач. В то же самое время теория графов вместе со смежным с ней комбинаторным анализом постепенно превращается из набора искусственных приемов решения отдельных задач в стройный и цельный раздел современной математики.
Одним из центральных разделов теории графов являются задачи раскраски графов, возникшие в связи со знаменитой проблемой четырех красок (решенной спустя 100 лет Аппелем и Хакеном [9, 10]).
Сама по себе проблема четырех красок едва ли имеет какие-либо важные приложения. Однако эта проблема сыграла большую роль в развитии всей теории графов. Попытки ее решения привели, в частности, к продвижению двух следующих направлений: чисто комбинаторной характеризации пленарных графов и изучения хроматических свойств графов общего вида, каждое из которых, как известно, имеет непосредственное применение и в чистой математике, и в практике.
Насколько трудна задача раскраски графов, показывает принадлежность к классу Л/Р -полных задач даже таких частных задач, как раскрашиваемость графа в 3 цвета [4] или рас-
_ 4 -
краска пленарных однородных степени 4 графов \8].
Вряд ли стоит здесь пытаться рассмотреть все направления исследований в раскраске графов. Вместо этого лишь укажем направления, к которым принадлежат результаты предлагаемой диссертации: изучение структур однозначно раскрашиваемых или близких к ним по свойствам графов, установление связей между хроматическим многочленом и некоторыми характеристиками графов.
Диссертация состоит из введения и трех глав. Для удобства читателя нумерация теорем и т.д. трехиндексная, новые результаты начинаются с цифры, означающей номер главы, далее идут номер параграфа и порядковый номер соответствующего утверждения, ранее известные результаты начинаются с первых трех букв А, Бг и В русского алфавита, соответственно относящих .эти результаты к одной из трех глав.
Переходим к обзору основных результатов диссертации.
Раскраска графов. Хроматический многочлен графов
Одним из центральных разделов теории графов являются задачи раскраски графов, возникшие в связи со знаменитой проблемой четырех красок (решенной спустя 100 лет Аппелем и Хакеном [9, 10]).
Сама по себе проблема четырех красок едва ли имеет какие-либо важные приложения. Однако эта проблема сыграла большую роль в развитии всей теории графов. Попытки ее решения привели, в частности, к продвижению двух следующих направлений: чисто комбинаторной характеризации пленарных графов и изучения хроматических свойств графов общего вида, каждое из которых, как известно, имеет непосредственное применение и в чистой математике, и в практике.
Насколько трудна задача раскраски графов, показывает принадлежность к классу Л/Р -полных задач даже таких частных задач, как раскрашиваемость графа в 3 цвета [4] или рас _ 4 краска пленарных однородных степени 4 графов \8].
Вряд ли стоит здесь пытаться рассмотреть все направления исследований в раскраске графов. Вместо этого лишь укажем направления, к которым принадлежат результаты предлагаемой диссертации: изучение структур однозначно раскрашиваемых или близких к ним по свойствам графов, установление связей между хроматическим многочленом и некоторыми характеристиками графов.
Диссертация состоит из введения и трех глав. Для удобства читателя нумерация теорем и т.д. трехиндексная, новые результаты начинаются с цифры, означающей номер главы, далее идут номер параграфа и порядковый номер соответствующего утверждения, ранее известные результаты начинаются с первых трех букв А, Бг и В русского алфавита, соответственно относящих .эти результаты к одной из трех глав. Переходим к обзору основных результатов диссертации. Глава I содержит основные определения и обозначения. Вторая глава посвящена однозначно к-раскрашиваемым графам, о которых при к З известно мало. Более того, доказано, что задача распознавания однозначной к -раскрашиваемости к-раскрашенного графа при к}3 принадлежит классу /VP-полных проблем [8J. Основной результат I связан с гипотезой: каждый однозначно 4-раскрашиваемый планарный граф имеет минимальную степень, равную 3. Здесь рассматривается класс ІА однозначно к-раскрашиваемых графов с наименьшим числом ребер. В частности, класс и4 содержит все однозначно 4-раскрашиваемые пленарные графы. В теореме 2.I.I доказано, что для любых къ-2. и k-4 S 2k-3 в классе Zi существует граф G с минимальной степенью of(a)ao .Из этой теоремы вытекает, что в Vr существуют графы с минимальной степенью 4 или 5, причем из конструктивного доказательства следует их непланарность.
Вышеуказанная гипотеза больше известна в своей двойственной форме [l5, I6J: каждый однозначно 3-реберно-раскраши-ваемый пленарный кубический граф содержит треугольники. Тат-том [lb] было показано, что требование планарности в этой гипотезе также существенно.
Если относительно однозначно 4-раскрашиваемых пленарных графов осталась нерешенной одна гипотеза (о минимальной степени) , то в случае однозначно 3-раскрашиваемых пленарных графов с каждой новой работой ситуация усугубляется. Много интересных результатов и нерешенных задач приведено в работах [ІІ-ІЗ]. Например, Мельниковым и Стейнбергом [із] одним контрпримером опровергнуты сразу две весьма правдоподобные гипотезы об однозначно 3-раскрашиваемых планарных графах.
Класс 1С -деревьев
Вспомогательный 3 содержит результаты о двудольных элементарных мультиграфах, на первый взгляд не относящихся к теории раскрасок. Но в следующем параграфе показывается тес - 6 ная связь этих мультиграфов с локально однозначно раскрашиваемыми графами.
Как показал Ловас [26, 27], элементарные двудольные графы играют важную роль в изучении структур факторизуемых графов (графов, имеющих I-фактор). Изучение последних является одной из проблем, важных как для самой теории графов, так и для многих ее приложений.
Впервые в [19] Харари, Хедетниеми и Робинсон показали, что необходимое условие однозначной к -раскрашиваемости -то, что G принадлежит СкД) , где 2 "Ь к-1 -не является достаточным при -Ь. «X . Обобщая их результаты, Ни-ейминен [25] показал, что дополнение цикла Qk принадлежит классу % (k, \с-Л) » но не является однозначно к -раскрашиваемым, т.е. Qk ф IkiMM) «Из этого следует недостаточность необходимого условия при любом "t , где 2"Ь к-1. Пусть даны граф 6j и две его произвольные к -раскраски "Ц и -у . Мультиграфом раскрасок MfeiVuVa.) на зывается мультиграф М , вершинами которого служат одноцветные классы раскрасок tyn и Ц)и , и две его вершины соединяются ha -кратным ребром тогда и только тогда, когда соот - 7 ветствующие им классы имеют Уг\ %. общих элементов. По определению к -раскраски мультиграф раскрасок является двудольным с к вершинами в каждой доле Один из основных результатов диссертации содержится в следующих трех утверждениях. ТЕОРЕМА 2.4.1. Пусть М - произвольный элементарный двудольный мультиграф с 2 к вершинами, W»2. . Тогда дополнение его реберного графа является неоднозначно к -раскрашиваемым графом класса Так как четный цикл есть двудольный элементарный граф, пример Ниейминена [25] является частным случаем этой теоремы. ТЕОРЕМА 2.4.2. Пусть \р« - такая к -раскраска графа , что (3,(- ) K k-l) и пусть Gi U(kX) . Тогда для любой к -раскраски "Ч 4 "Ц мультиграф раскрасок Ai = = {d; Vi V .) является двудольным и элементарным. Причем, если d является (Vi 4 i) - максимальным (т.е. граф (а содержит все ребра, не нарушающие правильность к -раскрасок \f 1 и "Ц\ ), то (3, изоморфен дополнению реберного графа мультиграфа М . ТЕОРЕМА 2.4.3. Если р- вершинный граф (д из класса ((kj-b) 2 -і кИ , имеет минимальную степень (») k-1 k-1 , то Gi - однозначно k -раскрашивае мый граф. Частный случай этой теоремы при »2. доказан Болло-башем [5, 24]. Глава Ш посвящена хроматическим многочленам, которые впервые были введены Биркгофом и Льюисом [34] в попытке решить проблему 4-х красок. В этом направлении продолжают рабо - 8 тать Татт [29, ЗО], Рут Бари [44] и др. После статьи Рида [35], где указываются нерешенные проблемы и некоторые практические применения хроматических многочленов, появилось много работ по другим направлениям; изучение хроматически эквивалентных графов [44, 45], корней хроматических многочленов [37, 40, 41] и т.д.
В последние годы большое количество работ [31-33]посвя-щено различным многочленам, определенным на графах. Наиболее развитой и интересной является спектральная теория (или теория характеристических многочленов) графов, которой посвящена монография Цветковича, Дуба и Закса [7].
Одним из интересных результатов о коспектральных графах (графах, имеющих один и тот же характеристический многочлен) является результат Швенка [5l]: для достаточно больших р почти для каждого р -вершинного дерева найдется ему неизоморфное и коспвктральное дерево.
В I рассматриваются хроматически эквивалентные графы, т.е. графы, имеющие один и тот же хроматический многочлен. Очевидно, что изоморфные графы хроматически эквивалентны. Однако часто несколько неизоморфных графов имеют один и тот же хроматический многочлен. Например, у всех деревьев с р вершинами один и тот же хроматический многочлен.
Более того, оказывается существуют неизоморфные хроматически эквивалентные графы с хроматически эквивалентными дополнениями. Здесь такие графы называются хроматически биэк-вивалентными. Доказывается теорема 3.1.1: для любого п .2 существуют п попарно неизоморфных хроматически биэквива-лентных графов. Как следствие теоремы 3.1.2 и результата Швенка [51] показывается, что доля р -вершинных деревьев, для которых не существует хроматически биэквивалентного дерева, стремится к нулю при р - оо . Предполагаем, что аналогичное утверждение верно и в классе всех графов с р вершинами при р - со В некотором смысле в пользу этого предположения говорит утверждение теоремы 3.1.3: при всех р}8 вида 4п и 4к + 1 существуют не самодополнительные графы, хроматически эквивалентные своему дополнению. Заметим, что в теории характеристических многочленов известны только примеры 8 и 9-вер-шинных несамодополнительных графов, коспектральных своему дополнению [49]. В 2 содержится второй основной результат диссертации - опровержение гипотезы Брауна, Крётца, В. Вальтера и М.Вальтера [4l]. Они доказали, что хроматический многочлен произвольного сильноциклического графа (или триангулированного графа, или графа без дырок) имеет только целочисленные корни и предположили, что верно и обратное.
Как показали Хайнал, Шураньи [43] и Берж [42], сильноциклические графы и их дополнения являются совершенным графами. Последние привлекают широкий интерес в связи с известными гипотезами Бержа о совершенных графах [42], Отметим, что совершенным графом посвящена недавно вышедшая монография Го-лумбица [б].
Примеры 5-дырочных графов с целочисленными хроматическими спектрами, приведенные в 3 третьей главы, показывают существование несовершенных графов, хроматически эквивалентных триангулированным, т.е. совершенным, графам.
Локально однозначно раскрашиваемые графы
Одной из основных нерешенных задач теории хроматических многочленов остается описание графов, имеющих один и тот же данный хроматический многочлен [35, 44]. Результаты 2 показывают, насколько трудна данная задача даже в классе графов, имеющих в качестве хроматического многочлена многочлен с целочисленными корнями.
Под графом подразумевается конечный неориентированный граф без петель и кратных ребер. Граф G» задается парой (V, Е) , где V - конечное непустое множество, элементы которого называются вершинами, а Є - антирефлексивное симметричное бинарное отношение (смежности) на множестве вершин V . Каждую пару e=.(x y) вершин в называют ребром графа (а и говорят, что вершины х и у смежны между собой и инцидентны ребру е . Обратно, если задан граф в , то множества его вершин и ребер обозначаются через V{G\) и Е(&) . Граф с р вершинами и а ребрами называется (Р)Я ) -графом.
Граф называется помеченным, если его вершины отличаются одна от другой какими-либо пометками, например, Х х . Хр Два помеченных графа G и 6 изоморфны (записывается (S, ( или просто (5,- )» если между их множествами вершин существует взаимно-однозначное соответствие, сохраняющее смежность.
Если в графе две несоседние вершины некоторого простого цикла или простой цепи смежны, то ребро, соединяющее их, называется хордой. Ясно, что в случае цикла это возможно, когда цикл имеет длину не менее четырех. Граф называется связным, если любая пара его вершин соединена цепью. Максимальный (по включению) связный подграф некоторого графа называется компонентой связности. Граф называется ациклическим, если в нем нет циклов. Дерево - это связный ациклический граф. Каждый граф, компонентами связности которого являются деревья, называется лесом. Расстояние е4(х у) между двумя вершинами х и у графа ( равно длине кратчайшей простой цепи, соединяющей их. В полном графе гСР каждая пара его р вершин смежна. Дополнение Кр полного графа называется пустым графом. Под к. -КЛИКОЙ графа понимается некоторый его k -вершинный полный подграф, не обязательно максимальный. Двудольный граф ( это граф, множество вершин V которого можно разбить на два подмножества Ц и 1( таким образом, что каждое ребро ($ соединяет вершины из разных - 16 множеств. Если двудольный граф Gi содержит все ребра, соеди няющие множества Ц и Й. , то этот граф называется пол ным двудольным. Если при ЭТОМ М И и va.e к t то будем обозначать его через KMiK . Аналогично даются поня тия V» -дольного и полного Y -дольного графов. Пусть графы йц и Gt имеют непересекающиеся множества вершин Ц и V4 и, поэтому, непересекающиеся множества ребер Еп и Ег , Для таких графов определяются следующие операции.
Граф (S называется планарным, если его можно начертить на плоскости так, чтобы никакие два ребра не пересекались в точках, отличных от вершин. Плоский граф - это граф, уже уложенный на плоскости без пересечений ребер. Максимальным планарным графом называется граф, который при добавлении любого ребра перестает быть планарным.
Пусть 5 - плоский граф. Тогда его гранью называется область плоскости, ограниченная ребрами и не содержащая внутри себя ни вершин, ни ребер. Две грани плоского графа называются смежными, если они имеют хотя бы одно общее ребро. Наконец, отметим, что у всякого плоского графа имеется одна, притом единственная, неограниченная грань, называемая внешней гранью, остальные грани называются внутренними.
Для данного плоского графа ( его геометрически двойственным (или просто двойственным) графом называется граф , который строится следующим образом: в каждую грань графа G (включая внешнюю) помещается по одной вершине графа ( и, если две грани смежны, то вершины,помещенные в них, соединяются ребром. Как следует из определения, двойственный граф плоского графа G также плоский. Понятно, что двойственный граф максимального плоского графа есть кубический плоский граф.
Сильно и слабо циклические графы с целочисленными хроматическими спектрами
Вышеприведенная гипотеза об однозначно 4-раскрашиваемых пленарных графах больше известна в своей двойственной форме: каждый однозначно реберно 3-раскрашиваемый кубический планарный граф содержит треугольник [15, 1б] . Ввиду теоремы Тейте-Волынского, перефразированной для двойственных графов, обе гипотезы равносильны [і].
Аналогично следствию 2.І.І, Таттом [l5j было показано существование однозначно реберно 3-раскрашиваемого непланарного кубического графа без треугольников.
Как и можно было ожидать, вопросы, связанные с однозначной (вершинной) 3-раскрашиваемостью планерного графа очень трудны. Это показывают результаты и нерешенные задачи, приведенные в работах [ll-13j. Понятно, что графы из & являются и-критическими, т.е. при удалении любого ребра полученный суграф уже не является однозначно к -раскрашиваемым, так как по определению класса Ьг у них нет "лишних" ребер. Но Мельниковым и Стейнбергом [із] было показано существование (даже пленарных) U -критических графов со сколь угодно большим числом "лишних" ребер, причем с дополнитель - 32 ным условием: в них нет треугольников с общим ребром. Заметим, что в случае однозначной 4-раскрашиваемости планарных графов осталась "только" одна нерешенная задача (вышеуказанная гипотеза о минимальной степени). ЗАМЕЧАНИЕ 2.I.I. В доказательствах теорем 2.I.I и 2.1.2 существенно использовалась операция частичного соединения (лемма 2.I.I). Определение этой операции и доказательства этих теорем показывают невозможность построения однозначно 4-раскрашиваемых планарных графов с нулевым вектор-дефицитом с помощью только операций добавления вершин (свойство Б.1.3), соединения графов (свойство Б.1.4) и частичного соединения. - 33 2. Класс к -деревьев Граф (5j с р2 к-И вершинами называется к -деревом (Ic o) , если он или совпадает с (Ьи) -вершинным пол ным графом, или получается из (р-1) -вершинного к -дерева добавлением новой вершины, смежной с каждой вершиной некоторой к -клики.
Из этого определения и свойства Б.1.3 следует, что любое р -вершинное к -дерево является однозначно (к-И)-раскрашиваемым графом с числом ребер р - С а. / Поэтому класс к -деревьев Т является подклассом известного нам класса Ч Понятно, что любое 1-дерево является деревом в обычном смысле. Описание и число неизоморфных 2-деревьев получили Ха-рари и Палмер [20]. Там же ими определено понятие 1 -плек-са как h-мерного симплициального комплекса, в котором каждый У -симплекс (г к) содержится в некотором к-симп-ликсе. В терминах к-плекса к-деревья охарактеризовали Байнеке и Пипперт [2l] В следующей теореме Роуза содержится другая характериэация к-деревьев. ТЕОРЕМА Б.2.1. [22] Граф ( является к -деревом тог да и только тогда, когда (I) граф ( связан; (2) граф ( имеет -клику, но не имеет ( -+2)-клику; (3) каждое минимальное множество вершин, разделяющих вершины х и у графа ( есть к-клика. В этом параграфе дается характериэация к -деревьев, связанная с раскраской графов. Сначала приведем некоторые определения и утверждения. Граф называется сильноциклическим (или триангулирован - 34 ным), если любой его цикл длины (.4 имеет хорду, т.е. более точно, если он не содержит (порожденного) подграфа, изоморфного простому циклу Сі при I 4 , В противном случае - слабоциклическим. Вершина графа ( называется симп-лициальной, если ее окружение порождает полный подграф в ( . Дирак [23] доказал, что сильноциклический граф всегда имеет симплициальную вершину.
Очевидно, что все к -деревья сильноциклические. ЛЕММА 2.2.1. Граф ( 2Д sT является слабоциклическим при любом k 2.. Доказательство. Предположим противное. Тогда в 4 существует симплициальная вершина. Она в силу однозначной (Ь-н) -раскрашиваемости имеет степень k . Отсюда простыми рассуждениями получаем, что ( - к-дерево. Противоречие. Лемма 2.2.1 доказана. Из определения k-дерева и теоремы Б.2.І немедленно следует ЛЕЖА 2.2.2. Пусть (дбТ и имеет р 2. вершин (к О . Тогда в к-дереве ( существует пара вершин X и у , окружения которых пересекаются по к -клике, причем эта к -клика является минимальным разделяющим множеством вершин х и у . В дальнейшем вершины и у , смежные с общей к -кликой Q , будем называть концами гиперребра [xQ VJ порядка к Понятно, что при (к-н) -раскраске к-дерева концы любого гиперребра получают один и тот же цвет, т.е. они всегда не смежны. ЛЕММА 2.2.3. Пусть T и CxQk.v] -некоторое его гиперребро. Тогда граф ( , получающийся при отождес - 35 твлении вершин X и у , является 1 -деревом. Доказательство. Заметим, что число ребер будет 11- _ її і і , /.L.J./U lEC s )l-lE(s)-k-(p- -CD и G является однозначно С 47 -раскрашиваемым, т.е. граф ( It +А . Поэтому, согласно лемме 2.2.1, остается показать, что граф ( сильноциклический. Предположим, что G имеет цикл Q длины (. 4 без хорд. В силу леммы 2.2.2, граф («J является объединением двух своих подграфов, пересекающихся по к-клике Q (см. рис. 2). Обозначим их через &х и (ду Очевидно, что граф ($ , получающийся по сле отождествления вершин X и у , также является объединением двух подграфов, а именно подгра фов, совпадающих с (дх и 6у и пересекающихся по ( ) клике Qfc+fcay .
