Что такое хроматическое число графа

Хроматическое число планарного графа

Содержание

Раскраска в 6 цветов [ править ]

Докажем по индукции.

Если граф содержит не более [math]6[/math] вершин, то очевидно, что [math] \chi (G) \leqslant 6.[/math]

Предположим, что для планарного графа с [math]N[/math] вершинами существует раскраска в [math]6[/math] цветов. Докажем то же для графа с [math] N+1 [/math] вершиной.

Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин (ведь «занято» максимум [math]5[/math] цветов). Индукционный переход доказан.[math]\triangleleft[/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 можно разбить на два подмножества V₁ÇV₂ = Æ, V₁ÈV₂ = V, таких, что для каждого ребра его вершины принадлежат различным подмножествам.

На рис. 4.3 приведен пример двудольного графа. Верхние вершины составляют первое подмножество разбиения, а нижние – второе.

Рис. 4.3. Пример двудольного графа

Пусть G = (V,E) – простой граф. Напомним, что две вершины, принадлежащие одному ребру, называются смежными.

Элементарным путем длины n в графе G, соединяющим вершины p и q, называется последовательность вершин (v₀, v₁, …, v_n ) таких, что

Элементарный цикл можно интерпретировать как непрерывный замкнутый путь в графе, не имеющий кратных вершин.

Следующие свойства графа G равносильны:

3) каждый элементарный цикл в графе G имеет четную длину.

Равносильность свойств 1 и 2 очевидна. Импликация (3) Þ (2) получается разбиением вершин на вершины, имеющие путь четной длины из фиксированной вершины, и имеющие путь нечетной длины. Импликация (2) Þ (3) очевидна.

Хроматической функцией f_G (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 метод годится для вычисления f_G(q) в общем случае.

Хроматическая функция f_G (q) конечного графа G с n вершинами является многочленом степени не более чем n.

ложению индукции. Чтобы получить число раскрасок исходного графа G, нужно из этого числа вычесть число раскрасок, при которых концы удаленного ребра g окрашены в одинаковый цвет. Это число раскрасок будет хроматической функцией графа G’’, полученного удалением ребра g и отождествлением концов этого ребра. Отсюда разность

– это разность многочленов степени не более чем n.

Срочно?
Закажи у профессионала, через форму заявки
8 (800) 100-77-13 с 7.00 до 22.00

Источник

Хроматическое число

Хроматическое число графа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G).

Содержание

Определение

Хроматическое число графа — минимальное число , такое что множество вершин графа можно разбить на непересекающихся классов :

таких, что вершины в каждом классе независимы, то есть любое ребро графа не соединяет вершины одного и того же класса.

Связанные определения

Реберная раскраска

Хроматический класс графа G — минимальное число цветов, в которые можно раскрасить ребра графа G так, чтобы смежные ребра имели разные цвета. Обозначается χ'(G). Проблема реберной раскраски произвольного плоского кубического графа без мостов тремя цветами эквивалентна знаменитой Проблеме четырех красок. Реберная раскраска определяет 1-факторизацию графа.

Хроматический многочлен

Если рассмотреть количество различных раскрасок помеченного графа как функцию от доступного числа цветов t, то оказывается, что эта функция всегда будет полиномом от t. Этот факт был обнаружен Биркгофом и Льюисом [1] при попытке доказать гипотезу четырех красок.

Хроматические многочлены некоторых графов

Треугольник
Полный граф
Дерево с вершинами
Цикл
Граф Петерсена

Нахождение хроматического многочлена произвольного графа

Для графа-вершины хроматический многочлен равен

Хроматический многочлен графа равен произведению хроматических многочленов его компонент

Также существует рекуррентное соотношение

где и — смежные вершины, — граф, получающийся из графа путем удаления ребра а — граф, получающийся из графа путем стягивания ребра в точку.
Можно использовать эквивалентную формулу

где и — несмежные вершины, а — граф, получающийся из графа путем добавления ребра

Свойства хроматического многочлена

Для всех целых положительных

Хроматическое число — наименьшее целое положительное , для которого

0.» border=»0″ />

Обобщения

Значение для теории графов

Множество глубоких задач теории графов легко формулируются в терминах раскраски. Самая знаменитая из таких задач, проблема четырёх красок, в настоящее время решена, однако появляются новые, например, обобщение проблемы четырёх красок, гипотеза Хадвигера.

См. также

Примечания

Литература

Полезное

Смотреть что такое «Хроматическое число» в других словарях:

Хроматическое число — [chro­matic number] число, характеризующее количество несмежных вершин графа. Если пометить все вершины графа р цветами (отсюда и термин“хроматическое”) и при этом никакие две смежные вершины не будут окрашены одинаково, то такой граф называется… … Экономико-математический словарь

хроматическое число — Число, характеризующее количество несмежных вершин графа. Если пометить все вершины графа р цветами (отсюда и термин“хроматическое”) и при этом никакие две смежные вершины не будут окрашены одинаково, то такой граф называется хроматическим… … Справочник технического переводчика

Раскраска графа — 3 раскраска графа Петерсена Хроматическое число графа G минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G). Содержание 1 Определение … Википедия

Раскрашиваемый граф — 3 раскраска графа Петерсена Хроматическое число графа G минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G). Содержание 1 Определение … Википедия

Хроматический граф — 3 раскраска графа Петерсена Хроматическое число графа G минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G). Содержание 1 Определение … Википедия

Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия

Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия

Инвариант графа — в теории графов некоторое обычно числовое значение или упорядоченный набор значений (хэш функция), характеризующее структуру графа и не зависящее от способа обозначения вершин или графического изображения графа. Играет важную роль при… … Википедия

Нерешённые проблемы математики — Нерешённые проблемы (или Открытые проблемы) проблемы, которые рассматривались математиками, но до сих пор не решены. Часто принимают форму гипотез, которые предположительно верны, но нуждаются в доказательстве. В научном мире популярна практика… … Википедия

Открытые математические проблемы — Открытые (нерешённые) математические проблемы проблемы, которые рассматривались математиками, но до сих пор не решены. Часто имеют форму гипотез, которые предположительно верны, но нуждаются в доказательстве. В научном мире популярна… … Википедия

Источник

В поисках хроматического числа

Российский математик опроверг гипотезу Стефана Хидетниеми

Несколько дней назад сообщество математиков — специалистов в теории графов было взволновано сообщением о том, что выдвинутая Стефеном Хидетниеми (Stephen T. Hedetniemi) в 1966 году гипотеза оказалась неверной. Оказывается, хроматическое число тензорного произведения двух графов может быть меньше минимума хроматических чисел сомножителей, а не всегда равно этому минимуму, как когда-то предположил Хидетниеми. Как построить контрпример к этой гипотезе, придумал молодой московский математик Ярослав Шитов. Подробнее об этом по просьбе N + 1 рассказал математик Владимир Потапов.

Хроматическое число графов

Расскажем подробнее о том, что такое хроматическое число графа, тензорное произведение графов и почему более 50 лет эта гипотеза казалась верной большинству специалистов.

Начнем с того, что графом в математике называется набор точек (вершин графа), соединенных отрезками (ребрами графа). Раскраска вершин графа в разные цвета называется правильной, если вершины, соединенные ребром (смежные вершины), раскрашены в разные цвета.

Хроматическим числом графа называется минимальное число цветов, которыми можно правильно раскрасить вершины графа. Нетрудно видеть, что изображенный выше граф Петерсена нельзя правильно раскрасить в два цвета, поскольку в нем есть циклы нечетной длины. Следовательно, его хроматическое число равно 3.

Задача нахождения хроматического числа графа стала популярной благодаря широко известному вопросу: «Можно ли вершины плоского (то есть размещенного на плоскости без пересечений ребер) графа правильно раскрасить в 4 цвета?»

Гипотеза «четырех красок», которая состоит в положительном ответе на этот вопрос, возникла еще в XIX веке и была доказана Кеннетом Аппелем и Вольфгангом Хакеном только в 1977 году. Причем в доказательстве авторам пришлось прибегнуть к компьютеру, чтобы правильно раскрасить сотни графов, раскраска которых уже не сводилась к раскраске более простых графов. Кстати, граф Петерсена плоским не является и может быть нарисован на плоскости только с пересечениями ребер.

