Без использования теоремы о четырех красках доказать, что любой планарный связный граф, построенный на не более чем $%n=11$% вершинах, является $%4$%-раскрашиваемым. Указание: вначале доказать, что в таком графе существует вершина, степень которой меньше или равна четырем.

задан 29 Мар '16 19:35

10|600 символов нужно символов осталось
1

Прежде всего, надо заметить, что в графе не должно быть петель и кратных рёбер, то есть это подразумевается в условии. Далее, граф можно считать связным, рассуждая относительно каждой его связной компоненты. В силу планарности, граф можно уложить без самопересечений на сфере, и для этой укладки будет выполнена формула Эйлера: В-Р+Г=2.

Если предположить, что степень каждой вершины не меньше 5, то отсюда следует неравенство 5В<=2Р (поскольку удвоенное число рёбер равно сумме степеней вершин). Далее, каждая грань содержит не менее трёх рёбер, откуда следует неравенство 3Г<=2Р (с учётом того, что ребро находится на границе двух граней). Таким образом, 2=В-Р+Г<=В-Р/3<=В-5В/6=В/6, и оказывается, что В>=12, вопреки условию.

Теперь, с учётом доказанного утверждения, 4-раскрашиваемость доказывается индукцией по числу вершин (примерно так же, как в известной теореме Хивуда). Берём произвольную вершину степени <=4, удаляя её из графа вместе с инцидентными рёбрами. То, что осталось, раскрашиваем в 4 цвета. Если степень удалённой вершины меньше 4, или если она равна 4, но среди её соседей какой-то цвет отсутствует, то для этой вершины найдётся подходящий цвет. Осталось рассмотреть случай, когда соседей 4, и все их цвета -- разные.

Рассмотрим картинку на плоскости: вершина v (пока не раскрашенная) имеет соседей v1, v2, v3, v4, и соединена с ними рёбрами e1, e2, e3, e4, идущими по часовой стрелке. Цвета этих вершин равны 1, 2, 3, 4 соответственно. Рассмотрим подграф раскрашенного графа, состоящий из вершин цветов 1 и 3, а также соединяющих их рёбер. Если вершины v1, v3 лежат в разных связных компонентах этого графа, то перекрасим цвета вершин компоненты, которой принадлежит v1, меняя местами цвета 1 и 3. Тогда v1 будет иметь цвет 3, и v раскрасим в цвет 1. Если же обе эти вершины лежат в одной компоненте, то они соединены путём p, в котором цвета 1 и 3 чередуются.

Теперь то же самое сделаем для вершин v2 и v4. Там тоже или возможна раскраска, или v2 соединена с v4 путём q, в котором цвета 2 и 4 чередуются. Из топологических соображений понятно, что такое невозможно. Действительно, путь p вместе с рёбрами e1, e3 образует цикл, разделяющий вершины v2, v4. Поэтому q пересечёт этот цикл в какой-то вершине, что невозможно, так как в цикле никакие вершины не имеют ни цвета 2, ни цвета 4.

ссылка

отвечен 29 Мар '16 20:32

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,274
×482
×262
×156
×10

задан
29 Мар '16 19:35

показан
764 раза

обновлен
29 Мар '16 20:32

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru