ГРАФА РАСКРАСКА

ГРАФА РАСКРАСКА

- приписывание цветов вершинам и (или) ребрам графа, обладающее определенными свойствами. Правильная вершинная (реберная) раскраска - это раскраска вершин (ребер) графа, при к-рой любые смежные вершины (ребра) окрашены в разные цвета. Правильную вершинную раскраску часто наз. просто раскраской графа. Граф наз. k-pаскрашиваемым, если существует правильная вершинная Г. p. kцветами. Наименьшее число цветов, достаточное для правильной вершинной раскраски графа G, наз. хроматическим числом графа G. Если , то граф Gназ. k- хроматическим. Граф является 2-хроматическим тогда и только тогда, когда он не содержит простых циклов нечетной длины. Если максимальная степень вершин графа Gравна г, то граф Gвсегда r-раскрашиваем, за исключением двух случаев: 1) r=2 и G имеет компоненту связности, являющуюся циклом нечетной длины; 2) r>2 и полный граф с r+1 вершинами является компонентой связности графа G.

Для объединения двух графов н справедливо неравенство причем равенство здесь достигается. Более того, если граф G такой, что , то найдутся подграфы и в G такие, что ,

Если G - граф с пвершинами н - граф, дополнительный к G, то


причем все границы достигаются. Хроматическим числом двумерной поверхности Sназ. максимум хроматич. чисел графов, допускающих правильную укладку на S(см. Графа укладка). Для ориентируемой поверхности рода справедливо равенство


При это равенство принимает вид , что составляет утверждение четырех красок задачи. Пусть - число различных правильных раскрасок графа G с нумерованными вершинами в tили меньше цветов, тогда для любого графа G функция есть многочлен от переменной t, наз. хроматическим многочленом графа G. Напр., хроматич. многочлен любого дерева с пвершинами имеет вид . Реберное хроматич. число (хроматический класс) графа G-это наименьшее число цветов, достаточное для правильной раскраски ребер графа G. Если максимальная степень вершин графа G равна k(допускаются кратные ребра), то


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

Задачи на Г. р. возникают при проектировании коммуникаций, в радиоэлектронике, в планировании эксперимента н других областях.

Лит.:[1] Xарари Ф., Теория графов, пер. с англ." М., 1973; [2] Оре О., Теория графов, пер. с англ., М., 1968; [3] Шеннон К. Э., "Кибернетический сборник", 1960, в. 2, с. 249-53. В. Б. Алексеев.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Игры ⚽ Поможем решить контрольную работу

Полезное


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

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

  • Раскраска графов — Проблема четырёх красок Проблема четырёх красок математическая задача, предложенная Гутри (англ.) в 1852 году. Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок …   Википедия

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

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

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

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

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

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

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

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


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

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