Может показаться, что игры в раскрашивание графов не могут иметь никакого полезного применения. Даже практический вопрос: сколько необходимо цветов, чтобы любые соседние страны на карте были разного цвета? — из которого возникла гипотеза о «четырех красках», кажется скорее праздным, чем полезным. Однако по мере роста сложности инфраструктуры и оборудования оказалось, что имеется множество вполне серьезных задач, которые сводятся к нахождению хроматического числа графа.

Например, недалеко расположенные станции сотовой связи должны работать на разных радиочастотах, чтобы не мешать друг другу. Если станции связи считать вершинами графа и соединить ребрами те пары станций, которые могут мешать работе друг друга, то хроматическое число графа будет равно минимально необходимому набору различных радиочастот для безотказной работы сотовой связи.

Если же рассмотреть социальную сеть Facebook как граф с вершинами — пользователями, каждая из которых смежна с «друзьями», то становится ясно, что изучение различных характеристик графов важно для понимания закономерностей распространения информации (новостей, моды, инноваций) в современном мире.

Произведения графов

Прежде чем перейти к обсуждению гипотезы Хидетниеми, поговорим о понятии декартова произведения графов. Пусть имеются два графа G и H с множествами вершин 1…u_n> и 1…v_m> соответственно. Тогда их декартовым произведением называется граф, вершины которого являются всевозможными парами (u_i,v_k). Причем вершины (g,h) и (b,d) соединены ребром, только если g=b и вершина h смежна с вершиной d в графе H или, наоборот, h=d и вершина g смежна с вершиной b в графе G.

Декартово произведение графов

Легко понять, что хроматическое число декартова произведения графов не меньше, чем хроматическое число любого из сомножителей. Если мы зафиксируем любую вершину h графа H и рассмотрим в декартовом произведении вершины вида (u,h), а также ребра между ними, то получится такой же подграф, как граф G. Значит, для правильной раскраски этого подграфа нужно столько же цветов, сколько для правильной раскраски графа G, а для правильной раскраски всего декартова произведения цветов нужно точно не меньше. То же самое можно сказать и про граф H.

Более 50 лет назад математик Герт Сабидусси доказал, что хроматическое число декартова произведения графов равно максимуму хроматических чисел сомножителей.

Теперь перейдем к тензорному произведению графов, о котором говорится в гипотезе Хидетниеми. Тензорным произведением графов G и H называется граф с теми же вершинами, что и у декартова произведения графов G и H, которые, однако, по-другому соединены ребрами. А именно, вершины (g,h) и (b,d) в тензорном произведении соединены ребром, только если вершина g смежна с вершиной b в графе G и вершина h смежна с вершиной d в графе H.

Тензорное произведение графов

Если в исходных графах G и H ребер больше, чем вершин, то в их тензорном произведении больше ребер, чем в декартовом произведении. Казалось бы, чем больше ребер в графе, тем больше цветов нужно для его правильной раскраски. Однако нетрудно видеть, что для правильной раскраски тензорного произведения графов G и H достаточно использовать правильную раскраску любого из них.

Действительно, если покрасить каждую вершину (u,v) тензорного произведения в тот цвет, в который была покрашена вершина u графа G, то любая смежная с ней вершина (g,h) окажется покрашена в другой цвет, поскольку вершины u и g были смежны в графе G и его раскраска была правильной. Значит, цвета вершин (u,v) и (g,h), так же как вершин u и g, различны. Поэтому хроматическое число тензорного произведения не превосходит минимума хроматических чисел сомножителей.

Правильная раскраска тензорного произведения графов

Сильным произведением двух графов G₁ и G₂ называется граф с тем же множеством вершин, как у декартова и тензорного произведения этих графов. Ребрами сильного произведения графов являются одновременно ребра декартова и тензорного произведений.

Гипотеза Хидетниеми и ее опровержение

Естественно предположить, что хроматическое число тензорного произведения будет в точности равно минимуму хроматических чисел сомножителей. Ведь каждая вершина тензорного произведения графов имеет гораздо больше соседей, чем было у вершин исходных графов! Тем более что в похожем случае декартова произведения имеется равенство.

