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

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

Содержание

1 Определение
2 Связанные определения
3 Реберная раскраска
4 Хроматический многочлен
5 Обобщения
6 Значение для теории графов
7 См. также
8 Примечания
9 Литература

Определение

Хроматическое число графа — минимальное число <math>k</math>, такое что множество <math>V</math> вершин графа можно разбить на <math>k</math> непересекающихся классов <math>C_1, C_2, \ldots, C_k</math>:

<math>V=\bigcup_i^{} C_i;\ C_i\cap C_j=\varnothing,</math>

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

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

K-раскрашиваемый граф — граф, хроматическое число которого не превосходит <math>K</math>. То есть его вершины можно раскрасить <math>K</math> разными цветами так, что у любого ребра концы будут разного цвета.
K-хроматический граф — граф, хроматическое число которого равно <math>K</math>. То есть вершины графа можно раскрасить <math>K</math> цветами так, что у любого ребра концы будут разного цвета, но так раскрасить <math>K - 1</math> цветами — уже нельзя.

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

Основная статья: Рёберная раскраска

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

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

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

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

Треугольник <math>K_3</math>	<math>t(t-1)(t-2)</math>
Полный граф <math>K_n</math>	<math>t(t-1)(t-2) ... (t-(n-1))</math>
Дерево с <math>n</math> вершинами	<math>t(t-1)^{n-1}</math>
Цикл <math>C_n</math>	<math>(t-1)^n+(-1)^n(t-1)</math>
Граф Петерсена	<math>t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)</math>

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

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

<math>|V(G)| = 1 \Rightarrow P(G,t)=t.</math>

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

<math>G_1 \cap G_2 = \emptyset \Rightarrow P((G_1 \cup G_2),t) = P(G_1,t)P(G_2,t).</math>

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

где <math>u</math> и <math>v</math> — смежные вершины, <math>G-(u,v)</math> — граф, получающийся из графа <math>G</math> путём удаления ребра <math>(u,v),</math> а <math>G/(u,v)</math> — граф, получающийся из графа <math>G</math> путём стягивания ребра <math>(u,v)</math> в точку.
Можно использовать эквивалентную формулу

<math>P(G,t)=P(G+(u,v), t) + P(G \Uparrow (u,v),t),</math>

где <math>u</math> и <math>v</math> — несмежные вершины, а <math>G+(u,v)</math> — граф, получающийся из графа <math>G</math> путём добавления ребра <math>(u,v).</math>

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

Для всех целых положительных <math>t</math>

Хроматическое число <math>\chi(G)</math> — наименьшее целое положительное <math>t</math>, для которого

Степень хроматического многочлена равна количеству вершин:

Обобщения

Также хроматическое число можно рассматривать для других объектов, например, для метрических пространств. Так, хроматическим числом плоскости называется минимальное число цветов χ, для которого существует такая раскраска всех точек плоскости в один из цветов, что никакие две точки одного цвета не находятся на расстоянии ровно 1 друг от друга. Аналогично для любой размерности пространства. Элементарно доказывается, что для плоскости <math>4\leqslant \chi\leqslant 7</math>, однако продвинуться дальше до сих пор не удаётся. Эта задача называется проблемой Нелсона — Эрдёша — Хадвигера.

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

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

См. также

Напишите отзыв о статье "Хроматическое число"

Примечания

↑ [slovar-vocab.com/russian-english/dictionary/raskraska-2536841.html Раскраска]
↑ Birkhoff, G. D. and Lewis, D. C. «Chromatic Polynomials.» Trans. Amer. Math. Soc. 60, 355—451, 1946.

Литература

О. Оре. Теория графов. Перевод с английского И. Н. Врублевской, под редакцией Н. Н. Воробьева. М.: Наука, 1986.

Отрывок, характеризующий Хроматическое число

– Ах, пожалуйста… Можно мне при вас остаться? – вскрикнул Петя.
– Да как тебе именно велено от генег'ала – сейчас вег'нуться? – спросил Денисов. Петя покраснел.
– Да он ничего не велел. Я думаю, можно? – сказал он вопросительно.
– Ну, ладно, – сказал Денисов. И, обратившись к своим подчиненным, он сделал распоряжения о том, чтоб партия шла к назначенному у караулки в лесу месту отдыха и чтобы офицер на киргизской лошади (офицер этот исполнял должность адъютанта) ехал отыскивать Долохова, узнать, где он и придет ли он вечером. Сам же Денисов с эсаулом и Петей намеревался подъехать к опушке леса, выходившей к Шамшеву, с тем, чтобы взглянуть на то место расположения французов, на которое должно было быть направлено завтрашнее нападение.
– Ну, бог'ода, – обратился он к мужику проводнику, – веди к Шамшеву.
Денисов, Петя и эсаул, сопутствуемые несколькими казаками и гусаром, который вез пленного, поехали влево через овраг, к опушке леса.

