В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 47

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 47)

Крол, 1973 г.). Плоский граф 3-раскрашиваем тогда и только тогда, когда он является подграфом плоской триангуляции с четными степенями вершин. 0 Н е о б х о д и м о с т ь. Будем считать, что порядок рассматриваемого графа более трех (для Кг утверждение тривиально). Пусть вершины плоского графа 6 правильно раскрашены тремн цветами 1, 2, 3. Рассмотрим произвольную отличную от треугольника грань Г этого графа. Возможны следующие случаи.

1) Границей грани Г является цккл четной длины, вершины которого окрашены в два цвета, например, и 2. Тогда поместим внутри Г вершину ш, соединив ее ребрами с каждой нз вершин этого цикла, и окрасим эту вершину в третий цвет 3 (рис. 58.1, а). 2) Границей грани Г является 4-цикл С =(оп ог, ог, о4, о~), вершины которого окрашены в три цвета, например, о1 — в цвет 1, ог — в 2, ог — в 3, о4 — в 2. В этом случае поместим внутри грани Г цепь! =(оь шп шг, ог), связывающую несмежные вершины цикла С, имеющие различные цвета. Соединим ш1 и шг с вершинами этого цикла, окрашенными в один цвет.

Для получения правильной раскраски остается каждой из вершин ш~ и игг приписать цвет 1 илп 3, однозначно определенный (см. рнс. 58Л, б). 17 в. л вмеввчев и др. 257 3) Границей грани Г является 1-иклл, 1>4, вершины которого окрашены в три цвета. Поместим в Г вершину пг, припишем ей цвет 3 и соединим ее со всеми вершинами цикла, имеющими цвета 1 и 2.

Грань Г прн этом разобьется на несколько граней, границами которых и, иг т г 7 8 и, иг Рвс. 58Л будут треугольники и 4-циклы (рис. 58.1, в). С последними поступим так же, как в предыдущих случаях. Проделав описанные построения для выбранной грани Г, отличной от треугольника, получим новый правильно 3-раскрашенный граф, в котором Г улье разбита на треугольники. Выполнив эти операции для всех таких граней, придем к правильно 3-раскрашенной плоской триангуляции, подграфом которой и будет исходный граф.

Покажем, что степени всех вершин этой триангуляции четны. Пусть и — произвольная вершина, имеющая, для определенности, цвет 1. Поскольку СФКз, то вершины, смежные с и, образуют цикл. Так как для их раскраски достаточно двух цветов 2 и 3, то этот цикл имеет четную длину и, следовательно, степень вершины и четная.

Достаточность. Пусть граф 6 является подграфом плоской триангуляции Т с четными степенями вершин. Покажем, что он З-раскрашиваем. Поскольку Т вЂ” эйлеров граф, то согласно утверждению 58.3 его грани можно раскрасить двумя цветами, например, красным и синим. Ориевтируем ребра, ограничивающие каждую красную грань, так, чтобы при движении по ориентированному ребру грань оставалась справа.

Произвольную вершину и графа Т окрасим в цвет 1 и для каждой вершины пг рассмотрим любую простую (и, и)-цепь Р. Пусть а(Р) и р(Р) — числа ребер этой цепи, ориентация которых совпадает и, соответственно, не совпадает с направлением цепи от и к иг. Првппшем вершине ги цвет с(лг) = 1 + а (Р) — р (Р) (шог) 3) . Покажем, что выполненная таким образом раскраска окажется правильной. Сперва докажем, что окраска любой вершины ш не зависит от выбора цепи Р. Рассмотрим произвольный простой цикл С в графе Т, ограничивающий некоторую область Р. Если при движении по ориентированному ребру, принадлежащему С, от вго начала к концу область нас к ходится справа от ребра, то к с назовем это ребро а-реброгг, с с в противном случае — Ь-реб- к ром.

Пусть а и р — числа а-ребер и, соответственно, 6 Ь-ребер в С, а й и г — числа Ряс. 88.2 красных и синих внутренних граней в области Г. Каждое а-ребро принадлежит красной внутренней грани, а Ь-ребро — синей внутренней грани. Вычислим число р ребер, находящихся внутри цикла. С одной стороны, они принадлежат красным граням, поэтому р =Зй — а. С другой стороны, эти ребра принадлежат синим граням, так что р = Зг — р.

