Раскраска графов. Хроматические графы

Пусть G = (S, U) – неориентированный граф.

Определение 14.1. Раскраской графа называется такое приписывание цветов его вершинам, что любые две различные смежные вершины имеют разный цвет.

Определение 14.2. Хроматическим числомc(G) графа G называется минимальное число цветов, требующееся для его раскраски. При этом если c(G) = k, то граф G называется k-хроматическим.

Найдем хроматические числа некоторых известных графов. Например,

c(K_n) = n, c( ) = 1, c(K_n,m) = 2, c(D) = 2, где – дополнение к графу K_n, а

D – дерево.

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

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

В 1879 году английский математик Кэли сформулировал гипотезу четырëх красок: «Всякий планарный граф 4-раскрашиваем».

Попытки доказать эту гипотезу привели к 1890 году к появлению следующей теоремы.

Теорема 14.1 (Хивуда). Всякий планарный граф 5-раскрашиваем. 

В 1976 году американские математики К. Аппель и В. Хейкен доказали гипотезу четырëх красок, существенно используя при этом компьютерные вычисления. Следует отметить, что такое доказательство является очень сложным и трудно воспроизводимым, поэтому оно не удовлетворяет многих математиков.

Список литературы

1. Андерсон Дж. А. Дискретная математика и комбинаторика / Дж. А. Андерсон. – М.: Вильямс, 2004.

2. Асанов М.О. Дискретная математика: графы, матроиды, алгоритмы: учеб. пособие / М.О. Асанов, В.А. Баранский, В.В. Расин. – СПб.: Лань, 2010.

3. Кузнецов О.П. Дискретная математика для инженера / О.П. Кузнецов. – СПб.: Лань, 2007.

4. Лапшин А.Б. Дискретная математика и математическая логика. Ч. 4. Элементы теории графов / А.Б. Лапшин, О.Б. Садовская. – Кострома: Изд-во Костром. гос. технол. ун-та, 2005.

5. Нефедов В.Н. Курс дискретной математики: учеб. пособие / В.Н. Нефедов, В.А. Осипова. – М.: Изд-во МАИ, 1992.

6. Палий И.А. Дискретная математика. Курс лекций / И.А. Палий. – М.: Эксмо, 2008.

7. Редькин Н.П. Дискретная математика: Курс лекций для студентов-механиков: учеб. пособие / Н.П. Редькин. – СПб.: Лань, 2006.

8. Судоплатов С.В. Дискретная математика: учебник / С.В. Судоплатов, Е.В. Овчинникова. – М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2007.

9. Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий / С.Д. Шапорев. – СПб.: БХВ-Петербург, 2006.

10. Шепелев Ю.П. Дискретная математика: учеб. пособие / Ю.П. Шепелев. – СПб.: Лань, 2008.

Учебное издание

Чередникова Алла Викторовна

Землякова Ирина Владимировна

ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ

Учебно-методическое пособие

Подписано в печать 13.02.2012. Формат бумаги 60х84 1/16.

Печать трафаретная. Печ. л. 1,56. Заказ 61. Тираж 30.

Костромской государственный технологический университет.

Редакционно-издательский отдел

Кострома, ул. Дзержинского,17

Тел. 31-15-21, e-mail: [email protected]