Раскраска графа | это... Что такое Раскраска графа? (original) (raw)

Раскраска графа

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

Содержание

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

Определение

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

$C_1, C_2, ..., C_k;\ V=\bigcup_i^{} C_i;\ C_i\cap C_j=\varnothing$

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

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

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

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

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

Хроматический класс графа 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 − 12_t_6 + 67_t_5 − 230_t_4 + 529_t_3 − 814_t_2 + 775_t − 352)

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

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

Литература

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

↑ Birkhoff, G. D. and Lewis, D. C. "Chromatic Polynomials." Trans. Amer. Math. Soc. 60, 355-451, 1946.

Wikimedia Foundation.2010.

Полезное

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

ГРАФА РАСКРАСКА — приписывание цветов вершинам и (или) ребрам графа, обладающее определенными свойствами. Правильная вершинная (реберная) раскраска это раскраска вершин (ребер) графа, при к рой любые смежные вершины (ребра) окрашены в разные цвета. Правильную… … Математическая энциклопедия
Раскраска графов — Проблема четырёх красок Проблема четырёх красок математическая задача, предложенная Гутри (англ.) в 1852 году. Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок … Википедия
Практическое применение раскраски графов — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Раскраска графов практически применяется (постановку задачи различиных раскрасок здесь обсуждаться не будет) дл … Википедия
Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия
Хроматическое число — 3 раскраска графа Петерсена Хроматическое число графа G минимальное число цветов, в которые можно раскрасить вершины … Википедия
Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Длина пути в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Инцидентность — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Мультиграф — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия