Введение к работе
Актуальность темы. Строение плоских графов привлекает математиков начиная с открытия Эйлером знаменитой формулы В - Р + Г = Z для многогранников. (Согласно теореме Штейница 1922 г., эйлеровы многогранники взаимно-однозначно соответствуют 3-связным плоским графам.) Уже Лежандру было известно CIS, с. 273 о существовании в любом многограннике вершины и грани ранга не более 5, а также либо вершины ранга 3, лиоо грани ранга 3 (ранг - это число инцидентных ребер). Важную роль в изучении строения плоских графов общего вида сыграла теория эйлеровых вкладов, предложенная Лебегом в 1940 г. Оборотной стороной универсальности и простоты этого подхода является его недостаточная- разрешающая способность: легко получаются всевозможные приближенные оценки, но как правило не удается получить неулучшаемых структурных характеристик. В частности, более тонкие соображения потребовались Коцигу [14] для доказательства в 1955 г. теоремы о том, что минимальный вес ребра (сумма степеней концевых вершин) в многограннике не превосходит 13 (оценка точна). Но и после этого долгое время не удавалось ответить на многие естественные вопросы о строении плоских графов, поставленные Лебегом С18], Коцигом [14-16], Юцовичем [13], Грюнбаумом [10-12], Пламмером [20, 21] и другими. Часть этих задач решена в данной диссертации.
Большое число работ за последние сто лет было посвящено изучению плоских графов специального вида, а именно, класса Т плоских триангуляции с минимальной степенью 5. Дело в том, что фактически именно Т является объектом исследования в известной задаче о четырех красках, поставленной в 1654 г. Гатри. Полученное Аппелем и Хакеном в 1976 г. решение состояло в построении неизбежной системы из почти полутора тысяч сводимых конфигураций. Другими словами, был найден такой набор структурных фрагментов, что в люоой триангуляции встречается хотя бы один из этих фрагментов, и в то же время ни один из фрагментов не может содержаться в минимальном контрпримере к теореме о четырех красках. Важным промежуточным пунктом в этих
исследованиях стала теорема Лебега 1940 г., описывающая строение окрестностей 5-вершины в Т . Б этом описании была еще очень слаба связь с 4-раскраской; многие конфигурации не являлись сводимыми. Далее Хееш разработал теорию того, как погружать имеющуюся систему конфигураций в более мощные системы конфигураций, сводимых по внешним признакам. Суть его подхода - в последовательной замене конфигураций, оказавшихся несводимыми, на серии объемлющих конфигураций с большими шансами быть сводимыми. В итоге программа Хееша и была реализована Аппелем и Хакеном в результате больших вычислений вручную и массированного применения ЭВМ.
Из приведенного примера видна роль структурных результатов в решении задач раскраски плоских графов.
Цель работы. В диссертации прослеживаются связи между задачами цикловой, совместной и предписанной раскраски и верхними оценками минимального веса ребра и грани для некоторых классов плоских графов. Полученные результаты являются, как правило, неулучшаемыми и позволяют ответить на ряд вопросов, поставленных в 60-70 гг. Рингелем, Коцигом, Грюнбаумом, Юцовичем, Пламмером, Кронком и другими.
Научная новизна. В диссертации получена новая довольно подробная информация о строении окрестностей ребра и грани в плоских графах. Ранее были известны в основном приближенные верхние и нижние оценки для ряда структурных характеристик, принадлежащие Вернике, Франклину, Лебегу, Оре, Коцигу, Грюн-Оауму, Пламмеру, Юцовичу, Тофту и другим исследователям.
Обнаружена тесная связь между задачами- Рингеля о 6 красках и Оре и Пламмера о цикловой раскраске (1966) с задачей о циклической связности Грюнбаума (1975) и оценками на вес грани в триангуляции Лебега (1940) и Коцига (1963, 1976).
Разработан подход, позволивший решать задачу о совместной
раскраске вершин, ребер и граней Кронка и Митчема (1973),
входящую под номером 1.10 в список Тофта [24], и задачу о
. предписанной раскраске ребер плоских графоь на основе новых
теорем коциговского типа о весе ребра.
Эти связи между старыми и казавшимися разрозненными
задачами и составляют идейную основу диссертации. Главные же технические трудности, преодоленные в работе, состояли в адаптации метода перераспределения вкладов к задачам о весе ребра и грани. До этого применялись лишь простые соображения, основанные на равномерном распределении вкладов (Лебег, Оре, Пламмер, Гофт) и в лучшем случае учитывалась неповторяемость вершин степени не более 5 (младших) в окружении вершин (Франклин, Коциг, Юцович).-
Таким образом, ядром диссертации является блок преимущественно неулучшаемых результатов о строении окрестности ребра и грани в различных классах плоских графов и основанные на них оценки для цикловой, совместных и предписанной раскрасок. Этот материал содержится в главах і и 2. Ряд новых результатов о строении и раскраске графов, уложенных на плоскости и других поверхностях, приводится в главе 3.
Среди результатов диссертации центральное место занимает
(а) решение задачи Рингеля' (1965 г.) о 6 красках [26]. Теорема
о 6 красках, допуская формулировку в терминах 1-вложимости
(теорема 2.1), цикловых (теорема 2.і') и совместных раскрасок
(теорема 2.1.."), подтолкнула исследования во всех трех
направлениях. Как раз накануне решения задачи Рингеля.
Бодендик, Вагнер и Шумахер [7] опубликовали в общематематиче
ском журнале статью с призывом к молодому поколению математи
ков заняться ею. Вскоре Бодендик Г.6] опубликовал там же сооб
щение о том, что задача решена дассергантом. Этот результат
уже успел войти ь обзоры и упоминается Харбортом в,предисловии
к книге, посвященной 70-летию Рингеля. Вскоре в Журнале теории
графов (США) выйдет найденное диссертантом новое доказатель
ство теоремы о 6 красках.
Другими основными результатами диссертации являются:
(б) подтверждение (за несколькими исключениями) предположения
xve < Д + 4 Кронка и Митчема (1973 г.) о совместной раскраске
'вершин, ребер и граней (теорема 2.6) и установление (за несколько большим числом исключений) неулучшаемой оценки х < < Д + 2 (теорема 2.7), где Д - максимальная степень графа;
(в) блок теорем коциговского типа о весе ребра (теоремы
1.5-і. 12);
(г) одновременное решение задач Грюнбаума (1975 г.) о цикличе
ской связности и Коцига (1963 г.) о весе грани в триангуляции
(теорема 1.16);
(д) решение серии задач Грюнбаума (1973 г.) и Юцовича (1974г.)
О ЧИСЛе "ЛеГКИХ" ребер (Теоремы 1.20-1.23);
(е) точная верхняя оценка хроматического числа графов, 1-вло-
Я1ИМЫХ в псевдоплоскость в смысле Кайнена (теорема 3.2);
(ж) теорема о диагональном преобразовании триангуляции ориен
тируемых поверхностей (теоремы 3.3 и 3.4).
Практическая ценность. Все доказательства в диссертации конструктивны и могут быть легко преобразованы в алгоритмы полиномиальной сложности. Развиваемый в диссертации подход к расшифровке строения плоских графов- может быть использован для получения еще более подробной структурной информации за счет вовлечения дополнительных входных параметров, что подтверждают последние результаты, не вошедшие в диссертацию. Приемы адаптации структурных результатов к задачам раскраски (погружение в замкнутый класс и т.п.) могут пригодиться и в дальнейшем. Бремя от времени возникают новые яркие задачи о раскраске плоских графов. При их решении глубокое знание строения плоских графов общего вида оказывается весьма полезным.
Апробация. Результаты диссертации докладывались на Совещании по теории графов в Самаркандском госуниверситете (1963); VII (Иркутск, 1965) и VIII (Горький, 1966) Всесоюзных конференциях по теоретической кибернетике; I, II и III Всесоюзных семинарах по дискретной математике и ее приложениям (Москва, 1964, 1967, 1990); Всесоюзной школе по теории графов и ее приложениям (Новосибирск, 1966); Первом Всемирном конгрессе общества математической статистики и теории вероятностей им.Бернудли (Ташкент, 1966); в лекциях XXX Семестра по комбинаторике и теории графов Международного математического центра им.Банаха (Варшава, 1967); в пленарных докладах на IV Чехословацком международном симпозиуме по комбинаторике (Пра-хатице, ЧСФР, 1990) и международных конференциях: "Дискретная
математика" (Айзенах, Германия, 1990), по теории графов памяти Юлиуса Петерсена (Хиндсглавль, Дания, 1990) и "Миноры графов" (Сиэтл, США, 1991) и Ежегодном собрании Германского математического общества (Дуйсбург, 1994), а также на научно-исследовательских семинарах Института математики СО РАН, Математического института Венгерской АН (Будапешт), университетов Оденсе (Дания), Нэшвила (США), Лондона, Рединга, Ноттингема и Оксфорда (все - Англия), Дрездена, йены, Фрайберга, Ростока и Ильменау (все - Германия).
Публикация. Основные результзаты диссертации опубликованы в [26-563. Большинство из результатов по раскраске включено в внигу Б.Тофта и Т.йенсена (Дания) "Задачи раскраски графов", выходящую в Wiley (США). За эти работы получены премии на конкурсах Института математики в 1967, 69 и 92 гг.
Структура и объем работы. Диссертация изложена на 239 страницах, состоит из введения, трех глав и списка литературы (110 наименований).