Дождик прошел, только падал туман и капли воды с веток деревьев. Денисов, эсаул и Петя молча ехали за мужиком в колпаке, который, легко и беззвучно ступая своими вывернутыми в лаптях ногами по кореньям и мокрым листьям, вел их к опушке леса.
Выйдя на изволок, мужик приостановился, огляделся и направился к редевшей стене деревьев. У большого дуба, еще не скинувшего листа, он остановился и таинственно поманил к себе рукою.
Денисов и Петя подъехали к нему. С того места, на котором остановился мужик, были видны французы. Сейчас за лесом шло вниз полубугром яровое поле. Вправо, через крутой овраг, виднелась небольшая деревушка и барский домик с разваленными крышами. В этой деревушке и в барском доме, и по всему бугру, в саду, у колодцев и пруда, и по всей дороге в гору от моста к деревне, не более как в двухстах саженях расстояния, виднелись в колеблющемся тумане толпы народа. Слышны были явственно их нерусские крики на выдиравшихся в гору лошадей в повозках и призывы друг другу.
– Пленного дайте сюда, – негромко сказал Денисоп, не спуская глаз с французов.
Казак слез с лошади, снял мальчика и вместе с ним подошел к Денисову. Денисов, указывая на французов, спрашивал, какие и какие это были войска. Мальчик, засунув свои озябшие руки в карманы и подняв брови, испуганно смотрел на Денисова и, несмотря на видимое желание сказать все, что он знал, путался в своих ответах и только подтверждал то, что спрашивал Денисов. Денисов, нахмурившись, отвернулся от него и обратился к эсаулу, сообщая ему свои соображения.
Петя, быстрыми движениями поворачивая голову, оглядывался то на барабанщика, то на Денисова, то на эсаула, то на французов в деревне и на дороге, стараясь не пропустить чего нибудь важного.
– Пг'идет, не пг'идет Долохов, надо бг'ать!.. А? – сказал Денисов, весело блеснув глазами.
– Место удобное, – сказал эсаул.
– Пехоту низом пошлем – болотами, – продолжал Денисов, – они подлезут к саду; вы заедете с казаками оттуда, – Денисов указал на лес за деревней, – а я отсюда, с своими гусаг'ами. И по выстг'елу…
– Лощиной нельзя будет – трясина, – сказал эсаул. – Коней увязишь, надо объезжать полевее…
В то время как они вполголоса говорили таким образом, внизу, в лощине от пруда, щелкнул один выстрел, забелелся дымок, другой и послышался дружный, как будто веселый крик сотен голосов французов, бывших на полугоре. В первую минуту и Денисов и эсаул подались назад. Они были так близко, что им показалось, что они были причиной этих выстрелов и криков. Но выстрелы и крики не относились к ним. Низом, по болотам, бежал человек в чем то красном. Очевидно, по нем стреляли и на него кричали французы.
– Ведь это Тихон наш, – сказал эсаул.
– Он! он и есть!
– Эка шельма, – сказал Денисов.
– Уйдет! – щуря глаза, сказал эсаул.
Человек, которого они называли Тихоном, подбежав к речке, бултыхнулся в нее так, что брызги полетели, и, скрывшись на мгновенье, весь черный от воды, выбрался на четвереньках и побежал дальше. Французы, бежавшие за ним, остановились.
– Ну ловок, – сказал эсаул.
– Экая бестия! – с тем же выражением досады проговорил Денисов. – И что он делал до сих пор?
– Это кто? – спросил Петя.
– Это наш пластун. Я его посылал языка взять.
– Ах, да, – сказал Петя с первого слова Денисова, кивая головой, как будто он все понял, хотя он решительно не понял ни одного слова.
Тихон Щербатый был один из самых нужных людей в партии. Он был мужик из Покровского под Гжатью. Когда, при начале своих действий, Денисов пришел в Покровское и, как всегда, призвав старосту, спросил о том, что им известно про французов, староста отвечал, как отвечали и все старосты, как бы защищаясь, что они ничего знать не знают, ведать не ведают. Но когда Денисов объяснил им, что его цель бить французов, и когда он спросил, не забредали ли к ним французы, то староста сказал, что мародеры бывали точно, но что у них в деревне только один Тишка Щербатый занимался этими делами. Денисов велел позвать к себе Тихона и, похвалив его за его деятельность, сказал при старосте несколько слов о той верности царю и отечеству и ненависти к французам, которую должны блюсти сыны отечества.

[1] [slovar-vocab.com/russian-english/dictionary/raskraska-2536841.html Раскраска]

[2] Birkhoff, G. D. and Lewis, D. C. «Chromatic Polynomials.» Trans. Amer. Math. Soc. 60, 355—451, 1946.

[1]

[2]