Это естественное предположение и сделал Хидетниеми. И оно подтверждалось практически для различных частных случаев, Например, граф на иллюстрации выше имеет циклы нечетной длины, а значит, его хроматическое число не меньше трех. И даже теоретически для некоторых классов графов было доказано, что гипотеза Хидетниеми верна, например для тензорного произведения любых двух графов с хроматическими числами не более 4.

Круг графов, для которых удалось проверить правильность гипотезы Хидетниеми постепенно расширялся и казалось, что вот-вот гипотеза будет доказана полностью.

Однако Ярославу Шитову неожиданно удалось доказать обратное. Причем не посредством построенного с помощью компьютера контрпримера, а полностью теоретически.

Для того чтобы кратко описать его доказательство, нам понадобится несколько определений. Во-первых, для произвольного графа H определим экспоненциальный граф E_s(H). Вершинами графа E_s(H) будут функции, действующие из множества вершин графа H в множество чисел <1, …, s>. Две функции f и g будем считать смежными, если они принимают различные значения на любых вершинах, смежных в графе H.

Нетрудно убедиться, что тензорное произведение графов H и E_s(H) можно правильно раскрасить в s цветов, независимо от хроматического числа графа H. Определим раскраску вершины (u,f) тензорного произведения равной f(u). Рассмотрим пару вершин (u,f) и (v,g) смежных в тензорном произведении графов. Тогда вершины u и v смежны в H, а вершины f и g смежны в E_s(H). Значит, по определению экспоненциального графа числа f(u) и g(v) не совпадают, то есть так определенная раскраска тензорного произведения в s цветов является правильной.

Теперь нужно найти подходящий граф H, чтобы хроматические числа графа H и его экспоненциального графа E_s (H) были строго больше s.

Классическая теорема Пала Эрдеша утверждает, что найдутся графы со сколь угодно большим хроматическим числом и сколь угодно большим обхватом (минимальным циклом).

Рассмотрим граф G с обхватом 10 и хроматическим числом 5. Полным графом K_q, или q-кликой, называется граф на q вершинах, все вершины которого попарно соединены ребрами.

Определим граф H как сильное произведение графов G и K_q. Граф H получается подстановкой q-клик во все вершины графа G, причем все вершины смежных q-клик попарно соединены ребрами. Отсюда нетрудно доказать, что хроматическое число сильного произведения графа G на q-клику будет иметь хроматическое число не меньше чем 5q.

Ярославу Шитову удалось доказать, что для достаточно больших q и s > 4,1q экспоненциальный граф E_s(H) имеет хроматическое число строго большее, чем s. Теперь достаточно выбрать такое s, что 5q > s > 4,1q и мы получаем, что оба сомножителя H и E_s(H) в тензорном произведении имеют хроматические числа больше, чем s, а их тензорное произведение имеет хроматическое число равное s, как было доказано выше. Таким образом, гипотеза Хидетниеми опровергнута.

Слово автору опровержения

Я не уверен, что у специалистов было единое мнение о том, верна ли гипотеза Хидетниеми: некоторые исследователи считали ее верной, но были и те, кто считал иначе. В пользу истинности гипотезы говорили случаи графов с хроматическим числом не больше четырех (подробнее); графов с большими кликами (подробнее здесь, здесь и здесь), графов и гиперграфов Кнезера (подробнее), а также аналог гипотезы Хидетниеми для дробных раскрасок. Тем не менее, аналогичное утверждение оказывается неверным для бесконечных графов: контрпример был найден еще в 1985 году.

Как и многие математические задачи и результаты, гипотеза Хидетниеми появилась и активно изучалась, как мне кажется, из чистого любопытства. Говорить о том, что из нее следовали какие-то важные выводы за пределами «чистой математики», которые теперь придется пересматривать, я бы не стал.

На языке гомоморфизмов гипотеза Хидетниеми звучит так: все полные графы являются мультипликативными (граф K называется мультипликативным, если существование гомоморфизма из тензорного произведения графов G и H в граф K влечет наличие гомоморфизма из G в K или гомоморфизма из H в K). Понятие мультипликативности активно обсуждается и для других графов, но ситуация с достаточно большими кликами стала ясна лишь теперь. Были еще и топологические следствия из гипотезы Хидетниеми, но, так как гипотеза не подтвердилась, они остаются открытыми проблемами.

Источник