Задача - раскраска - граф
Cтраница 1
Задача раскраски графа тесно связана с построением независимых или внутренне устойчивых подмножеств, а также определением клик графа. Если две любые вершины подмножества X графа G ( X, U), X С X, не смежны, то оно называется внутренне устойчивым. Подмножество Ф С С X графа G ( X, U) называется максимальным внутренне устойчивым подмножеством или независимым, если добавление к нему любой вершины xi С X делает его не внутренне устойчивым. [1]
Рассмотрена задача раскраски графа и описан гибридный ГА ее решения. Основной стратегией для задач раскраски графа являются последовательные и жадные эвристики, которые дают с первой попытки результаты с локальным оптимумом. [2]
Рассмотрим задачу раскраски графа. [3]
Основной стратегией для задач раскраски графа являются последовательные и жадные эвристики, которые дают с первой попытки результаты с локальным оптимумом. [4]
Оптимизация сводится тогда к задаче раскраски графа, где каждый цвет соответствует физическому регистру. Естественно, что не связанные между собой вершины графа могут быть раскрашены в одинаковые цвета, а связанные - не могут. [5]
С другой ] стороны, в [133] показано, что существуют приближенные постановки ЛГР-полных [ задач ( более точно, Р - полных, если следовать обозначениям, принятым в [133]), которые также являются ЛГР-полными, а в [56] показано, что приближенная постановка задачи раскраски графа является в некотором смысле такой же трудной, как и сама задача раскраски графа. Таким образом, Сахни и Гонзалес [133] указывают 5что некоторые трудные комбинаторные задачи являются более трудными, чем другие. [6]
С другой ] стороны, в [133] показано, что существуют приближенные постановки ЛГР-полных [ задач ( более точно, Р - полных, если следовать обозначениям, принятым в [133]), которые также являются ЛГР-полными, а в [56] показано, что приближенная постановка задачи раскраски графа является в некотором смысле такой же трудной, как и сама задача раскраски графа. Таким образом, Сахни и Гонзалес [133] указывают 5что некоторые трудные комбинаторные задачи являются более трудными, чем другие. [7]
Разработка бесконфликтного расписания экзаменов эквивалентна раскраске графов. Однако задача раскраски графов принадлежит к классу NP, поэтому разработка бесконфликтного расписания за разумное время невозможна. Кроме того при планировании экзаменов обычно требуется, чтобы у студента было не больше двух экзаменов в день, а экзамены по различным частям курсам назначаются в один день. Очевидно, что разработка совершенного плана экзаменов невозможна, и поэтому необходима другая техника для получения по крайней мере неплохих планов. [8]
 |
Граф G [ IMAGE ] Колесо W7. [9] |
Алгоритм на основе такой эвристики является жадным, так как он раскрашивает граф последовательно вершину за вершиной, присваивая каждой вершине цвет, если это возможно, не учитывая глобальных последствий такой раскраски. Жадный алгоритм задачи раскраски графа очень быстр ( временная сложность алгоритма О ( п)), так как он рассматривает лишь один из возможных вариантов раскраски каждой вершины. [10]
Рассмотрена задача раскраски графа и описан гибридный ГА ее решения. Основной стратегией для задач раскраски графа являются последовательные и жадные эвристики, которые дают с первой попытки результаты с локальным оптимумом. [11]
Независимые подмножества различаются по числу входящих в них элементов. Жадные стратегии, используемые для задачи раскраски графа, также эффективно применяются для построения семейства независимых подмножеств. Например, построим семейство независимых подмножеств для графа G, представленного на рисунке 6.51. Здесь предварительно произведем упорядочивание вершин по возрастанию, начиная с наименьшей локальной степени. [12]
К задачам вложения графов может быть отнесена задача раскраски вершин графа. Граф G называют К-раскрашиваемым, если существует такое разбиение множества его вершин на К непересекающихся подмножеств, что ребра в G соединяют вершины только из разных подмножеств. Если каждому подмножеству взаимно однозначно поставить в соответствие краску, то граф G не содержит смежных вершин, окрашенных одной краской. Таким образом, согласно определению полного А - дольного графа, задача раскраски графа G в К красок есть задача вложения графа G в полный А-дольный граф. [13]
При раскраске графа любые две смежные вершины не должны иметь один и тот же цвет. Предположим, что имеются три вершины, соединенные в треугольник. Вершины X и У могут быть окрашены в красный или зеленый цвета. Вершина Z может быть окрашена в зеленый или голубой цвета. Задача раскраски графа может быть поставлена следующим образом. [14]
Вершины этого графа обозначают отдельные виды работ на стройке, кроме того, есть еще две вершины: начало строительства и его окончание. Стрелка от работы А к работе В на графе означает, что работа В не может начаться раньше, чем кончится работа А, Около вершин графа указаны числа - продолжительность в днях соответствующей работы. Анализ потоков в сетях, - деятельность любого современного общества тесно связана с разного рода сетями - например транспорт, распределение товаров, различные коммуникации, электронные средства связи и т.п. Поэтому математический анализ таких сетей стал предметом функциональной важности. Теория графов позволяет проанализировать потоки в сетях, выявить наиболее и наименее загруженные участки сетей и, таким образом сформировать комплекс практических мер по повышению эффективности и экономичности функционирования данной сети. Задачи о составлении расписаний - решаются путем построения графа, вершины которого обозначают лекции по различным предметам, а ребра соединяют те пары лекции, которые не должны быть назначены на одно и то же время. Для решения задачи раскраски графа вводится понятие хроматической функции. Теория графов позволяет найти хроматическую функцию Po ( k) для любого заданного графа. Непосредственную связь с теорией графов имеет теория линейного программирования, имеющая широкое применение во многих прикладных науках, в т.ч. в экономике. [15]
Страницы: 1