Раскраска графов

Теорема (о пяти красках)

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

Теорема (о четырех  красках)

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

Отметим самую известную интерпретацию проблемы о четырех красках. Пусть имеется географическая карта. Можно ли, используя только 4 краски, изобразить эту карту так, чтобы соседние страны (имеющие общую границу) были окрашены в разный цвет? Понятно, что в соответствующем графе вершинами являются страны, а смежными вершинами являются соседние страны. Ясно, что полученный граф является планарным, и после 1976 г. ответ на этот вопрос является положительным.

Раскраска ребер

Заметим, что в теории графов ставится часто вопрос о реберной раскраске графов,  когда цвета назначаются ребрам. Какое минимальное число цветов (это число иногда называют реберно-хроматическим) нужно, чтобы раскрасить ребра графа так, что любые 2 смежных ребра (т. е. 2 ребра, имеющих общую вершину) были бы окрашены в разный цвет? Для реберно-хроматического числа графа справедлива гораздо более точная оценка, чем для просто хроматического числа, а именно, верна следующая, в какой-то степени удивительная, теорема.

Теорема Визинга. Если в графе максимальная степень вершин равна r, то реберно-хроматическое число равно либо r, либо r +1.

Заметим, что до сих пор  нет “хороших” критериев для  графов, когда же именно реберно-хроматическое  число равно r, а когда r + 1.

Раскраска ребер (или реберная раскраска) называется правильной, если любые два ребра, имеющие общую  вершину, окрашены в разные цвета. Минимальное  число цветов, необходимое для  правильной раскраски ребер графа  , называется хроматическим индексом графа и обозначается через  .

Очевидно, что простейший алгоритм нахождения реберно-хроматического числа (и соответствующей раскраски  ребер) состоит в следующем: по данному  графу строим так называемый двойственный граф: ребра графа соответствуют вершинам нового (двойственного) графа, причем, если 2 ребра имеют общую вершину, то они являются смежными и в двойственном графе соединены ребром. После этого раскрашиваем наилучшим образом вершины двойственного графа и, переходя к “старому” графу, получаем (одну из возможных) наилучших реберных раскрасок графов.

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

Применение задачи о раскраске

Теория расписаний

В задачах теории расписаний осмотры представляются в виде временных  интервалов. Каждому осмотру можно  сопоставить вершину некоторого графа, причем две любые вершины графа будут соединены ребром лишь тогда, когда соответствующие им осмотры нельзя осуществлять одновременно. Требуется составить такой график осмотра, который связан с наименьшими временными затратами (с учетом приведенных выше ограничений на «совместимость» осмотров). Эта задача эквивалентна задаче о раскраске вершин графа с использованием наименьшего числа цветов. Хроматическое число графа как раз и соответствует осмотру, требующему наименьших временных затрат.

Распределение ресурсов

Пусть для выполнения каких-то n работ надо распределить m имеющихся в наличии ресурсов. Считаем, что каждая из работ выполняется за некоторый (одинаковый для всех работ) промежуток времени и что для выполнения i-й работы требуется подмножество ресурсов S_i.

Построим граф G: каждой работе соответствует определенная вершина графа, а ребро (x_i, x_j) существует в графе тогда и только тогда, когда для выполнения i-й и j-й работ требуется хотя бы один общий ресурс, т. е. когда S_i∩S_j≠Ø. Это означает, что i-я и j-я работы не могут выполняться одновременно. Раскраска графа G определяет тогда некоторое распределение ресурсов (по выполняемым работам), причем такое, что работы, соответствующие вершинам одного цвета, выполняются одновременно. Наилучшее использование ресурсов (т. е. выполнение всех n работ за наименьшее время) достигается при оптимальной раскраске вершин графа G.

Естественно, что круг применения не ограничен приведенными примерами.

 

 

 

 

 

 

 

 

Заключение

В настоящем реферате рассмотрены  математические графы, области их применения,. Рассмотрены способы раскраски вершин и ребер графов и задачи на их применение. Графы достаточно широко применяются в математике, технике, экономике, управлении. Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом (например, сетевой график строительства, графики доставки почты).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список используемой литературы:

1. Аляев Ю.А. , Тюрин С.Ф. Дискретная математика и математическая логика: учебник .- М.:Финансы и статистика, 2006-368с.:ил.
2. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб.для вузов/ Под ред. В.С. Зарубина, А.П. Крищенко. – 3-к изд., стереотип.- М.: Изд-во МГТУ им. Н.Э. Баумана, 2004.- 744с. (Сер. Математика в техническом университете; Вып. XIX).
3. Берж К. "Теория графов и ее применение", М., ИЛ, 1962;
4. Битюцкий В.П., Соколов С.С.Основы дискретной математики: учебное пособие по дисциплине «Дискретная математика» .- Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2005. Ч. 1. 96 c.
5. Носов. В.А. Комбинаторика и теория графов: учебное пособие. - М.: Изд-во МИЭМ( Технический университет),Москва,1999- 166с.