Отсюда Зй — а = = Зг — р, нли а — р = Зй — Зг — = О (пюй 3). Пусть Р, и Рг — две различные простые (э, ш)-цепи. Покажем, что с~ (ш) = сг(ш), где с (ш) = 1+ а(Р~) — р(Р,) (шос(3), 1= 1, 2. Вначале рассмотрим случай, когда цепи Р~ и Рг не имеют общих вершин, отличных от г и ш (см. рис. 53.2, на котором красные грани обозначены буквой К, а синие — С).

Пусть С вЂ” цикл, полученный объединением цепей Р1 и Р,. Для определенности считаем, что ориентация а-ребер совпадает с направлением цепи Рь Тогда С содерлгит и(Р~)+ р(Рг) а-ребер и а(Рг)+(1(Р~) Ь-ребер. По доказанному выше (а(Р~)+ (~(Рг) ) — (а(Рг)+ р (Р1) ) = О (пюс( 3), и(Р1) р(Р1) — и(рг) э(рг) (шос(3) откуда вытекает, что с1(ш) = сг(ш). Если цепи Р~ и Рг имеют общие вершины, отличные от г и ш, то объединение этих цепей разбиваем на простые циклы и цепи, а далее проводим доказательство так, как для случая одного цикла.

17г 259 Таким образом доказано, что после выбора цвета вершины о остальные вершины графа Т однозначно раскрашиваются тремя цветами. Покажем, что эта раскраска является правильной. Рассмотрим любые две смежные вершины и и ш графа Т, отличные от вершины о. Из простых (о, и)- и (о, и~)-цепей выберем кратчайшую. Пусть ею окажется (о, ш)-цепь Р. Рассмотрим также (о, и)-цепь, полученную при присоединении к цепи Р ребра ши. Тогда с(ш) = 1+ и(Р) — р(Р) (шой 3), с (и) = 1+ и(Р) — ~ (Р) ~ 1 (шой 3) (знак последнего слагаемого зависит от ориентации ребра ши). В случае, когда о = и>, последнее соотношение принимает вид с (и) = 1 ~ 1.

Отсюда следует, что с(ш)Фс(и), и раскраска графа Т является правильной. Поскольку 6 — подграф 3-раскрашиваемого графа Т, то оп также 3-раскрашиваем. 3 Утверждение 58.2 и теорема 58.4 дают необходимые и достаточные условия существования правильной раскраски вершин плоского графа двумя и тремя цветами. Однако между этими утверждениями есть принципиальная разница: условие утверждения 58.2 легко проверяемо, но не известно эффективных способов проверки условий теоремы 58.4. Приведем без доказательства одно легко проверяемое достаточное условие 3-раскрашиваемости плоского графа. Т е о р е м а 58.5. Л~обой плоский граф, содержащий менее четырех З-циклов, З-раскрашиваем. э 59. Проблема четырех красок Гипотеза четырех красок привлекала внимание многих исследователей.

Уже в 1880 году появилось первое доказательство А. 11емпе. Опшбка в этом доказательстве была обнаружена Р. Хивудом в 1890 году. Одновременно он показал, что если в формулировке гипотезы слово «четыре» заменить на «пять», то она легко доказывается. Теорема 59.1 (Р. Хивуд, 1890 г.). Кажда»й планарный граф 5-раскрашиваем. ~> По-прежнему, не теряя общности, будем рассматривать плоские графы. Проведем доказательство индукцией по числу вершин графа. Теорема справедлива для гра- фов с не более чем пятью веРшинами.

Предположим, что она верна для графов порядка, не превосходящего и, и ~ 5. Рассмотрим произвольный плоский граф С порядка и+1. Согласно утвернвденпю 38.5 этот граф содержит вершину оо, степень которой но превосходит пяти. Пусть % = У(ос) — окружение вершины оа в графе 6. Отдельно рассмотрим два случая. 1) |Х~ ( 4. По индуктивному предположению граф С вЂ” ос 5-раскрашиваем; раскрасим его вершины пятью ~4, из у Рис. 598 цветами. Затем окрасим вершину оо в тот из пяти цветов, который пе использован при раскраске вершин из Х 2) ~М~ =5. В множестве У существуют две несмежные вервпипы о1 и ог, иначе 6(Х)= Кг и граф 6 не планареп. Граф С, полученньш из 6 — оо слиянием этих вориши в вершину о (см.

рис. 59.1), является плоским и по индуктивному предположению 5-раскрашиваемым. Фиксируем какую-либо пз его правильных 5-раскрасок. В графе С окрасим вершины о1 и ог в цвет вершины о, а остальные отличные от о вершины — з те же цвета, что и соответствующие вершины графа С. Затем припишем вершине ос цвет, не использованный при раскраске вершин из )т'. Таким образом, получена правильная 5-раскраска графа 6. 0 Трудность проблемы четырех красок привела к появлению большого числа равпосильных ей формулировок. Изучая эквивалентные задачи, исследователи пытались доказать гипотезу четырех красок. Теорема 59.2.

Следуюи1ие три утверждения эквивалентны: 1) произвольный плоский граф 4-раскрашиваелц 2) любая кубическая карта 4-раскрашиваема; 3) хроматический индекс произвольной кубической карты равен 3. » Вначале докажем истинность импликации 2)= 1). Согласно теореме 58А достаточно показать, что 4-раскраска произвольной карты определяется 4-раскраской некоторой кубической карты. Пусть 6 — произвольная карта, и — ее вершина степепи 2. Замена ребер ио и и»о, инцидентных вершине и, ребром он» приводит к новой карте 6. Легко видеть, что правильная раскраска одной карты очевидным образом переносится на вторую.

Характеристики

Список файлов лекций