Хроматическое число планарного графа
Содержание
Раскраска в 6 цветов [ править ]
Докажем по индукции.
Если граф содержит не более [math]6[/math] вершин, то очевидно, что [math] \chi (G) \leqslant 6.[/math]
Предположим, что для планарного графа с [math]N[/math] вершинами существует раскраска в [math]6[/math] цветов. Докажем то же для графа с [math] N+1 [/math] вершиной.
Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин (ведь «занято» максимум [math]5[/math] цветов). Индукционный переход доказан.
Раскраска в 5 цветов [ править ]
Обозначим за [math] u [/math] — возвращаемую вершину, [math] v^ <(k)>[/math] — вершину, покрашенную в [math] k [/math] цвет.
Иначе, уложим полученный после удаления [math] u [/math] граф на плоскость, вернём вершину [math] u [/math] (пока бесцветную) и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.
Заметим, что не удаётся составить подобное доказательство для раскраски в четыре цвета, поскольку здесь наличие двух вершин одного цвета среди смежных [math] u [/math] не исключает того, что при их (смежных вершин) раскраске использовались все возможные цвета.
Раскраска в 4 цвета [ править ]
Теорема о четырёх красках была доказана в [math]1976[/math] году Кеннетом Аппелем и Вольфгангом Хакеном из Иллинойского университета. Это была первая крупная математическая теорема, доказанная с помощью компьютера. Первым шагом доказательства была демонстрация того, что существует определенный набор из [math]1936[/math] карт, ни одна из которых не может содержать карту меньшего размера, которая опровергала бы теорему. Аппель и Хакен использовали специальную компьютерную программу, чтобы доказать это свойство для каждой из [math]1936[/math] карт. Доказательство этого факта заняло сотни страниц. После этого Аппель и Хакен пришли к выводу, что не существует наименьшего контрпримера к теореме, потому что иначе он должен бы содержать, хотя не содержит, какую-нибудь из этих [math]1936[/math] карт. Это противоречие говорит о том, что вообще не существует контрпримера. Изначально доказательство не было принято всеми математиками, поскольку его невозможно было проверить вручную. В дальнейшем оно получило более широкое признание, хотя у некоторых долгое время оставались сомнения.
Чтобы развеять оставшиеся сомнения, в [math]1997[/math] году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, но по-прежнему проделанное с помощью компьютера. Кроме того, в [math]2005[/math] году доказательство было проделано Джорджсом Гонтиром с использованием специализированного программного обеспечения (Coq v7.3.1)
Эквивалентные формулировки [ править ]
В теории графов утверждение теоремы четырёх красок имеет следующие формулировки:
Ложное доказательство [ править ]
Карта(слева) окрашена пятью цветами, и нужно изменить как минимум [math]4[/math] из [math]10[/math] регионов, чтобы получить окраску в четыре цвета(справа)
Электронная библиотека
Раскраска вершин графа G = (V, E) называется правильной, если любые две смежные вершины окрашены в различные цвета. Минимальное число цветов, необходимое для правильной раскраски, называется хроматическим числом графа и обозначается c(G).
Простой граф G = (V,E) называется двудольным, если множество его вершин V можно разбить на два подмножества V1ÇV2 = Æ, V1ÈV2 = V, таких, что для каждого ребра его вершины принадлежат различным подмножествам.
На рис. 4.3 приведен пример двудольного графа. Верхние вершины составляют первое подмножество разбиения, а нижние – второе.
Рис. 4.3. Пример двудольного графа
Пусть G = (V,E) – простой граф. Напомним, что две вершины, принадлежащие одному ребру, называются смежными.
Элементарным путем длины n в графе G, соединяющим вершины p и q, называется последовательность вершин (v0, v1, …, vn ) таких, что
Элементарный цикл можно интерпретировать как непрерывный замкнутый путь в графе, не имеющий кратных вершин.
Следующие свойства графа G равносильны:
3) каждый элементарный цикл в графе G имеет четную длину.
Равносильность свойств 1 и 2 очевидна. Импликация (3) Þ (2) получается разбиением вершин на вершины, имеющие путь четной длины из фиксированной вершины, и имеющие путь нечетной длины. Импликация (2) Þ (3) очевидна.
Хроматической функцией fG (q) графа G = (V,E) называется число правильных раскрасок с помощью не более чем q красок.
Граф называется дискретным, если он не имеет ребер, т.е. состоит из одних вершин.
Вершина v Î V графа G = (V,E) называется висячей, если ее степень d(v) равна 1.
Простой граф, не имеющий элементарных циклов длиной больше нуля, называется деревом.
Для дерева T, имеющего число вершин n, хроматическая функция равна:
Используем метод индукции по n.
Удалим висячую вершину (которая существует в силу формулы Эйлера и соотношения |E| + 1 = |V|). Получим дерево, которое можно раскрасить q(q – 1) n-2 способами, согласно предположению индукции. Затем снова присоединим удаленную вершину. Для каждой из q(q – 1) n-2 раскрасок ее можно раскрасить (q – 1) способами. Отсюда получаем доказываемую формулу.
Рис. 4.4. Удаление ребра (б) и склеивание двух вершин (в)
Вычислим хроматическую функцию графа, состоящего из двух треугольников, имеющих общую сторону (рис. 4.4, а). С этой целью удалим ребро. Получим граф (рис. 4.4, б), который имеет q(q – 1)(q – 2)(q – 1) правильных раскрасок. Но не все раскраски являются правильными для исходного графа.
Число раскрасок, у которых концы удаленного ребра имеют одинаковый цвет, нужно вычесть. Число таких раскрасок равно значению хроматического многочлена графа (рис. 4.4, в). Отсюда:
Рассмотренный в примере 2 метод годится для вычисления fG(q) в общем случае.
Хроматическая функция fG (q) конечного графа G с n вершинами является многочленом степени не более чем n.
ложению индукции. Чтобы получить число раскрасок исходного графа G, нужно из этого числа вычесть число раскрасок, при которых концы удаленного ребра g окрашены в одинаковый цвет. Это число раскрасок будет хроматической функцией графа G’’, полученного удалением ребра g и отождествлением концов этого ребра. Отсюда разность
– это разность многочленов степени не более чем n.
Срочно?
Закажи у профессионала, через форму заявки
8 (800) 100-77-13 с 7.00 до 22.00
Хроматическое число плоскости не меньше 5
Задача о хроматическом числе плоскости формулируется следующим образом: в какое наименьшее число цветов можно раскрасить плоскость так, чтобы любые две точки на расстоянии 1 были покрашены в различные цвета?
Эту задачу сформулировали Хуго Хадвигер и Пал Эрдёш в сороковых годах XX века. Независимо от них примерно в то же самое время этой задачей занимались Эдуард Нелсон и Дж. Р. Исбелл. После работы Хадвигера 1961 года об открытых на тот момент проблемах, хроматическое число плоскости стало активно изучаться.
Сразу же было показано, что в 3 цвета плоскость требуемым образом раскрасить нельзя, однако 7 цветов достаточно. Действительно, легко выбрать на плоскости несколько точек так, что некоторые из них находятся на расстоянии ровно 1 (такая конструкция точек называется графом единичных расстояний), и затем перебором показать, что в 3 цвета эти точки раскрасить невозможно. Примеры таких графов — веретено Мозера и граф Голомба приведены на картинке ниже. Чтобы показать, что 7 цветов достаточно, замостим плоскость правильными шестиугольниками со стороной 0.4 и закрасим их по определённому паттерну, как на картинке ниже. Тогда, как несложно убедиться, концы любого отрезка длины 1 будут лежать в разных шестиугольниках различных цветов.
Однако, с тех пор никто не мог уточнить ни верхнюю, ни нижнюю границы. Задача получила название Проблема Нелсона — Эрдёша — Хадвигера. Прошло 60 лет, и вот, в апреле 2018 года математик-любитель Обри де Грей предъявил граф единичных расстояний, который нельзя покрасить в 4 цвета.
Геронтология и математика
Обри Дэвид Николас Джаспер ди Грей — британский геронтолог, исследует различные аспекты старения человека. Является разработчиком концепции SENS — «стратегии достижения пренебрежимого старения инженерными методами» (strategies for engineered negligible senescence). Председатель и директор по науке Фонда SENS, главный редактор академического журнала «Rejuvenation Research». Автор научно-популярной книги «Ending Aging», в которой в деталях рассматривается вопрос о полной победе над старением средствами медицины в течение ближайших нескольких десятилетий. (инфо из вики)
Как оказалось, этот почтенный бородатый дядька ещё и увлекается математикой в свободное время. 8 апреля 2018 года он выложил на arXiv статью, в которой описывает способ построения графа единичных расстояний, для покраски которого нужно как минимум 5 цветов.
Давайте разберёмся подробнее, что же это за граф такой.
Граф, который построил Джек
Всё начинается с простого графа H, состоящего из 7 вершин и 12 рёбер:
Давайте попробуем раскрасить его не более чем в 4 цвета всевозможными способами. Оказывается, различных способов это сделать (с точностью до поворотов, отражений и порядка цветов) всего 4:
Заметим, что в верхних двух вариантах у нас есть тройки одноцветных вершин, которые расположены в вершинах правильного треугольника, а в нижних двух — нет. Назовём раскраску графа H плохой, если там есть такая одноцветная тройка, иначе раскраска H — хорошая. Итого, у нас 2 плохие раскраски и 2 хорошие.
Хорошо, идём дальше. Рассмотрим граф J, склеенный из 13 графов H (найдите их все!):
Давайте попробуем покрасить граф J так, чтобы покраски всех входящих в него подграфов H были хорошие. Немного терпения, и мы получаем 6 различных вариантов (опять же с точностью до всяких эквивалентных преобразований, указанных выше; плюс цветов вершин, отмеченных чёрным):
Чёрные вершины могут быть покрашены несколькими способами, но их покраска нам не особо важна. Тем не менее, выкидывать их из графа J нежелательно — тогда появляются «лишние» варианты покраски. Которые, к тому же, портят все дальнейшие построения. Поэтому пусть чёрные вершины остаются.
Теперь давайте внимательно посмотрим на получившиеся варианты. А именно, на центральную вершину и на 6 вершин, удалённых от центральной на расстояние 2 (этаких граф H, увеличенный в два раза). Мы видим, что там всегда используется не более двух цветов. Более того, все варианты можно разбить на 3 случая:
Уже становится немного сложно, не правда ли?
Теперь давайте опять немного помедитируем на получившуюся конструкцию. А именно давайте поймём какие типы раскрасок у каждой копии графа J могли быть из тех трёх, что были перечислены выше. Типа a) раскраски там нет, так как какой бы тип ни был у второй копии, мы получим две вершины одного цвета на расстоянии 1. Типа b) там тоже нет: если у второй копии тоже тип b), то какие-то 2 вершины цвета центра «мешают» друг на другу; если у второй копии тип c), то хотя бы одна вершина на концах одноцветной диагонали будет соответствовать одной из четырёх вершин первой копии. Стало быть, у обеих копий графа J тип покраски c)! И такие покраски возможны, поскольку 4 вершины, которые покрашены в цвет, отличный от центрального, хотя и имеют один цвет, в каждой из копий этот цвет может быть разным.
Теперь, раз у двух копий графа J в графе K тип c), то пары противоположных вершин (из 6 нами рассматриваемых в каждой копии) имеют один и тот же цвет. Воспользуемся этим наблюдением и сделаем ещё один шаг. А именно, построим граф L из двух копий графа K:
Мы накладываем графы K друг на друга следующим образом: берём в каждом из них пару противоположных вершин и первые вершины в каждой паре совмещаем (на картинке выше это отмечено буквой A), а вторые размещаем на расстоянии ровно 1 (они отмечены буквами B и C). Этот приём называется оверетенением графа (от англ. spindling, где spindle — веретено). Например, веретено Мозера — это оверетенение графа-ромбика, составленного из двух треугольников. По наблюдению чуть выше, вершины A, B и C должны быть одного цвета, B и C на расстоянии 1, значит граф L покрасить нельзя.
Итак, что же, мы всё доказали? Да нет же, мы только доказали, что граф L нельзя покрасить в 4 цвета так, чтобы покраски всех копий графа H (а их уже насчитывается 52 штуки!) были хорошими. Значит, в любой покраске графа L покраска хотя бы одного графа H будет плохой!
Плохие покраски графа H
С этой частью, к сожалению, нельзя разобраться без помощи компьютера. Поэтому разберём кратко дальнейшую часть построений, за деталями можно обратиться к оригинальной статье, либо по ссылкам на Polymath чуть ниже. Картинки, взятые из оригинальной статьи, не очень высокого качества, но они позволяют примерно понять, что происходит.
Итак, сначала мы строим граф V на 31 вершину, который состоит из 5 графов H, которые совмещены центрами и повёрнуты на хитрые углы друг относительно друга:
Далее мы строим граф W следующим образом: делаем 31 копию графа V и помещаем центр каждой копии в каждую вершину ещё одного графа V (такая операция называется суммой Минковского двух графов единичных расстояний, т.е. мы делаем 
), после чего удаляем все вершины, которые удалены от центра на расстояние больше 
. Итого теперь у нас есть граф W на 301 вершину:
Теперь берём граф H и заменяем каждую его вершину на копию графа W (т.е. делаем 
). В итоге получаем граф M на 1345 вершин:
Полученный граф M в сущности является объединением большой кучи веретён Мозера в различных положениях. И, если мы покрасим в один цвет три вершины на попарном расстоянии изначального графа H, который мы распушивали до M, тем самым сделав покраску H плохой, то остальную часть графа M покрасить в 4 цвета не получится. Этот факт проверяется компьютерным перебором.
И, наконец, последний шаг: мы теперь берём вот эту жесть M на 1345 вершин и копируем поверх каждой из 52 копии графа H в графе L. В итоге получаем полную жесть на 20425 вершин, которая называется граф N. И этот граф нельзя покрасить в 4 цвета: при покраске каркаса L покраска хотя бы одного из подграфов H получится плохой, и для этого подграфа H соответствующую копию M докрасить до конца не получится.
Что и требовалось доказать.
Уменьшенный граф
Граф на 20425 вершин — довольно большой граф. Можно ли построить пример поменьше? Можно! Ещё в оригинальной статье де Грей различными отсечками уменьшил пример до 1581 вершины.
После публикации статьи, математическое сообщество организовало проект Polymath16 (как это было, например, с задачей про простые числа близнецы) для того, чтобы коллективными усилиями уменьшить граф, полученный де Греем, обобщить результат на большие размерности (для трехмерного пространства, четырехмерного, и так далее), а то и улучшить нижнюю границу хроматического числа для плоскости до 6.
Кстати, там же независимо проверили при помощи SAT-солверов, что пример де Грея на 1581 вершину действительно можно покрасить только в 5 цветов, а также то, что его граф является графом единичных расстояний. Так что сомнений в корректности полученного результата нет.
Граф де Грея потихоньку уменьшают. Например, граф L на 121 вершину и 52 копии графа H можно слегка уменьшить до графа L’ на 97 вершин и 40 копий графа H. Граф M с 1345 вершинами был уменьшен до графа M’ с всего 278 вершинами.
После замещения всех подграфов H на M’ а графе L’, результат можно улучшать и далее. На момент написания данной статьи наименьший найденный граф единичных расстояний, который нельзя покрасить в 4 цвета, имеет 610 вершин. Вот его картинка (кликабельно):
Работа продолжается. Может быть в скором времени удастся построить граф единичных расстояний, который нельзя покрасить в 5 цветов. А затем — в 6, и тогда задача о хроматическом числе плоскости будет решена полностью.
Хроматическое число
Хроматическое число графа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G).
Содержание
Определение
Хроматическое число графа — минимальное число 
, такое что множество 
вершин графа можно разбить на непересекающихся классов 
:
таких, что вершины в каждом классе независимы, то есть любое ребро графа не соединяет вершины одного и того же класса.
Связанные определения
Реберная раскраска
Хроматический класс графа G — минимальное число цветов, в которые можно раскрасить ребра графа G так, чтобы смежные ребра имели разные цвета. Обозначается χ'(G). Проблема реберной раскраски произвольного плоского кубического графа без мостов тремя цветами эквивалентна знаменитой Проблеме четырех красок. Реберная раскраска определяет 1-факторизацию графа.
Хроматический многочлен
Если рассмотреть количество различных раскрасок помеченного графа как функцию от доступного числа цветов t, то оказывается, что эта функция всегда будет полиномом от t. Этот факт был обнаружен Биркгофом и Льюисом [1] при попытке доказать гипотезу четырех красок.
Хроматические многочлены некоторых графов
Треугольник  |  |
Полный граф  |  |
Дерево с  вершинами |  |
Цикл  |  |
| Граф Петерсена |  |
Нахождение хроматического многочлена произвольного графа
Для графа-вершины хроматический многочлен равен 
Хроматический многочлен графа равен произведению хроматических многочленов его компонент
Также существует рекуррентное соотношение
где 
и 
— смежные вершины, 
— граф, получающийся из графа 
путем удаления ребра 
а 
— граф, получающийся из графа путем стягивания ребра 
в точку.
Можно использовать эквивалентную формулу
где и — несмежные вершины, а 
— граф, получающийся из графа путем добавления ребра 
Свойства хроматического многочлена
Для всех целых положительных
Хроматическое число 
— наименьшее целое положительное , для которого
0.» border=»0″/>
Обобщения
Значение для теории графов
Множество глубоких задач теории графов легко формулируются в терминах раскраски. Самая знаменитая из таких задач, проблема четырёх красок, в настоящее время решена, однако появляются новые, например, обобщение проблемы четырёх красок, гипотеза Хадвигера.
См. также
Примечания
Литература
Полезное
Смотреть что такое «Хроматическое число» в других словарях:
Хроматическое число — [chromatic number] число, характеризующее количество несмежных вершин графа. Если пометить все вершины графа р цветами (отсюда и термин“хроматическое”) и при этом никакие две смежные вершины не будут окрашены одинаково, то такой граф называется… … Экономико-математический словарь
хроматическое число — Число, характеризующее количество несмежных вершин графа. Если пометить все вершины графа р цветами (отсюда и термин“хроматическое”) и при этом никакие две смежные вершины не будут окрашены одинаково, то такой граф называется хроматическим… … Справочник технического переводчика
Раскраска графа — 3 раскраска графа Петерсена Хроматическое число графа G минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G). Содержание 1 Определение … Википедия
Раскрашиваемый граф — 3 раскраска графа Петерсена Хроматическое число графа G минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G). Содержание 1 Определение … Википедия
Хроматический граф — 3 раскраска графа Петерсена Хроматическое число графа G минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G). Содержание 1 Определение … Википедия
Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия
Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия
Инвариант графа — в теории графов некоторое обычно числовое значение или упорядоченный набор значений (хэш функция), характеризующее структуру графа и не зависящее от способа обозначения вершин или графического изображения графа. Играет важную роль при… … Википедия
Нерешённые проблемы математики — Нерешённые проблемы (или Открытые проблемы) проблемы, которые рассматривались математиками, но до сих пор не решены. Часто принимают форму гипотез, которые предположительно верны, но нуждаются в доказательстве. В научном мире популярна практика… … Википедия
Открытые математические проблемы — Открытые (нерешённые) математические проблемы проблемы, которые рассматривались математиками, но до сих пор не решены. Часто имеют форму гипотез, которые предположительно верны, но нуждаются в доказательстве. В научном мире популярна… … Википедия
