Ориентированные и неориентированные графы план Введение Основные определения

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