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

Хроматическое число
3-раскраска графа Петерсена

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

Содержание

Определение

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

V=\bigcup_i^{} C_i;\ C_i\cap C_j=\varnothing,

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

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

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

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

реберная раскраска кубического графа

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

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

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

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

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

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

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

|V(G)| = 1 \Rightarrow P(G,t)=t.

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

G_1 \cap G_2 = \emptyset \Rightarrow P((G_1 \cup G_2),t) = P(G_1,t)P(G_2,t).

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

P(G,t)=P(G-(u,v), t) - P(G/(u,v),t),

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

P(G,t)=P(G+(u,v), t) + P(G \Uparrow (u,v),t),

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

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

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

P(G,t) \ge 0.

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

P(G,t) > 0.

Обобщения

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

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

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

См. также

Примечания

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

Литература

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

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Полезное


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

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

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

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

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

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

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

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

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

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

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


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»